Answer to Question #117513 in Discrete Mathematics for Pappu Kumar Gupta

Question

Solve the recurrence relation a_n-4a_n-1+5a_n-2-2a_n-3=1+2^n

Answer 1

$a_n-4a_{n-1}+5a_{n-2}-2a_{n-3}=1+2^n$

$a_n=4a_{n-1}-5a_{n-2}+2a_{n-3}+(1+2^n)$

Characteristic equation: $r^3-4r^2+5r-2=(r-1)^2(r-2)=0, \ \ r_1=1, r_2=2$

Then $a^{(0)}_n=(c_1+c_2n)r_1^n+c_3r_2^n=c_1+c_2n+c_32^n$ is a solution of $a_n=4a_{n-1}-5a_{n-2}+2a_{n-3}$

We need do find particular solution of $a_n=4a_{n-1}-5a_{n-2}+2a_{n-3}+F(n), \ \ F(n)=(1+2^n)$

1 and 2 are characteristic roots of multiplicity 2 and 1 respectively.

Then particular solution has form of $a^{(p)}_n=n^2(b_tn^t+b_{t-1}n_{t-1}+...+b_1n+b_0)1^n+ n(d_kn^k+d_{k-1}n_{k-1}+...+d_1n+d_0)2^n$

Suppose that $a^{(p)}_n=n^2 b_0\times 1^n+nd_02^n=b_0n^2+d_0n2^n$ and substitute it:

$b_0n^2+d_0n2^n=4(b_0(n-1)^2+d_0(n-1)2^{n-1})-5(b_0(n-2)^2+d_0(n-2)2^{n-2})+2(b_0(n-3)^2+d_0(n-3)2^{n-3})+1+2^n=b_0(n^2+2)+d_0n2^n-d_02^{n-2}+1+2^n$

$b_0n^2+d_0n2^n=b_0(n^2+2)+d_0n2^n-d_02^{n-2}+1+2^n$

$(2b_0+1)+(2^n-d_02^{n-2})=0, \ \ \forall n\in\mathbb{N}$

$b_0=-1/2, \ \ d_0=4$

Solution of the recurrence relation is sum of $a^{(0)}_n$ and $a^{(p)}_n$ .

We have the following solution of the recurrence relation:

$a_n=c_1+c_2n+c_32^n-1/2n^2+n2^{n+2}$ .

Answer: $a_n=c_1+c_2n+c_32^n-1/2n^2+n2^{n+2}.$

The following source is used:

https://courses.ics.hawaii.edu/ReviewICS241/morea/counting/RecurrenceRelations2-QA.pdf