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?

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

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


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.

  • $\begingroup$ 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. $\endgroup$ – B. Lee Sep 17 '14 at 19:50
  • 1
    $\begingroup$ @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. $\endgroup$ – Semiclassical Sep 17 '14 at 19:58
  • 1
    $\begingroup$ 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. $\endgroup$ – 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.


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.