Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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.

share|improve this question
    
interesting question –  dato datuashvili Sep 25 '11 at 9:08
add comment

5 Answers

up vote 5 down vote accepted

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$.

share|improve this answer
add comment

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 $$

share|improve this answer
add comment

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$.

share|improve this answer
add comment

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

share|improve this answer
    
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
add comment

for general,solution of this recurrence relation is given by

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

example is here enter image description here

share|improve this answer
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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