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#

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#