Answer to Question #117136 in Combinatorics | Number Theory for Priya

Question

Use generating functions to solve the recurrence relation a_k=5a_(k-1)-6a_(k-2) with the initial conditions a_0=6 and a_1=30.

Answer 1

Given $a_0=6 = 6(3^1-2^1)$ and $a_1=30 = 6(3^2-2^2)$ .

Also, given the recurrence relation $a_k=5a_{k-1}-6a_{k-2}$ .

Hence, $a_2 = 5 a_1 - 6a_0 = 150 - 36 = 114 = 6 (19) = 6(3^3-2^3)$

$a_3 = 5a_2 - 6a_1 = 5 \times 114 - 6\times 30 = 390 = 6(65) = 6(3^4-2^4)$

$a_4 = 5a_3 - 6a_2 = 5 \times 390 - 6\times 114 = 1266 = 6(211) = 6(3^5-2^5)$ and so on.

Hence, Generating function is $a_k = 6 (3^{k+1}-2^{k+1})= 18\times 3^k−12 \times 2^k$.