Recurrence relation - second order

55 Views Asked by At

I read this book, and I do not understand one thing in proof.

The theorem is:

Let $s_1, s_2$ be number so that quadratic equation $x^2-s_1x-s_2 = 0$ has exactly one root, $r \neq 0.$

Then every solution to the recurrence relation $$a_n = s_1a_{n-1} + s_2a_{n-2}$$ is of the form $$a_n = c_1r^n+c_2nr^n$$

Proof: Since the quadratic equation has a single (repeated) root, it must be of the form $(x-r)(x-r)=x^2-2rx+r^2$. Thus the recurrence must be $a_n = 2ra_{n-1}-r^na_{n-2}$.

And I stop here, because I do not understand the last sentence (in bold).

Thank you for explenation.

1

There are 1 best solutions below

1
On BEST ANSWER

It could be either a typo in your post, on in the book, but the right expression is $a_n = 2r a_{n - 1} - r^{\color{red}{2}} a_{n - 2}$. To show the statement in bold you can try this way. Imagine the recurrence

$$ a_n = 2r a_{n - 1} - r^{\color{red}{2}} a_{n - 2} \tag{1} $$

and consider a solution of the form $a_n = c x^n$, if you replace this in Eqn (1) you get

$$ \require{cancel} \cancel{c} x^n = 2 r (\cancel{c} x^{n - 1}) - r^2 (\cancel{c} x^{n - 2}) $$

Multiply everything by $x^{2-n}$, you will get

$$ x^2 = 2r x - r^2 ~~~\Leftrightarrow (x-r)^2 = 0 \tag{2} $$

Or equivalently, an equation of the form $x^2 -2rx + r^2 = 0$ implies $a_n = 2r a_{n - 1} - r^{\color{red}{2}} a_{n - 2}$