Formula for nth term of sequence?

Question

How do you find a formula for the nth term of the sequence defined by:

$x_n=x_{n-1}+2x_{n-2}$

Where $x_0=4$ and $x_1=-1$ ?

$n=1,2,3,\dots$

Answer 1

(Stated without proof:)

To solve a homogeneous linear recurrence of the form $$x_n = a_{1} x_{n-1}+ a_2 x_{n-2}+\dots+a_k x_{n-k}$$

construct the characteristic polynomial, $p(x)$, by moving everything to one side and replacing $x_i$ by $x^i$ and dividing by a sufficiently large power of $x$ to arrive at a polynomial of degree $k$. I.e.

$$p(x)=x^k-a_1x^{k-1}-a_2x^{k-2}-\dots-a_{k-1}x-a_k=0$$

(it is worth mentioning that this characteristic polynomial is exactly the same characteristic polynomial that appears when trying to calculate the eigenvalues of the matrix that describes exactly this scenario)

Factor $p(x)$ and it will be of the form $p(x)=(x-b_1)^{\beta_1}(x-b_2)^{\beta_2}\dots(x-b_j)^{\beta_3}$ (with each $b_i$ distinct)

(these $b_i$'s are exactly the eigenvalues of the matrix that describes the scenario)

We will have then that $x_n = c_1 (b_1)^n + c_2 n(b_1)^n+\dots+c_{\beta_1}n^{\beta_1-1}(b_1)^n+d_1(b_2)^n+d_2n(b_2)^n+\dots+d_{\beta_2}n^{\beta_2-1}(b_2)^n+\dots$

for appropriate values $c_1,c_2,\dots,d_1,d_2,\dots$ that we solve for using the initial conditions.

Fortunately, most examples you will be asked to solve will only involve two or possibly three terms and so will be much shorter than the full theorem that I just cited.

---

For a similar example to yours consider the equation $x_n = 2x_{n-1}-x_{n-2}$ with the initial conditions $x_0=1$ and $x_1=3$.

We move everything to one side: $x_n-2x_{n-1}+x_{n-2}=0$

We look at our characteristic polynomial: $p(x)=x^2-2x+1=0$. This factors as $p(x)=(x-1)^2$

This tells us that we know that our final closed form should look something like $x_n = c_1(1)^n + c_2 n (1)^n$

Using our initial conditions, we know that $1=x_0=c_1(1)^0 + c_2\cdot 0 (1)^0 = c_1$, so $c_1=1$ and further that $3=x_1=c_1(1)^1+c_2\cdot 1 (1)^1 = 1+c_2$, so $c_2=2$. We have the closed form $x_n = 1+2n$. Checking the first several values agrees with the result.

---

For your specific problem, your recurrence relation is $x_n = x_{n-1}+2x_{n-2}$.

Moving to one side, we have $x_n - x_{n-1} - 2x_{n-2}=0$ giving the characteristic polynomial $p(x)=x^2-x-2=0$.

Factor this as $p(x)=(x-b_1)(x-b_2)$.

It factors as $p(x)=(x-2)(x+1)$

You will have then that $x_n = c_1 (b_1)^n + c_2 (b_2)^n$ if $b_1\neq b_2$ or you would have $x_n = c_1 (b_1)^n + c_2 n(b_2)^n$ if $b_1=b_2$.

So it will be of the form $x_n = c_1 2^n + c_2 (-1)^n$

Using this equation, you can then use your initial conditions to make a system of two equations with two unknowns (namely $c_1$ and $c_2$) and solve for them using your favorite method.

We set up the system of equations $\begin{cases} 4=x_0=c_1(2)^0+c_2(-1)^0\\-1=x_1=c_1(2)^1+c_2(-1)^1\end{cases}$ and solve for $c_1$ and $c_2$.

Answer 2

You have to write the characteristic equation to find a basis $(r_1^n,r_2^n)$ of the vector space of solutions to the linear recurrence, then choose the coefficients $\alpha, \beta$ in $\alpha r_1^n+\beta r_2^n\;$ so that it satisfies the initial conditions.