1

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?

2 Answers2

2

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.

André Nicolas
  • 507,029
  • 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? –  Oct 25 '14 at 17:29
  • 1
    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. – André Nicolas Oct 25 '14 at 17:33
  • And why is the set of solutions a 2-dim vector space? –  Oct 25 '14 at 17:33
  • 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. – André Nicolas Oct 25 '14 at 17:40
  • 1
    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 –  Oct 25 '14 at 17:50
2

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