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

Question

Use generating functions to solve the recurrence relation a_k=3a_(k-1)+4^(k-1) with the initial condition a_0=1.

Answer 1

Given $a_0 = 1$, and $a_k=3a_{k-1}+4^{k-1}$ .

So, $a_1 = 3a_0 + 4^0 = 3 + 1 = 4$

$a_2 = 3a_1 + 4^1 = 12+4 = 16 \\ a_3 = 3a_2 + 4^2 = 48 + 16 = 64 \\ a_4 = 3a_3+4^3 = 192+64 = 256$ and so on.

Hence the given series is $1, 4 , 16 , 64, 256$ , _ _ _ _.

Hence, the generating function is $a_n = 4^{n}$ .