Solving a non-homogeneous linear recurrence relation

Question

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

$$a_{n}=2a_{n-1}-a_{n-2}+2^n+2$$

$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.

Answer 1

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}}$$

Answer 2

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$

Answer 3

Generally speaking, you can solve any non-homogeneous linear recurrence relations with constant coefficients using several methods depending on the recurrence formula.

First-order non-homogeneous linear recurrences: guessing, iteration or telescoping

A first-order non-homogeneous linear recurrence has the form $u_n=au_{n-1}+p\left(n\right)\ \text{with}\ a\in\mathbb{R}$ and you can often guess the closed formula or use iteration to find a recurring pattern. Also, first-order recurrence relations always telescope to a simple sum, starting with $u_n-u_{n-1}$ you can build the corresponding telescoping sum and determine the closed formula. Then, induction is naturally used to prove the found formula.

There is also a general method to determine the closed formula of non-homogeneous linear recurrences of the form $u_n=au_{n-1}+b\ \text{with}\ a,b\in\mathbb{R}$ using the fixed point theorem, let the fixed point $\alpha$ satisfies $\alpha=a\alpha+b$ and you have

$$u_n-\alpha=a\left(u_{n-1}-\alpha\right)$$

This theorem can then be used to construct a translated sequence $v_n=u_n-\alpha$ to determine the closed formula for $u_n$ depending on the initial value. However, this elegant method is not mentioned in most calculus books and there is not many online resources on the topic (except this blog article). I was introduced to this method during my high school in France.

Note: this approach is very similar to the one used for solving second-order and higher non-homogeneous linear recurrences. Namely solving the characteristic polynomial equation for the homogeneous recurrence relation and then finding the particular solution, which turns out to be $\alpha$ in this situation.

---

Second-order and higher non-homogeneous linear recurrences: the characteristic polynomial equation

For second-order and higher order recurrence relations, trying to guess the formula or use iteration will usually result in a lot of frustration. Also, these recurrence relations will usually not telescope to a simple sum. The idea here is to solve the characteristic polynomial equation associated with the homogeneous recurrence relation.

Note: the characteristic polynomial equation is directly derived from generating series, the proof is admitted here.

A second-order non-homogeneous linear recurrence has the form $u_n=au_{n-2}+bu_{n-2}+p\left(n\right)\ \text{with}\ a,b\in\mathbb{R}\ \text{and}\ p\left(n\right)\neq0$ and from there you can distinguish its associated homogeneous relation $u_n=au_{n-2}+bu_{n-2}$ and the non-homogeneous part $p\left(n\right)$. The solution of a non-homogeneous linear recurrence relation has thus two parts.

• The solution $\left\{u_n^H\right\}$ of the associated homogeneous recurrence relation $u_n=au_{n-2}+bu_{n-2}$
• The solution $\left\{u_n^P\right\}$ of the non-homogeneous part $p\left(n\right)$ called the particular solution

We eventually have the final solution $\left\{u_n^H+u_n^P\right\}$ as a combination of the two previous solutions.

The homogeneous solution can be found using the roots of the associated characteristic polynomial equation. The particular solution is then found based on the homogeneous solution and chosen to satisfy the initial values $u_0$ and $u_1$.

Another method to solve a non-homogeneous recurrence is the method of symbolic differentiation. If $p\left(n\right)$ is a polynomial with degree $r$, then this non-homogeneous recurrence can be reduced to a homogeneous recurrence by applying the method of symbolic differentiation $r$ times. You can then find the roots of the characteristic polynomial in order to solve the relation.

I will edit this post and add more content when I have more free time.