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)