Proof: if $a_n=nx_0^n$ is a solution of recurrence relation then $x_0$ has multiplicity 2.

61 Views Asked by At

I have to prove that if $a_n=nx_0^n$ is a solution of $$a_n=c_1a_{n-1}+c_2a_{n-2}+c_3a_{n-3}, n\geq 3,$$ then $x_0$ is a multiple root of the characteristic equation $$x^3-c_1x^2-c_2x-c_3=(x-x_0)(x-x_1)(x-x_2)=0,$$ so $x_1$ or $x_2$ (or both) has to be equal to $x_0$.

I know how to proof the opposite direction, however I'm stuck with this. How can I start the proof?

1

There are 1 best solutions below

0
On BEST ANSWER

Substituting $a_n=n x_0^n$ into the recurrence:

$$n x_0^n=c_1(n-1)x_0^{n-1}+c_2(n-2)x_0^{n-2}+c_3(n-3)x_0^{n-3}$$

Dividing by $x_0^{n-3}$ (on the implicit assumption that $x_0 \ne 0$):

$$n x_0^3=c_1(n-1)x_0^2+c_2(n-2)x_0+c_3(n-3) \tag{1}$$

Writing $(1)$ for $n-1$:

$$(n-1) x_0^3=c_1(n-2)x_0^2+c_2(n-3)x_0+c_3(n-4) \tag{2}$$

Subtracting $(1)-(2)\,$:

$$x_0^3=c_1 x_0^2+c_2 x_0+c_3 \tag{3}$$

$(3)$ proves that $x_0$ is a root of the characteristic polynomial $P(x)=x^3-c_1x^2-c_2x-c_3\,$.

Then, writing the recurrence for $n=3\,$:

$$ 3x_0^3=2c_1x_0^2+c_2 x_0$$

Dividing by $x_0\,$:

$$ 3x_0^2=2c_1x_0+c_2 \tag{4}$$

$(4)$ proves that $x_0$ is a root of $P'(x)=3x^2-2c_1x^2-c_2\,$, therefore $x_0$ is a common root of $P(x)$ and $P'(x)$ and, as such, it has multiplicity at least $2\,$.