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.
 A: 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$.
A: 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$. 
A: 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
$$
A: 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 
A: for  general,solution of this  recurrence relation is given by
x(n)=c2*2^n+c1

example is here

