Proving $F_{1} - F_{2} + F_{3} - F_{4} + F_{5} ... + F_{2n-1} - F_{2n} = 1 - F_{2n-1}$ Here is what I have so far for proof by induction:
Base case:
Suppose n = 3
$$\sum_{i=1}^{n}(F_{2n-1} - F_{2n}) = 1 - F_{2n-1}$$
$$\sum_{i=1}^{3}(F_{2n-1} - F_{2n}) = 1 - F_{2*3-1}$$
$$F_{1} - F_{2} + F_{3} - F_{4} + F_{5} - F_{6} = 1 - F_{5}$$
$$1 - 1 + 2 - 3 + 5 - 8 = 1 - 5$$
$$-4 = -4$$
Inductive hypothesis:
$$\sum_{i=1}^{k}(F_{2k-1} - F_{2k}) = 1 - F_{2k-1} \forall k \geq 1$$
Inductive step:
$$\textrm{We must prove that} \ \sum_{i=1}^{k+1}(F_{2k+1} - F_{2k+2}) = 1 - F_{2k+1}$$
This is where I get stuck. I am also unsure whether the equation in the inductive step is actually correct or not. I know I have to sub in k+1 for k, but when I try a base case with the new equation to see if it is still true, I can't actually make it work out. I have been at this question for over an hour now so maybe my brain is just fried. Have I been going at this question wrong?
 A: Note that the sum "telescopes" using the Fibonacci recursion $F_{2n}=F_{2n-1}+F_{2n-2}$, so that 
$$
\sum_{i=1}^n(F_{2i-1}-F_{2i})=-\left(\sum_{i=0}^{n-1}F_{2i}\right).
$$
Thus it suffices to show 
$$
\sum_{i=0}^{n-1}F_{2i}=F_{2n-1}-1;
$$
this is much easier to induct with, as if 
$$
F_0+\dots+F_{2n-2}=F_{2n-1}-1,
$$
then 
$$
F_0+\dots+F_{2n-2}+F_{2n}=F_{2n-1}-1+F_{2n}=F_{2n+1}-1
$$
A: Why do you have $n=3$ as your base case? Why not just $n=1$?
Also, make sure to use the running index $i$ as your variable in the formula inside the summation (you are using $n$ and $k$, which is not right!)
So I would do:
Claim: for all $n \ge 1$:
$$\sum_{i=1}^{n}(F_{2i-1}-F_{2i})=1-F_{2n-1}$$
Base: $n=1$
$$F_1-F_2=1-1=1-F_1$$ Check!
Step:
Inductive hypothesis: Suppose that for some arbitrary $k$:
$$\sum_{i=1}^{k}(F_{2i-1}-F_{2i})=1-F_{2k-1}$$
now consider $k+1$:
$$\sum_{i=1}^{k+1}(F_{2i-1}-F_{2i})=$$
$$\sum_{i=1}^{k}(F_{2i-1}-F_{2i})+F_{2(k+1)-1}-F_{2(k+1)}=\text{ (Inductive Hypothesis)}$$
$$1-F_{2k-1}+F_{2k+1}-F_{2k+2}=$$
$$1-F_{2k-1}+F_{2k-1}+F_{2k}-F_{2k}-F_{2k+1}=$$
$$1-F_{2(k+1)-1}$$
Check!
