# Linear homogeneous difference equation with constant coefficients

If I have for instance the equation:

$0 = 2x_{n} - 3x_{n+1}+x_{n+2}$

Then the solution space is a linear vector space of dimension 2.

Someone who can explain why this is true? My teacher has written something about a dimension argument.

-
interesting question – dato datuashvili Sep 25 '11 at 9:08

The set of solutions is a vector space because the null sequence is a solution and because, if $x=(x_n)_{n\ge0}$ and $y=(y_n)_{n\ge0}$ are solutions, then $x+y=(x_n+y_n)_{n\ge0}$ and $ax=(ax_n)_{n\ge0}$ are solutions as well, for every scalar $a$.

This vector space is a plane because there exists two solutions, say $x^0=(x^0_n)_{n\ge0}$ and $x^1=(x^1_n)_{n\ge0}$ which are not proportional and such that every solution $x=(x_n)_{n\ge0}$ is a linear combination of these.

For example, one can define $x^0$ by the initial condition $(x^0_0,x^0_1)=(1,0)$ and $x^1$ by the initial condition $(x^1_0,x^1_1)=(0,1)$. This defines uniquely $x^0$ and $x^1$ because $x^0$ and $x^1$ are solutions of the recursion. Every solution $x=(x_n)_{n\ge0}$ is such that $x=x_0x^0+x_1x^1$, in other words, such that for every $n\ge0$, $x_n=x_0x^0_n+x_1x^1_n$. And finally, $x^0$ and $x^1$ are linearly independent because the two first terms of the sequence $ax^0+bx^1$ are $a$ and $b$, hence if $ax^0+bx^1=0$, then $a=b=0$.

-

Because the sequence is completely determined by its two starting values. But since they can be taken to be anything, this vector space is isomorphic to $\mathbb{R}^2$.

-

You can rewrite the equation as follows :

$$\pmatrix{x_{n+1}\\x_{n+2}} = \pmatrix{0 &1\\-2 &3}\pmatrix{x_{n}\\x_{n+1}}$$ with calling new variables for help, it is simply $$X_{n+1} = \pmatrix{0 &1\\-2 &3} X_n$$

The vector is usually called the state vector and describes the evolution of an autonomous system (in this case it can be considered as a discrete linear time-invariant system). Regardless of whatever causing the increase from $n$ to $n+1$, you can always start from any point in the space, in other words, you can set $$X_0 = \pmatrix{x_0\\x_1} = \pmatrix{a\\b}$$ with arbitrary $a,b$. This means that any point in $\mathbb{R^2}$ can be a point on a admissible trajectory of $x$. Moreover you can start from any point and go back in terms of negative $n$, thus, travel back in time, once you know the rule of evolution of $x$ :p

The closed form solution is simple to obtain: $$X_n = \pmatrix{0 &1\\-2 &3} X_{n-1}=\pmatrix{0 &1\\-2 &3} ^2 X_{n-2} = \pmatrix{0 &1\\-2 &3} ^nX_0$$

-

There is a closed formula to solve such equations:

Let $b,c,x_0,x_1$ be complex numbers, define $x_2,x_3,\dots$ by $$x_{n+2}+b\,x_{n+1}+c\,x_n=0,$$ let $u$ and $v$ be the solutions of $z^2+b\,z+c=0$, and put $$s_n:=u^n+u^{n-1}\,v+u^{n-2}\,v^2+\cdots+v^n$$ for $n\ge0$, that is $$s_0:=1,\quad s_1:=u+v,\quad s_1:=u^2+uv+v^2,\dots$$ In particular $$s_n=\frac{u^{n+1}-v^{n+1}}{u-v}\quad\text{if}\quad u\not=v$$ and $$s_n=(n+1)\ u^n\quad\text{if}\quad u=v.$$ Then we have

$$x_n=s_{n-1}\ x_1-s_1\ s_{n-1}\ x_0+s_n\ x_0$$

for $n\ge1$.

More generally there is a (slightly less explicit) closed formula to solve equations of the form $$x_{n+k}+a_{k-1}\ x_{n+k-1}+\cdots+a_0\ x_n=b_n$$ in terms of $x_0,x_1,\dots,x_{k-1}$. If anybody is interested I'd be happy to give it.

EDIT. Thank you to Didier Piau for his interest! [Added: ... and for pointing out typos in such a funny way!] The following is a variation around the almost obscene and well known fact that a single integration suffices to solve the ODE $y^{(n)}=f$.

Let $D$ be a degree $q\ge1$ monic polynomial; let $\mathbb C^\mathbb N$ be the set of sequences of complex numbers; let $\Delta$ be the shift operator mapping the sequence $x$ in $\mathbb C^\mathbb N$ to the sequence $\Delta x$ in $\mathbb C^\mathbb N$ defined by $(\Delta x)_t=x_{t+1}$; let $f$ be in $\mathbb C^\mathbb N$; let $c_0,\dots,c_{q-1}$ be complex numbers; let $y$ be the unique element of $\mathbb C^\mathbb N$ satisfying $$D(\Delta)\,y=f,\quad y_n=c_n\text{ for all }n<q.$$

We'll give

• a formula for $y$ in terms of remainder of the long division of $X^t$ by $D$, and

• a formula for the remainder of any long division of a polynomial $P$ by a nonzero polynomial $D$.

For $(n,t)$ in $\mathbb N^2$ denote by $g_n(t)$ the coefficient of $X^n$ in the remainder of the long division of $X^t$ by $D$. Here is the first formula:

If $t\ge q$ then $\displaystyle y_t=\sum_{n<q}\,c_n\,g_n(t)+\sum_{k<t}\,g_{q-1}(t-1-k)\,f_k.$

Proof of the first formula. Introduce the sequence of vectors $v_t:=(y_t,\dots,y_{t+q-1})$. We have $$v_{t+1}=B\,v_t+f_t\,e_q,\quad v_0=c,$$ where $e_q$ is the last vector of the canonical basis of $\mathbb C^q$, and $B$ is the transpose of the $q$ by $q$ matrix $A$ characterized by $$j<q\Rightarrow A\,e_j=e_{j+1},\quad A\,e_q=-a_0\,e_1-\dots-a_{q-1}\,e_q.$$

Hence $$v_t=B^t c+f_0\,B^{t-1}\,e_q+f_1\,B^{t-2}\,e_q+\dots +f_{t-1}\,e_q.$$ It suffices then to take the first component of the left and right hand sides, and to note the following fact:

Let $D$ be a degree $q\ge1$ polynomial, let $P$ be a polynomial, and $$b_{q-1}\,X^{q-1}+\dots+b_0$$ the remainder of the long division of $P$ by $D$. Then we have $$P(A)\,e_1=b_0\,e_1+\dots+b_{q-1}\,e_q.$$ QED

(2) Let $R$ be the remainder of the long division of a polynomial $P$ by a nonzero polynomial $D$. Here $P$ and $D$ are in $\mathbb C[X]$. We may assume $$D(X)=\big(X-a_1\big)^{m_1}\cdots\big(X-a_r\big)^{m_r},$$ where the $a_j$ are distinct and the $m_j$ positive. For any rational fraction $f(X)\in\mathbb C(X)$ defined at $a_j$, let $T_j(f(X))$ be the degree at most $m_j-1$ Taylor approximation of $f(X)$ at $X=a_j$. The second formula is

$\displaystyle R(X)=\sum_{j=1}^r\,T_j\left(P(X)\,\frac{(X-a_j)^{m_j}}{D(X)}\right) \frac{D(X)}{(X-a_j)^{m_j}}\quad.$

If $m_j=1$ for all $j$, we get Lagrange's Interpolation Formula $$R(X)=\sum_{j=1}^r\,P(a_j)\,\prod_{k\not=j}\,\frac{X-a_k}{a_j-a_k}\quad.$$ Proof of the second formula. We solve the congruences $$R\equiv P\bmod(X-a_j)^{m_j}$$ as explained in this answer. QED

-
Pierre-Yves, please do (give it)... :-) – Did Sep 27 '11 at 6:46
Wow. Not sure this stuff is as well known as you say it is. Nice addition. – Did Sep 27 '11 at 16:20
@Didier: Thanks again! I'm realizing that I made your joke completely ununderstandable! Sorry... – Pierre-Yves Gaillard Sep 27 '11 at 16:28
P-Y, there is nothing here to feel sorry for, your almost obscene and well known fact made my day. – Did Sep 27 '11 at 16:47
Just to make things understandable again: I had written "well know" instead of "well known", and Didier wrote "Not sure this stuff is as well know[n] as you say it is". – Pierre-Yves Gaillard Sep 27 '11 at 16:52

for general,solution of this recurrence relation is given by

x(n)=c2*2^n+c1


example is here

-