Solving a recurrence relation of second order

Question

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?

Answer 1

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

This is a linear homogeneous recurrence relation with constant coefficients.

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

Answer 2

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.

Answer 3

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.