So i have this non-homogeneous linear recurrence relation to solve:


$a_{1}=7$ and $a_{2}=19$

I know that the non-homogeneous part is $2^n$ and i know how to solve homogeneous linear recurrence relations, but when i get a non-homogeneous one i have no idea how to approach it.

I have this as well: $b_{n}=Aq^n$ when the non-homogeneous part is an exponential function look-alike. So yeah i know it should be of help, but i don't know how to apply it in solution. I need to make a characteristic polynomial as well(if that's what it is called) but i am really stuck at using all that in practical example.

So i am not sure how to solve it, any hints or help would really be appreciated.


If we set $a_n=b_n+2^{n+2}$ we have $$ b_n+2^{n+2}=2 b_{n-1} + 2^{n+2}-b_{n-2}-2^{n}+2^n + 2 $$ or just: $$ b_n = 2b_{n-1}-b_{n-2}+2 $$ In a similar way, if we set $b_n=c_n+ n^2$ we have $$ c_n=2c_{n-1}-c_{n-2}. $$ $a_1=7, a_2=19$ lead to $b_1=-1,b_2=3$ and to $c_1=-2, c_2=-1$.
By the previous homogeneous recurrence relation, it follows that $c_n=n-3$, hence $b_n=n^2+n-3$ and $$\boxed{\phantom{\sum}a_n = \color{red}{2^{n+2}+n^2+n-3}\phantom{\sum}}$$


Define: $g_n := a_{n}-a_{n-1}$

Then $a_{n}=2a_{n-1}-a_{n-2}+2^n+2 \implies a_{n}-a_{n-1}=a_{n-1}-a_{n-2}+2^n+2 \\\ \implies g_n = g_{n-1} + 2^n +2 \implies g_n- g_{n-1} = 2^n +2$

$$g_n- g_{n-1} = 2^n +2 $$ $$g_{n-1}- g_{n-2} = 2^{n-1} +2 $$ $$.$$ $$.$$ $$.$$ $$g_3- g_{2} = 2^3 +2 $$

Since $g_2 = 19-7=12$, then $g_n = \sum_{i=3}^n g_i-g_{i-1} +g_2 = 2^3\times \frac{1-2^{n-3+1}}{1-2} + 2\times (n-3+1) + 12= 2^{n+1}+2n$ Therefore $a_n-a_{n-1} = 2^{n+1}+2n$.For all $n \geq 3$.

$$a_n-a_{n-1} = 2^{n+1}+2n$$ $$a_{n-1}-a_{n-2} = 2^{n}+2(n-1)$$ $$.$$ $$.$$ $$.$$ $$a_3-a_{2} = 2^4+2 \times 3$$

$a_n = \sum_{i = 3}^{n} a_i - a_{i-1} + a_{2} = 2^4 \times \frac{1-2^{n-3+1}}{1-2}+ (3+n) \times (n-3+1) + 19 = n^2+n +2^{n+2}-3$. For all $n \geq 3$.

EDIT: For generalization:

$$a_n = Aa_{n-1}+Ba_{n-2} + P(n)$$ Assert: $$a_n - C a_{n-1} = D (a_{n-1} - Ca_{n-2}) + P(n) \implies $$ Where $C,D \in \mathbb C$ \begin{cases}C+D = A \\ CD = -B\end{cases}

so $C,D$ is roots of $x^2-Ax-B=0$


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.