Let f(m,1) = f(1,n) = 1f(m,1)=f(1,n)=1 for m geq 1m1, n geq 1n1, 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

1 Answer
Jun 9, 2017

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