1
$\begingroup$

Find general solution of recurrence relation $$ ax_{n+1}+bx_n+cx_{n-1}=0 $$ for two distinct roots $\alpha$ and $\beta$..

My question is: One solution is $y_n=A\alpha^n+B\beta^n$. But how does one show that this is the general solution?

$\endgroup$
2
  • $\begingroup$ Once you fix the first two x with this form, the others are so by the relation. $\endgroup$
    – Chen Jiang
    Commented Oct 25, 2014 at 17:26
  • $\begingroup$ Sorry, do not understand. How do you mean that? $\endgroup$
    – user34632
    Commented Oct 25, 2014 at 17:27

2 Answers 2

Reset to default
2
$\begingroup$

It is basic linear algebra. The set of solutions (functions from the non-negative integers to (say) the reals) of the recurrence is a $2$-dimensional vector space.

It can be shown that $y_n=\alpha^n$ and $y_n=\beta^n$ are linearly independent solutions, and therefore they span the space of solutions.

$\endgroup$
5
  • $\begingroup$ For example $\alpha^n$ is a solution, because $a\alpha^2+b\alpha+c=0$ and so $\alpha^{n-1}\cdot (a\alpha^2+b\alpha+c)=0$, right? $\endgroup$
    – user34632
    Commented Oct 25, 2014 at 17:29
  • 1
    $\begingroup$ Yes, verification that $\alpha^n$ and $\beta^n$ are solutions is as you write. And one is not a multiple of the other, so they are linearly independent. $\endgroup$
    – André Nicolas
    Commented Oct 25, 2014 at 17:33
  • $\begingroup$ And why is the set of solutions a 2-dim vector space? $\endgroup$
    – user34632
    Commented Oct 25, 2014 at 17:33
  • $\begingroup$ Vector space because if $(x_n)$ and $(y_n)$ are solutions, so is $(px_n+qy_n)$. Two dimensional because if $(a_n)$ is a solution that satisfies initial condition $a_0=1$, $a_1=0$, and $(b_n)$ one that satisifies $b_0=0$, $b_1=1$ then every solution is a linear combination of $(a_n)$ and $(b_n)$. This is basically because any solution $c_n$ which is $0$ at $0$ and $1$ is $0$ everywhere. $\endgroup$
    – André Nicolas
    Commented Oct 25, 2014 at 17:40
  • 1
    $\begingroup$ Notice that every solution is entirely known by giving its two first terms so we can construct an isomorphism between the set of solutions and $\Bbb R^2$. See my answer. @math12 $\endgroup$
    – user63181
    Commented Oct 25, 2014 at 17:50
2
$\begingroup$

Let $E_{R_2}$ the set of solutions of the recurrence relation. It's easy to prove that this set is subspace of $\Bbb R^{\Bbb N}$ so let

$$\Phi : E_{R_2}\to \Bbb R^2,\quad (u_n)\mapsto (u_0,u_1)$$

then we see easily that $\Phi$ is an isomorphism of vector spaces hence $$\dim E_{R_2}=2$$

$\endgroup$

You must log in to answer this question.