Answer to Question #275764 in Discrete Mathematics for Himanshi

Question

Find the solution of the recurrence relation an = 4an−1 − 3an−2 + 2^n + n + 3 with

a^0 = 1 and a^1 = 4.

Answer 1

Let us find the solution of the recurrence relation $a_n = 4a_{n−1} − 3a_{n−2} + 2^n + n + 3$ with

$a_0 = 1$ and $a_1 = 4.$

The characteristic equation $k^2-4k+3=0$ of the homogeous recurrence relation $a_n -4a_{n−1} + 3a_{n−2}=0$ is equivalent to $(k-1)(k-3)=0,$ and hence has the solutions $k_1=1$

and $k_2=3.$ Therefore, the general solution of the relation $a_n = 4a_{n−1} − 3a_{n−2} + 2^n + n + 3$ is of the form $a_n=c_1+c_23^n+b_n^p,$ where $b_n^p=a2^n+n(bn+c)=a2^n+bn^2+cn.$

It follows that

$a2^n+bn^2+cn$

$=4(a2^{n-1}+b(n-1)^2+c(n-1))-3(a2^{n-2}+b(n-2)^2+c(n-2))+2^n+n+3$

$=4a2^{n-1}+4b(n^2-2n+1)+4c(n-1)-3a2^{n-2}-3b(n^2-4n+4)-3c(n-2)+2^n+n+3$

$=4a2^{n-1}-3a2^{n-2}+2^n+bn^2+(4b+c+1)n+(-8b+2c+3)$

$=(5a+4)2^{n-2}+bn^2+(4b+c+1)n+(-8b+2c+3).$

It follows that $4a=5a+4,\ c=4b+c+1$ and $-8b+2c+3=0.$

Therefore, $a=-4,\ b=-\frac{1}4,\ c=\frac{1}2(8b-3)=\frac{1}2(-2-3)=-\frac{5}2.$

We conclude that the general solution of the relation $a_n = 4a_{n−1} − 3a_{n−2} + 2^n + n + 3$ is of the form $a_n=c_1+c_23^n-4\cdot2^n-\frac{1}4n^2-\frac{5}2n.$

Since $a_0 = 1$ and $a_1 = 4,$ we get

$1=a_0=c_1+c_2-4$ and $4=a_1=c_1+3c_2-8-\frac{1}4-\frac{5}2=c_1+3c_2-\frac{43}4.$

Therefore, $c_1+c_2=5$ and $c_1+3c_2=\frac{59}4.$ It follows that $c_2=\frac{39}8$ and $c_1=\frac{1}8.$

Consequently, the general solution of the relation $a_n = 4a_{n−1} − 3a_{n−2} + 2^n + n + 3$ is the following:

$a_n=\frac{39}8+\frac{1}83^n-2^{n+2}-\frac{1}4n^2-\frac{5}2n.$