# Strong induction. Fibonacci numbers

Using Strong Induction, prove that the (n + 3)-rd Fibonacci number can be computed as 1 plus the sum of the first n + 1 Fibonacci numbers (remember n includes 0). so it has to be proven by Strong Induction with the Inductive Hypothesis applied twice . . . twice because of the nature of the two-term recurrence.

Here I'm confused. I know how to use simple induction.

But I have to use strong induction.

The inductive hypothesis will be like

For arbitrary k ∈ N, ∀j ∈ N, 1 ≤ j ≤ k, S(j) and the inductive step should be like (∀j ∈ N, 1 ≤ j ≤ k, S(j)) → S(k + 1) then??? Examples can be n =5, sum of first 5 fibonacci numbers are 7 + 1 = 8. There is a fibonacci number 8 which is (5+3). (n+3)rd fibonacci number = F(n + 2)because n = F(n-1)

• The specific result you are referring to can be proven using regular induction. You could of course phrase it using strong induction, but you probably won't use anything more than $S(k)$ to prove $S(k+1)$. As for a hint, remember that $f_{n}+f_{n+1}=f_{n+2}$. – JMoravitz Oct 30 '18 at 1:43
• This tutorial explains how to typeset mathematics on this site. – N. F. Taussig Oct 30 '18 at 10:48