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

Question

Find the solution of the recurrence relation a_n=4a_(n-1)-4a_(n-2)+(n+1).2^n.

Answer 1

Given a_n=4a_(n-1)-4a_(n-2)+(n+1).2ⁿ

Roots Characteristics equation

Let a_n=r²,a_(n-1)=r and a_(n-2)=1

r²=4r-4

r² -4r+4=0

(r-2)²=0

r=2 with multiciplity 2

solution homogeneous linear recurrence relation

a_n=a₁r₁ⁿ+a₂nr₁ⁿ+------+a_kn^(k-1)r₁ⁿ with r₁ a root with multiplicity k of the characteristic equation.

a_n^(h)=a₁ 2ⁿ+ a₂n2ⁿ

Particular solution

F(n)=(n+1)2ⁿ

Since 2 is a root of the characteristic equation with multiplicity 2

So particular solution takes the forms of

a_n^(p)=n²(p₁n+p₀)2ⁿ

Thus the complete solution is the sum of homogeneous solution and particular integral

a_n=a_n^(h)+a_n^(p)=a₁2ⁿ+ a₂n2ⁿ+n²(p₁n+p₀)2ⁿ

In order to find out the coefficient , P.I needs to satisfy the recurrence relation:

a_n=4_(a-1)-4_(a-2)+(n+1)2ⁿ

p₁n³+p₀n²2ⁿ=4p₁(n-1)³2^(n-1)+4p₀(n-1)²2^n-1-4p₁(n-2)³2^n-2-4p₀(n-2)²2^n-2+(n+1)2ⁿ

4p₁n³+4p₀n²=8p₁(n-1)³+8p₀(n-1)²-4p₁(n-2)³-4p₁(n-2)³-4p₀(n-2)²+4(n+1)

4p₁n³+4p₀n²=p₁(4n³-24n+24)+p₀(4n²-8)+4n+4

0=(-24p₁+4)n+(24p₁-8p₀+4)

Equate the coefficients

0=(-24p₁+4) and (24p₁-8p₀+4)=0

Thus p₁=1/6 and p₀=(24p₁+4)/8=(24(1/6)+4)/8=1

Put the value of coefficients in complete solution

we have,

a_n=a_n^(h)+a_n^(p)=a₁2ⁿ+ a₂n2ⁿ+n²(n/6+1)2ⁿ

a_n=(a₁+a₂n+n²+n³/6)2ⁿ