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.

  • $\begingroup$ interesting question $\endgroup$ – 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

  • $\begingroup$ Pierre-Yves, please do (give it)... :-) $\endgroup$ – Did Sep 27 '11 at 6:46
  • $\begingroup$ Wow. Not sure this stuff is as well known as you say it is. Nice addition. $\endgroup$ – Did Sep 27 '11 at 16:20
  • $\begingroup$ @Didier: Thanks again! I'm realizing that I made your joke completely ununderstandable! Sorry... $\endgroup$ – Pierre-Yves Gaillard Sep 27 '11 at 16:28
  • $\begingroup$ P-Y, there is nothing here to feel sorry for, your almost obscene and well known fact made my day. $\endgroup$ – Did Sep 27 '11 at 16:47
  • $\begingroup$ 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". $\endgroup$ – Pierre-Yves Gaillard Sep 27 '11 at 16:52

for general,solution of this recurrence relation is given by


example is here enter image description here


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.