1
$\begingroup$

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.

$\endgroup$
  • 1
    $\begingroup$ Let $P(n)$ be the proposition you've written above. The base case is $P(1)$, the statement $f_1^2 = f_1f_2$. That's easy to show, no? $\endgroup$ – Simon S Nov 29 '14 at 19:14
1
$\begingroup$

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}}$$

$\endgroup$
-1
$\begingroup$

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}$.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.