Is the recurrence relation a good way to compute $x_n$ from arbitrary initial values $x_0$ and $x_1$?

Question

Show that the recurrence relation $$x_n=2x_{n-1}+x_{n-2}$$ has a general solution of the form $$x_n=A\lambda^n+B\mu^n.$$ Is the recurrence relation a good way to compute $x_n$ from arbitrary initial values $x_0$ and $x_1$?

Proof: Suppose we are given the following recurrence relation $$x_n=2x_{n-1}+x_{n-2}.$$ We want to show that this relation has a general solution of the form $$x_n=A\lambda^n+B\mu^n.$$

The corresponding characteristic polynomial to the recurrence relation is $$p(\lambda)=\lambda^2-2\lambda-1=0 \iff p(\lambda)=\left(\lambda-(1+\sqrt{2})\right)\left(\lambda-(1-\sqrt{2})\right)=0.$$ Hence the roots of the characteristic polynomial are $\lambda=1+\sqrt{2}$ and $\lambda=1-\sqrt{2}$. Hence the general solution for the relation is $$x_n=A(1+\sqrt{2})^n+B(1-\sqrt{2})^n,$$ where $\lambda=1+\sqrt{2}$ and $\mu=1-\sqrt{2}$.

Where I am stuck is determine whether or not this recurrence relation is a "good" way to compute $x_n$?

Answer 1

Here is what I believe is the best way to compute $x_n$. Note that $$ \begin{bmatrix}2&1\\1&0\end{bmatrix}\begin{bmatrix}x_n\\x_{n-1}\end{bmatrix}=\begin{bmatrix}x_{n+1}\\x_{n}\end{bmatrix} $$ Extending this, $$ \begin{bmatrix}2&1\\1&0\end{bmatrix}^{n-1}\begin{bmatrix}x_1\\x_{0}\end{bmatrix}=\begin{bmatrix}x_{n}\\x_{n-1}\end{bmatrix} $$ This shows that once we have computed $\begin{bmatrix}2&1\\1&0\end{bmatrix}^{n-1}$, then we can compute $x_n$ in constant time.

Fortunately, one can compute the $k^\text{th}$ power of a matrix $M$ using only $O(\log k)$ multiplications, using exponentiation by squaring:

$$M^{2k} = M^k\cdot M^k, \qquad M^{2k+1}=M\cdot M^k\cdot M^k$$

Summarizing, $x_n$ can be computed in $O(\log n)$ arithmetic operations. This is much faster than using naive dynamic programming based on the recurrence relation. Also, only integer arithmetic is involved, so there is no risk of arithmetic errors, as there would be with simply substituting $n$ into the closed form solution. This method generalizes to any homogenous integer linear recurrence of any order.

Answer 2

So your general solution is $x_n = c_1 (1 + \sqrt{2})^n + c_2 (1 - \sqrt{2})^n$. If you pick initial values so that $x_n = (1 - \sqrt{2})^n$ (i.e., $x_0 = 1, x_1 = 1 - \sqrt{2}$), you see that $x_n \to 0$ as $n \to \infty$. Say only your initial values are sligtly off (can't represent $1 - \sqrt{2}$ exactly!), you'll get a solution for a different recurrence $p_n = 2 p_{n - 1} + p_{n - 2}$ with other initial values, the errors $\epsilon_n = x_n - p_n$ satisfy $\epsilon_n = \epsilon_{n - 1} + \epsilon_{n - 2}$ with initial values $\epsilon_0 = 0$, $\epsilon_1$ given. It's general solution is as above, but here $c_1 = \frac{2 + \epsilon_1 \sqrt{2}}{4} > 0$. Thus as $n \to \infty$, $\epsilon_n \to \infty$. The error grows without bound in this case. Errors on the way just make this worse.