Question

Let `f(m,1) = f(1,n) = 1` for `m geq 1`, `n geq 1`, and let `$f(m,n) = f(m-1,n) + f(m,n-1) +...` ?

Let `f(m,1) = f(1,n) = 1` for `m geq 1`, `n geq 1`, and let `f(m,n) = f(m-1,n) + f(m,n-1) + f(m-1,n-1)` for `m > 1` and `n > 1.` Also, let

`S(k) = \sum_{a+b=k} f(a,b), \text{ for } a geq 1, b geq 1`

Note: The summation notation means to sum over all positive integers `a,b` such that `a+b=k.`

Given that

`S(k+2) = pS(k+1) + qS(k) \text{ for all } k \geq 2,`

for some constants `p` and `q`, find `pq`

Answer 1

`pq=2`

Explanation:

Solving the difference equation

`S(k+2) = pS(k+1) + qS(k)`

Proposing `S(k) = C a^k` and substituting into the difference equation

`C a^2 xx a^k = p C a xx a^k + q C a^k rArr a^2-pa-q=0`

we get at

`S(k)=2^-k (p - sqrt[p^2 + 4 q])^k C_1+ 2^-k (p + sqrt[p^2 + 4 q])^k C_2`

and also

`{(S(2)=f(1,1)=1),(S(3)=f(1,2)+f(2,1)=2):}`

so

#{(C_1=(2 (-4 + p + sqrt[p^2 + 4 q]))/(sqrt[ p^2 + 4 q] (p - sqrt[p^2 + 4 q])^2)),(C_2=(2 (4 - p + sqrt[p^2 + 4 q]))/(sqrt[p^2 + 4 q] (p + sqrt[p^2 + 4 q])^2 )):}#

and

#S(k) =( ((p - sqrt[p^2 + 4 q])^(k-2) (p -4+ sqrt[p^2 + 4 q]) + (4 - p + sqrt[p^2 + 4 q]) (p + sqrt[p^2 + 4 q])^(k-2)))/(2^(k-1)sqrt[p^2 + 4 q] )#

and thus we have

`S(2)=1`
`S(3)=2`
`S(4)=5=2p+q`
`S(5)=12=2 p^2 + (2 + p) q`

So solving

`{(2p+q=5),(2p^2+(p+2)q=12):}`

we obtain

`p=2` and `q = 1`