Fibonnaci Sequence

Question

Prove that $\forall n\epsilon N$ $$F(n+2) = 1 + \sum_{i=0}^n F(i) $$

I know this is strong induction. However I am new to it and not 100% familiar with how it works. The base case is $$ F(0+2) = F(2) = 1$$

and

$$1 +\sum_{i=0}^0 F(i) = 1 $$

Then the Induction Hypothesis is that you assume for arbitrary $k\epsilon N,\forall j \epsilon N, 1 \le j \le k, S(j) $ Then the inductive step is that I must prove the inductive hypothesis implies $S(k+1)$. However I am confused on how to do that part

You don't need "strong" induction. – Angina Seng Oct 29 '18 at 16:59 — Angina Seng, Oct 29 '18 at 16:59

score 1 · Answer 1 · answered Oct 29 '18 at 17:07

1

We know that $F(i) = F(i - 1) + F(i - 2)$ $\forall i>1$

Then, $F( k + 1 + 2) = F(k + 3) = F(k + 2) + F(k + 1)$

Then use the inductive hypotesis to $F(k + 2)$

We have $F(k + 3) =1 + \sum_{i = 0}^{k}F(i) + F(k + 1) = 1 + \sum_{k = 0}^{k+1} F(i)$

answered Oct 29 '18 at 17:07

ZAF

2,618
7
13

Fibonnaci Sequence

1 Answers1