Prove by induction: The fibonacci sequence is defined as follows:
$f_1 = 1$, $f_2 = 1$ and $f_{n+2} = f_n + f_{n+1}$ for $n \geq 1$
Prove by induction that $f_1^2 + f_2^2 + \dotsb + f_n^2 = f_n f_{n+1}$
I am new to proofs by induction and having a hard time even getting the base case.
HINT Note that $$f_n f_{n+1} + f_{n+1}^2 = \underbrace{f_{n+1}(f_n + f_{n+1}) = f_{n+1} f_{n+2}}_{\text{From the definition, } f_{n+2} = f_n + f_{n+1}}$$
For the base case you start with showing your assertion holds for $n=1$. This can be done in numerous ways, for example $$1=1 \iff 1= 1 \cdot 1 \\ \iff 1^2 = f_1 \cdot f_2 \\ \iff f^2_1 = f_1 \cdot f_2 \\ \iff \sum_{i=1}^1 f^2_i= f_{1}f_{2}$$ you know the equality holds since $f_1 = f_2 = 1$. Now you know your expression is true for $n=1$, simply by starting with a (very basic) fact that you know. Namely, that $1=1$. This completes the base case.
Next, we make the induction hypothesis: Suppose that for all $n$ where $1< n \leq k$ that $$\sum_{i=1}^n f^2_i= f_{n}f_{n+1}$$ holds. Now we want to know what happens if we consider the quantity $$\sum_{i=1}^{k+1} f^2_i$$ Now we manipulate this sum in a way that we know something about part of it. What I mean by that is rewrite $$\sum_{i=1}^{k+1} f^2_i = \sum_{i=1}^{k} f^2_i+f^2_{k+1}$$ This is useful, because by the induction hypothesis we know $$\sum_{i=1}^{k} f^2_i =f_kf_{k+1}$$ and hence $$\sum_{i=1}^{k} f^2_i+f^2_{k+1} = f_kf_{k+1}+f^2_{k+1} \\ = f_{k+1}(f_k+f_{k+1})$$ Now recall the definition of a fibonacci number, that $f_k+f_{k+1} = f_{k+2}$ which means $$f_{k+1}(f_k+f_{k+1}) = f_{k+1}f_{k+2}$$ And now piecing everything together, you have enough to conclude that $$\sum_{i=1}^{k+1} f^2_i=f_{k+1}f_{k+2}$$ That completes the proof by induction. An overhead view of what happened was we proved a proposition $P(n)$ for the case of $n=1$ (base case). Then we showed in general that if $P(k)$ is true for any $k$ that $P(k) \implies P(k+1)$. Hence, since $P(1)$ is true, we get a sequence of true propositions $$P(1) \implies P(2) \implies P(3) \implies \dots \implies P(k) \implies P(k+1) \implies \dots $$ and are allowed to say that $$\sum_{i=1}^{n} f^2_i=f_{n}f_{n+1}$$ for all $n \in \Bbb{N}$.
