Show that where defined as
1. Guess at a solution
Let’s start off by enumerating these terms
Since the problem asks us to prove that , let’s just see what we get left over after dividing out
Oh my god! That’s the fibonacci sequence defined by
This naturally suggests that
2. Show that
We can prove this inductive on consecutive naturals . Informally, We form the inductive steps through the regrouping of the terms of as
Proof by induction
We need to prove the proposition holds for all .
As the base cases, we observe that and hence .
This concludes our proof that .
3. Show that
Since is successively defined in terms of addition on the naturals, which closes the naturals, then it must be the case that for any , . Because , then trivially . This concludes the proof that .