I am having trouble with the induction step of this proof, any nudges in the right direction or pointers where my reasoning is wrong are greatly appreciated.
I should prove the following equality:
For all $ n, n_1 \in \mathbb N, n_1 \ge 4, F_0 = 1, F_1 = 2, F_n = F_{n-1} + F_{n-2}$ $$ F_{n_1-1} = 2 + \sum_{i=0}^{n_1-3} F_i $$
My work so far:
Base case $ n_1 = 4 $: $$F_3 = 2 + \sum_{i=0}^{1} F_i = 2 + F_0 + F_1 $$ $$= 2 + 1 + 2$$ $$=5$$
IA: Assume for particular $k \in \mathbb N, k \ge 4$ $$F_{k-1} = 2 + \sum_{i+0}^{k-3} F_i$$
IS: Here I should show that this applies for $k+1$. $$ F_{(k+1)-1} = 2 + \sum_{i=0}^{(k+1)-3} F_i $$ $$=2 + \sum_{i=0}^{k-2} F_i$$ And this is where I'm a bit stuck. I think I need to show that this is the same thing as the sum for k, plus a bit...right? And that "bit" should basically be enough to get us to the next term in the Fibonacci sequence?
Because we defined the nth Fibonacci term as $F_n = F_{n-1} + F_{n-2}$, I broke up the sum for $k+1$ like so: $$(2 + \sum_{i = 0}^{((k+1)-1) - 3}F_i) + (2 + \sum_{i=0}^{((k+1)-2)-3}F_i)$$ $$= (2 + \sum_{i = 0}^{k-3}F_i) + (2 + \sum_{i=0}^{k-4}F_i)$$ And then I can see that the first operand is actually the sum for $k$. But here I feel stuck. How do I show that the second operand is enough to get us to the term after $F_{k-1}$?
