0

I am having some problem solving sequences in the form $x_k$, I have some notes about it however they skip over a lot of steps and I was hoping someone could help me clarify them!

Basically I start with the sequence:

$$x_{k+1}-4x_k+3x_{k-1}=0$$

Then what they say is to look for solutions of the form $x_k =l^k$ ,where $l$ is a constant to be determined.

They then say: Substituting in to the equation and cancelling $l^{k-1}$ we discover $l$ must satisfy the quadratic equation:

$l^2-4l+3=0$

But how on earth do they get this with that substitution? Could anyone shed any light on this? Thank you :)

  • Note for other readers: the quadratic equation is often called the 'characteristic polynomial' of the recurrence relation. – Toby Mak Oct 27 '19 at 12:49

2 Answers2

1

If $x_k=l^k$ and $x_{k-1}=l^{k-1}$ for some particular $k$ then you can say $x_{k+1}-4l^k+3l^{k-1}=0$ , i.e. you can say $x_{k+1}=4l^k-3l^{k-1}=l^{k-1}(4l-3)$

If you also know $l^2-4l+3=0$, i.e. $l^2=4l-3$, then you can then say $x_{k+1}=l^{k+1}$

It is then a simple induction to say that any $l$ satisfying $l^2-4l+3=0$ gives $x_k=l^k$ as a solution to $x_{k+1}-4x_k+3x_{k-1}=0$

You can go further:

  • with any $l$ satisfying $l^2-4l+3=0$ you have $x_k=al^k$ as a solution to $x_{k+1}-4x_k+3x_{k-1}=0$ for any constant $a$

  • with distinct $l_1, l_2$ satisfying $l^2-4l+3=0$ you have $x_k=a_1^{\,}l_1^k+a_2^{\,}l_2^k$ as a solution to $x_{k+1}-4x_k+3x_{k-1}=0$ for any constants $a_1,a_2$

  • $x_{k+1}-4x_k+3x_{k-1}=0$, i.e. $x_{k+1}=4x_k+3x_{k-1}$ has two degrees of freedom as knowing $x_0$ and $x_1$ determines $x_k$ for all positive integer $k$. The same is true for $x_k=a_1^{\,}l_1^k+a_2^{\,}l_2^k$ when $l_1$ and $l_2$ are distinct. So there can be no other solutions

Here you have the solutions to $l^2-4l+3=0$ being $1$ and $3$ so you have the particular solutions $x_k=1$ and $x_k=3^k$, giving $x_k=a_1^{\,}+a_2^{\,}3^k$ as the general form satisfying $x_{k+1}-4x_k+3x_{k-1}=0$

Henry
  • 157,058
0

If $x_k=l^k$, then the equality $x_{k+1}-4x_k+3x_{k-1}$ becomes $l^{k+1}-4l^k+3l^{k-1}=0$. Dividing this by $l^{k-1}$, you get that $l^2-4l+3=0$.

José Carlos Santos
  • 427,504