\problemdata
{strong induction}
{Velleman}

\begin{problem}
% strong induction
% source: Velleman section 6.4, problem 5

Let $F_n$ be the $n$th Fibonacci number, for all $n \in \mathbb{N}$.
Recall that the Fibonacci numbers are defined recursively as follows:
$F_0 = 0$, $F_1 = 1$, and $F_n = F_{n-1} + F_{n-2}$, for all $n \in
\mathbb{N}, n \geq 2$.

\begin{problemparts}

\problempart 

Prove that for all $n \in \mathbb{N}$, $\sum_{i = 0}^{n} F_i =
F_{n + 2} - 1$.

\solution{
 Let $P(n): \sum_{i = 0}^{n} F_i = F_{n + 2} - 1$.

}
\problempart

Find a formula for $\sum_{i = 0}^{n} F_{2 i}$ and prove that the
formula is correct.

\solution{
 Let $P(n): \sum_{i = 0}^{n} F_{2 i} = F_{2n+1} - 1$.

}
\end{problemparts}
\end{problem}
