How to turn the recurrence $a_n=2a_{n−1}−a_{n−2}$, with $a_0=−1$ and $a_1=1$ into a quadratic, to find the closed form?

Question

I am having trouble understanding how to turn the recurrence into a quadratic equation. What principles are involved, rules etc.?

Answer 1

Suppose we have:

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

What the recurrence relation tells you is that too get to the next term you multiply by three. What happens when you multiply by $3$ more than once? we get powers of $3$. Thus the solution which you may check works is:

$$a_n=a_03^n$$

Now let's look at your equation:

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

You may think that something similar is happening here, as if we discard $a_{n-2}$ we get pretty much the same problem. So you may guess the solution to be $a_n=cr^n$ like we saw earlier. Substitute this back into the original equation we have:

$$cr^n=2cr^{n-1}-cr^{n-2}$$

We want too find an $r$ such that this equality will hold for all $n$. Obviously $0$ is a solution. But if we divide by $cr^n$ we get:

$$r^2=2r-1$$

$$r^2-2r+1=0$$

And we call this a characteristic equation.

From this you see,

$$(r-1)^2=0$$

And thus $r=1$, and thus you may guess that the solutions are of the form;

$$a_n=c(1)^n=c$$

But then you notice something given two initial conditions $a_0$ and $a_1$, this might not be true in the case $a_0 \neq a_1$.

Because our characteristic equation had two repeated roots one other solution is:

$$a_n=c_2n(1)^n$$

Again you may check this works.You may check that a linear combination of these particular solutions we came up with is also a solution :

$$a_n=k_0n(1)^n+k_1(1)^n$$

If it was the case that we had all of our roots for our characteristic equation different. It would be straight forward to check that a linear combination of all possible $cr^n$ would also be a solution. In other worlds what I'm trying to say is that if $c_0(r_0)^n, c_1(r_1)^n,..c_i(r_i)^n$ are all solutions (where at the moment we are keeping $c_0,c_1,...c_i$ arbitrary and not worrying about fulfilling initial conditions) it is straight forward to check:

$c_0(r_0)^n+c_1(r_1)^n...+c_i(r_i)^n$

Is also a solution because:

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

If $a_n=f_i(n)$ is a solution. Adding all these equations gives another solution:

$$a_{n0}+...a_{ni}=\left(2c_0(r_0)^{n-1}-c_0(r_0)^{n-2} \right)+\cdots \left(2c_i(r_1)^{n-1}-c_i(r_1)^{n-2} \right)=2(a_{n0}+\cdots a_{ni})-(a_{n0}+\cdots a_{ni})=0+\cdots 0=0$$

Answer 2

Note that:

$$a_n=2a_{n-1}-a_{n-2}\iff a_n-a_{n-1}=a_{n-1}-a_{n-2}$$

So what you're saying is that the difference between two consecutive terms is constant.

Answer 3

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

yields the characteristic equation

$x^2 - 2 x + 1 = 0$

as each successive power describes the successive recursion level. You simply replace each element by a power of $x$, where the power is the same as the index. Thus:

• $a_n \rightarrow x^n$
• $a_{n-1} \rightarrow x^{n-1}$
• $a_{n-2} \rightarrow x^{n-2}$

and then divide out the constant factor (here, $x^{n-2}$).

This equation has solution $x \rightarrow 1$. Thus the growth is linear.

Answer 4

What you are probably talking about is how to get the "characteristic polynomial" (also known as the "auxiliary polynomial") associated to the recurrence relation. I can explain the solution using the full power of linear algebra, but I keep to elementary terminology.

There are a few facts which are important for obtaining a solution. Let's ignore the initial conditions for now. Fact 1: multiplying a solution by a constant yields another solution to the linear recurrence. Fact 2: adding two solutions together yields another solution to the linear recurrence. What we will do with these is come up with a pair of solutions to the linear recurrence, and then add together some scaled copies of them to achieve the initial condition.

Fact 3: (homogeneous) linear recurrence relations have some solution of the form $a_n=c^n$ for some $c$. Let's check: $a_n-2a_{n-1}+a_{n-2}=0$ with this supposed solution would imply $c^n-2c^{n-1}+c^{n-2}=0$, and so by factoring, $(c^2-2c+1)c^{n-2}=0$. Because $c^{n-2}$ is guaranteed nonzero at $n=2$, we have $c^2-2c+1=0$. This is the quadratic you are likely asking about.

Since this polynomial factors as $(c-1)^2$, then $c=1$ is a root with multiplicity two. Hence, we have a solution $a_n=1^n=1$.

Fact 4: when multiplicity occurs, there is another solution of the form $a_n=tc^n$. With $c=1$, this is then $a_n=t$. (I'm omitting an explanation of this.)

Together, we have solutions of the form $a_n=d_1+d_2t$, for some constants $d_1,d_2$. It is a simple matter of substituting $n=0$ and $n=1$ to get a system of two equations, two unknowns, which we may solve for $d_1$ and $d_2$.

Answer 5

You can write the recurrence with matices:

$$ \begin{pmatrix} a_{n-1} \\ a_{n} \\ \end{pmatrix} = \begin{pmatrix} 0 & 1 \\ -1 & 2 \\ \end{pmatrix} \begin{pmatrix} a_{n-2} \\ a_{n-1} \\ \end{pmatrix} $$

Then,

$$ \begin{pmatrix} a_{n-1} \\ a_{n} \\ \end{pmatrix} = \begin{pmatrix} 0 & 1 \\ -1 & 2 \\ \end{pmatrix}^{n-1} \begin{pmatrix} -1 \\ 1 \\ \end{pmatrix} $$

You can Jordan-decompose the matrix in the power as $M = S J S^{-1}$

$$ \begin{pmatrix} 0 & 1 \\ -1 & 2 \\ \end{pmatrix} = \begin{pmatrix} 1 & -1 \\ 1 & 0 \\ \end{pmatrix} \begin{pmatrix} 1 & 1 \\ 0 & 1 \\ \end{pmatrix} \begin{pmatrix} 0 & 1 \\ -1 & 1 \\ \end{pmatrix} $$

To do that manually, you can use the characteristic polynomial, which probably is what you meant with quadratic equation.

$$ \det(M - \lambda \mathbb{1}) = \begin{vmatrix} -\lambda & 1 \\ -1 & 2-\lambda \\ \end{vmatrix} = \lambda^2 -2 \lambda + 1 = (\lambda^2 - 1)^2 = 0 $$

That means that there is only the eigenvalue $\lambda = 1$. Then you find eigenvectors and etcetera. Probably there is some answer which already explains how to do the decomposition in detail.

Once you have the decomposition, it's easy to see that

$$ \begin{pmatrix} 1 & 1 \\ 0 & 1 \\ \end{pmatrix}^{n-1} = \begin{pmatrix} 1 & n-1 \\ 0 & 1 \\ \end{pmatrix} $$

Therefore,

$$ \begin{pmatrix} 0 & 1 \\ -1 & 2 \\ \end{pmatrix}^{n-1} = \begin{pmatrix} 1 & -1 \\ 1 & 0 \\ \end{pmatrix} \begin{pmatrix} 1 & n-1 \\ 0 & 1 \\ \end{pmatrix} \begin{pmatrix} 0 & 1 \\ -1 & 1 \\ \end{pmatrix} $$

And finally,

$$ \begin{pmatrix} a_{n-1} \\ a_{n} \\ \end{pmatrix} = \begin{pmatrix} 1 & -1 \\ 1 & 0 \\ \end{pmatrix} \begin{pmatrix} 1 & n-1 \\ 0 & 1 \\ \end{pmatrix} \begin{pmatrix} 0 & 1 \\ -1 & 1 \\ \end{pmatrix} \begin{pmatrix} -1 \\ 1 \\ \end{pmatrix} = \begin{pmatrix} 2n-3 \\ 2n-1 \\ \end{pmatrix} $$

The general term is

$$a_n = 2n-1$$

Answer 6

Reference: For proofs, look up Linear Homogeneous Difference Equations OR Linear Recurrence Equations.

For a recurrence $a_{n+M}-\sum_{j=0}^{M-1}aB_ja_{n+j}=0$, with $M>0$ and constants $B_0,...,B_{M-1}$ with $B_0\ne 0,$ consider the polynomial $p(x)=x^M-\sum_{j=0}^{M-1}B_jx^j.$ Factor it : $p(x)=\prod_{i=1}^k(x-y_i)^{d_i}$, where $\{y_i: 1\leq i\leq k\}$ is the set of $k$ distinct real or complex zeros of $p(x),$ and each $d_1\in N.$ Every solution of the recurrence is of the form $a_n=\sum_{i=1}^k y_i^n q_i(n)$ where each $q_i$ is a polynomial of degree at most $d_i-1.$(A polynomial of degree $0$ is a constant.) Given the values $a_j$ for $0\leq j\leq r-1$ uniquely determines all the $q_i.$

In your Q, $ p(x)=x^2-2x+1=(x-1)^2,$ so $k=1$ and $\{y_i: 1\leq i\leq k\}=\{y_1\}=1$, and $d_1=2.$ So the solution is $a_n=Sn+T$ with constant $S, T$ such that $a_0=-1$ and $a_1=1.$