## On Fibonacci-style Sequences continued

In my previous post on Fibonacci-style sequences, I gave the formulae for the closed form

$a_n = p \cdot r^n + q \cdot s^n$

given the recurrence values $a_0, a_1, b, c$ where

$a_{n+2} = b \cdot a_{n} + c \cdot a_{n+1}$

but I did not show that the formula is valid. I do that here.

In that previous post, the closed form was derived from its applications to $n = 0, 1, 2$.

We need to demonstrate that the formula continues to be valid for other values of n.

There, we showed that

$b = - r s$

$c = r + s$

We proceed by induction.

Consider two cases to be valid (as inductive hypotheses):

$a_{n-1} = p \cdot r^{n-1} + q \cdot s^{n-1}$

$a_{n} = p \cdot r^{n} + q \cdot s^{n}$

Now

$a_{n+1} = b \cdot a_{n-1} + c \cdot a_{n}$

${} = (- r s) (p \cdot r^{n-1} + q \cdot s^{n-1}) + (r + s) (p \cdot r^{n} + q \cdot s^{n})$

${} = {} - r s p \cdot r^{n-1} - r s q \cdot s^{n-1}$

${} + r p \cdot r^{n} + r q \cdot s^{n} + s p \cdot r^{n} + s q \cdot s^{n}$

${} = {} - s p \cdot r^{n} - r q \cdot s^{n}$

${} + p \cdot r^{n+1} + r q \cdot s^{n} + s p \cdot r^{n} + q \cdot s^{n+1}$

${} = p \cdot r^{n+1} + q \cdot s^{n+1}$

We have at least two base cases available. Hence by induction, the formula holds for all n.