In my previous post on Fibonacci-style sequences, I gave the formulae for the closed form
given the recurrence values where
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 .
We need to demonstrate that the formula continues to be valid for other values of n.
There, we showed that
We proceed by induction.
Consider two cases to be valid (as inductive hypotheses):
We have at least two base cases available. Hence by induction, the formula holds for all n.