1

I encountered the following recurrence relation $2x_n-3x_{n-1}+x_{n-2}=0$ with $x_0=1$ $x_1=1$.I did not have any idea how to go about this.However, google pointed me to page 18 of Herbert Wilf's Algorithms and Complexity where he substituted $x_n=\alpha^n$, found a quadratic equation and found a solution to the Fibonnaci sequence using the roots of the quadratic equation.Here is the image. It left me with two questions:

1) Why should a general term of the recurrence relation $x_{n+1}=ax_{n}+bx_{n-1}$,($n\ge 1$, $x_0,x_1$ given) be of the form $x_n=\alpha^n$ for some alpha ?

2) Why should $x_n$ be a linear combination of the roots of the the quadratic equation obtained by substituting $x_n=\alpha^n$?

User10263
  • 37
  • Observe $a\alpha^n+b\alpha^{n-1}=\alpha^{n-1}(a\alpha+b)=\alpha^{n+1}$ for $a\alpha+b=\alpha^2$. – obataku Apr 29 '13 at 06:57
  • 1
    The reason the linear combination works is that if $X_n$ and $X_n'$ both satisfy our relation then so does $X_n + X_n'$. Similarly, if $X_n$ satisfies our relationship, so does $kX_n$ for some constant $k$... these are called linear recurrence relationships for a reason. – obataku Apr 29 '13 at 07:02
  • @SMu: take a look also at my answer here: http://math.stackexchange.com/questions/154667/how-to-find-the-closed-form-formula-for-this-recurrence-relation/154696#154696 – Dennis Gulko Apr 29 '13 at 07:36
  • Your questions are contradictory. The general term of the degree $2$ recurrence relation is not given by $x_n=\alpha^n$; if it were, then the would be no linear combination to form in point 2) (which is also not formulated cleanly: the linear combination is not of roots, but of solutions associated to those roots). The whole idea is that by dropping the initial conditions one gets a more general problem, which does allow solutions of the form $x_n=\alpha^n$; then by forming linear combination one can get back to the original problem, with the initial values as given. – Marc van Leeuwen Apr 29 '13 at 09:01

2 Answers2

4

Consider a second-order linear difference equation with constant coefficients $$x_{n+1}=ax_n+bx_{n-1}$$ for some $a,b$ given $x_0,x_1$. Now, recognize that if $X_n$ is a solution to our equation, i.e. $X_{n+1}=aX_n+bX_{n-1}$, then so is $kX_n$ for any constant $k$: $$kX_{n+1}=akX_n+bkX_n=k(aX_n+bX_{n-1})$$

Similarly, if $X_n$ and $Y_n$ are solutions to our equation, i.e. $X_{n+1}=aX_n+bX_{n-1}$ and $Y_{n+1}=aY_n+bY_{n-1}$, it follows readily from adding these equations that $X_n+Y_n$ is also a solution. $$X_{n+1}+Y_{n+1}=aX_n+bX_{n-1}+aY_n+bY_{n-1}=a(X_n+Y_n)+b(X_{n-1}+Y_{n-1})$$

It follows then that our solutions form a 2-dimensional vector space (all other axioms are trivial; $x_n=0$ is our zero vector, etc.).

We may guess a solution of the form $x_n=\alpha^n$ to yield: $$\begin{align*}\alpha^{n+1}&=a\alpha^n+b\alpha^{n-1}\\&=\alpha^{n-1}(a\alpha+b)\\&\implies\alpha^2-a\alpha-b=0\end{align*}$$ If this quadratic equation has two distinct roots $\alpha_1,\alpha_2$, we have determined two linearly independent solutions -- a fundamental set of solutions, a basis for our vector space. Thus every solution may be written as a linear combination of these solutions i.e. in the form:$$x_n=c_1\alpha_1^n+c_2\alpha_2^n$$

obataku
  • 5,571
3

For a general linear recurrence relation of the form:

$$x_{n+1} = \sum_{k=0}^{N} a_k x_{n-k}\tag{*}$$

In additional to being linear, it is invariant under translation. This means if $(x_n)$ is a solution of $(*)$, so does the sequence $(y_n)$ defined by $y_n = x_{n+1}$.

Just like when you have two commuting Hermitian matrices, you can look for eigen-vectors for both matrices at the same time. Instead of finding solutions for $(*)$ alone, one can look for solutions which are "eigen-vectors" for the translation operation.

i.e. Looking for solution $(x_n)$ satisfies additional constraint:

$$y_n = \alpha x_n \iff x_{n+1} = \alpha x_n \iff x_n \propto \alpha^n$$

achille hui
  • 122,701