Fibonacci Sequence Proof

Every positive integer is the sum of distinct nonconsecutive Fibonacci Numbers.

• We know that the recursive formula for the sequence is   f_n + 1  =  f_n  +  f_n - 1  with  f₁  =  f₂  =  1.
• We know that the first 6 Fibonacci numbers are 1, 1, 2, 3, 5, 8

Using Mathematical Strong Induction:

1. The statement is clearly true for n = 1, 2, and 3 since 1 = f₁, 2 = f₃, and 3 = f₄, which we may consider as single term sums.
2. Suppose that the statement is true for all n <= m. We will prove that the statement is true for n = m+1.
   
   If m+1 = f_t for some t, then it is trivially correct. In other cases we find the t such that f_t < m+1 < f_{t+1}.
   
   Let q = m+1 - f_t ; then we can write q as sum of nonconsecutive Fibonacci numbers according to the induction hypothesis. We also note that this sum does not contain f_{t-1} because:
   
   q = m + 1 - f_t < f_{t+1} - f_t = f_{t-1}
   
   So if we add f_t to the sum of nonconsecutive Fibonacci numbers for q, we have such a sum for m+1 as well. And the statement is true for n = m+1.