# Confusion with sequences

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!

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

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

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

• Do you not miss a solution on one side though? like $l^{k-1}=0$? – user635953 Oct 27 '19 at 12:44
• Yes, but since it is trivial that the null sequence satisfies that recurrence relation, I saw no problem in assuming that $l\neq0$. – José Carlos Santos Oct 27 '19 at 12:46