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

Question

Find all solutions of the recurrence relation a_n=5a_(n-1)-6a_(n-2)+2^n+3n.

Answer 1

Let f(z) generating function. f(z) = $\sum$ a_n*zⁿ and if n < 0 then a_n = 0

a_n = 5*a_n-1 -n6*a_n-2 + 2ⁿ + 3*n multiply by zⁿ and add up

$\sum$ 2ⁿ*zⁿ = 1/(1-2z) , $\sum$ 3*n*zⁿ = 3z/(1-z)² =>

f(z) = 5*f(z)*z -6*f(z)*z² + 1/(1 - 2z) + 3z/(1-z)² + b + c*z =>

a₀ = f(0) = 1 + b , a₁ = f'(0) =5*f(0)+ 2 + 3 = 5*a₀ + 5 + c =>

b = a₀ - 1 , c = a₁ - 5a₀ - 5 =>

f(z) = (1+3z)/((1-2z)(1-3z)(1-z)²) + (a₀ - 1 + (a₁ - 5a₀ - 5)*z)/((1-2z)(1-3z)) =>

a_n = (a₀ - 1)*(3ⁿ⁺¹ - 2ⁿ⁺¹) + (a₁ - 5a₀ - 5)*(3ⁿ - 2ⁿ) + (15 - 5*2ⁿ⁺³ + 3ⁿ⁺³ + 4n)/2