# Solving a recurrence relation of second order

I have a pattern, which goes: $x_n =2(x_{n-1}-x_{n-2})+x_{n-1}$ and this pattern holds for all $n \ge 2$. I also know that $x_0 = 1 \ and \ x_1 = 5.$

$x_2 = 2(x_1-x_0)+x_1$

\begin{align} x_3 = 2(x_2-x_1) + x_2 &= 2(2(x_1-x_0)+x_1)+x_2\\ &=2^2x_1-2^2x_0+2x_ 1+x_2 \end{align}

\begin{align} x_4 = 2(x_3-x_2)+x_3 &= 2(2^2x_1-2^2x_0+2x_1+x_2-(2(x_1-x_0)+x_1)+x_2)+x_3 \\ &=2^3x_1-2^3x_0+2^2x_1+2x_2-(2x_1-2x_0+x_1)+x_2)+x_3 \\ &=2^3x_1-2^3x_0+2^2x_1+2x_2 - 2x_1 +2x_0-x_1+x_2+x_3 \\ &=2^2x_1-2^2x_0+2x_1+2^2x_2+x_3 \end{align}

(The formula below is no longer valid, I noticed since last edit) $[x_n = 2^{n-1}(x_1-x_0) + \sum^{n-1}_{i=0}(2^{n-2-i}x_i)]$

Well, here I'm confused; there's no pattern to be found anymore, or am I just blind?

• Do you mean that the pattern holds for all $n\geq 2$ in the first line? – Semiclassical Sep 17 '14 at 19:00
• I clarified my first sentence, if that helps. – B. Lee Sep 17 '14 at 19:03
• It helps somewhat, but do you really mean that it's valid for all $x\geq 2$ rather than $n \geq 2$? – Semiclassical Sep 17 '14 at 19:05
• You're right, I changed that as well. – B. Lee Sep 17 '14 at 19:05
• I changed and added a bit because I think I did something wrong the first time around. – B. Lee Sep 17 '14 at 19:27

Let's write the formula as $x_n = 3x_{n-1} - 2x_{n-2}$.

The characteristic equation is $\lambda^2 - 3\lambda + 2 = 0$, i.e. $(\lambda-2)(\lambda-1) = 0$.

The roots are $\lambda_1 = 2$ and $\lambda_2 = 1$, so the general solution is $x_n = C_1\lambda_1^n + C_2\lambda_2^n = C_1 \cdot 2^n + C_2$.

Using the initial conditions $x_0 = 1$ and $x_1 = 5$, we get:

$x_0 = C_1+C_2 = 1$

$x_1 = 2C_1+C_2 = 5$

Solving gives us $C_1 = 4$ and $C_2 = -3$.

Therefore, the specific solution (based on the initial conditions) is $x_n = 4\cdot 2^n - 3$.

Since I'm a fan of generating-function methods, I'll demonstrate how that works here. (It'll prove to be overkill, but it's perfectly straightforward). Let $X(t)=\sum_{n=0}^\infty x_n t^n$, which is the formal power series in $t$ with coefficients. We have the recurrence relation $x_n=2(x_{n-1}-x_{n-2})+x_{n-1}=3x_{n-1}-2x_{n-2}$. Since this is valid for $n\geq 2$, let's focus on the terms in $X(t)$ of at least quadratic order; with this in mind we may write

\begin{align} X(t)-x_0-x_1 t &=\sum_{n=2}^\infty x_{n}t^n\\ &=\sum_{n=2}^\infty 3x_{n-1}t^n-\sum_{n=2}^\infty 2x_{n-2}t^n\quad(\text{recurrence relation})\\ &=3t\cdot\sum_{n=1}^\infty x_{n}t^n-2t^2\cdot \sum_{n=0}^\infty x_{n}t^n\quad(\text{by shifting indices})\\ &=3t(X(t)-x_0)-2t^2 X(t) \end{align}

which we may rearrange to solve for $X(t)$ as $$(1-3t+2t^2)X(t)=x_0+(x_1-3x_0)t\implies X(t)=\frac{1+2t}{(1-t)(1-2t)}$$ where we have plugged in $(x_0,x_1)=(1,5)$. To read off series coefficients we expand in partial fractions as $$X(t)=\frac{1+2t}{(1-t)(1-2t)}=\frac{4(1-t)-3(1-2t)}{(1-t)(1-2t)}=\frac{4}{1-2t}-\frac{3}{1-t}$$ and since these are geometric series we immediately have $\boxed{x_n=4\cdot 2^n-3}$ which matches the first solution.

• This is awesome. I have one question though. When you shift indices, what is the process? I'm a little confused by that part. Anyhow, your answer is very well written. – B. Lee Sep 17 '14 at 19:50
• @XMLParsing: It's just relabeling and factoring, really. For instance, $$\sum_{n=2}x_{n-1} t^n=x_1 t^2+x_2 t^3+\cdots=t\cdot\left(x_1t+x_2 t^2+\cdots\right)=t\cdot \sum_{n=1}x_{n=1}t^n.$$ Or you can read that as $\sum_{n=2}x_{n-1} t^n=\sum_{m=1}x_{m} t^{m+1}$ where $m=n-1$, and then decide to relabel $m$ to $n$ since the name doesn't matter. – Semiclassical Sep 17 '14 at 19:58
• To draw a connection between this computation and the other quick solution I gave, note that $$(1-t)X(t)=\frac{1+2t}{1-2t}=-1+\frac{4}{1-2t}=3+8t+16t^2+32t^3+\cdots$$ has every term past the first being half of its successor. Since $(1-t)X(t)$ has coefficients $x_0,\,x_1-x_0,\,x_2-x_1,\ldots$, this means that $x_n-x_{n-1}=2(x_{n-1}-x_{n-2})$ for $n\geq 2$ which is the same relationship found by inspection in the other answer. – Semiclassical Sep 17 '14 at 21:47

Here is another answer which uses a trick special to this problem. Note that the recurrence may be written as $x_n-x_{n-1}=2(x_{n-1}-x_{n-2})$ for $n\geq 2$. So the difference in terms is doubling at each step, and if we iterate this we come to $x_n-x_{n-1}=2^{n-1}(x_1-x_0)=2^{n+1}$ since $x_1-x_0=4$. So we can solve the recurrence $x_n=x_{n-1}+2^{n+1}$ instead (valid for $n\geq 1$). But this iterates to

\begin{align} x_n &=x_{n-1}+2^{n+1}\\ &=x_{n-2}+2^n+2^{n+1}\\ &\cdots\\ &=x_0+2^2+2^3+\cdots +2^{n+1}\\ &=1+4\cdot(2^{n}-1)\\ &=4\cdot 2^{n+2}-3 \end{align}

which is the same answer as in the other solutions.