# Finding the explicit formula of a given recurrence relation

This is the recurrence relation: $$a_n=2a_{n-1}+2n, a_2=2$$.The way we have found the explicit formulas in my course in the past was to notice some pattern either by finding several values or using the next terms to define $$a_n$$.However, I'm completely lost on the equation above.

The following manipulations yield a homogeneous linear recurrence relation with constant coefficients:

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

$$a_{n-1}=2a_{n-2}+2(n-1)$$

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

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

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

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

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

Can you take it from here?

• This technique is in fact quite general. It works whenever the RHS is itself a solution of an homogeneous equation, it amounts to multiply both sides of the equation by an operator that nullifies the RHS. – PierreCarre Feb 4 at 13:19
• From equation $a_n=4a_{n-1}-5a_{n-2}-2a_{n-3}$ I find the characteristic polynomial $r^3-4r^2-5r^-2=0$,then I find the roots,after that I write $a_n=\alpha (x_1^n)+ \alpha (x_2^n)+ \alpha(x_3^n)$ and find the value of all 3 $\alpha$ -s right? – Tabris Feb 4 at 13:31
• Basically right, though you may find a repeated root here – J. W. Tanner Feb 4 at 13:37

This is a linear difference equation with constant coefficients. You can get the solution as follows

1. Find the general solution of the homogeneous equation $$a_n = 2a_{n-1}$$, which yields $$a_n^h = k 2^n$$.

2. Find a particular solution to the equation: Try something similar to $$2n$$, say $$a_n^* = \alpha n +\beta$$. replacing into the equation you get $$a_n^* = -2n-4$$

3. The general solution is $$a_n =a_n^h + a_n^* = k 2^n -2n -4$$.

4. Using the initial condition you compute $$k$$, to get the particular solution $$a_n = 5\cdot 2^{n-1}-2n-4$$

• Did you mean $5\cdot2^{n-1}$ where you typed $5a^{n-1}$? – J. W. Tanner Feb 4 at 12:06
• @J.W.Tanner Yes, i'll edit. – PierreCarre Feb 4 at 12:09
• Thank you for your contribution. Can you clarify what $a_n^*$ means?I haven't seen that notation used in my course papers. – Tabris Feb 4 at 12:24
• @Tabris No special meaning... It is just to distinguish it form $a_n$. The point is that it is a particular solution of the equation. – PierreCarre Feb 4 at 13:15

$$A_n=2A_{n-1}+2n$$ The solution of $$A_n=2A_{n-1}$$ is $$A_n= C~~ 2^n$$ Next, for $$A_n-2A_{n-1}=2n$$ take $$A_n=pn+q$$, we get $$(pn+q)-2[p(n-1)+q]=2n \implies p=-2, q=-4.$$ The total solution is $$A_n=2^nC-2n-4$$. $$A_2=2$$ gives $$C=5/2.$$ WE finally get $$A_n=5~. 2^{n-1}-2n-4.$$

• Thank you for contribution.Can you explain what does $C2^n$ mean? – Tabris Feb 4 at 12:27
• @Tabris I have written it well now here $C$ multiplies $2^n$. $2$ is like common factor of a GP. – Z Ahmed Feb 4 at 12:31