5
$\begingroup$

This question already has an answer here:

The sequence of numbers $F_n$ for $n \in N$ defined below are called the Fibonnaci numbers. $F_1 = F_2 = 1$, and for $n \geq 2$, $F_{n+1} = F_n + F_{n-1}$. Prove the following facts about the Fibonnaci numbers

For each of the following, $n \in N$

a) $\displaystyle \sum_{i=1}^nF_i = F_{n+2} - 1$

I started this proof by using strong induction

To prove something by strong induction, you have to prove that if all natural numbers strictly less than $N$ have the property, then $N$ has the property.

$n \geq 2$, $F_{n+1} = F_n + F_{n-1}$

Check basis step $n=2$:

$F_1 + F_2 = 1 + 1 = 2 = 3-1 = F_4 - 1$, therefore TRUE

I'm unsure how to go any further, when it comes to strong induction I'm lost on how to set up my IH, and proceed for the rest of the steps

$\endgroup$

marked as duplicate by Martin Sleziak, Henrik, Adam Hughes, hardmath, Namaste discrete-mathematics Dec 30 '16 at 17:55

This question has been asked before and already has an answer. If those answers do not fully address your question, please ask a new question.

  • $\begingroup$ For strong induction, your assumption is that the statement is true for all $n=1,2,\cdots,k$ and then you try to prove it for the case $n=k+1$. So, if you try to prove this in the case for $n=k+1$, which extra assumptions will you also need (for smaller values of $n$)? Hint, you may also need more base cases. $\endgroup$ – Michael Burr Aug 18 '15 at 19:01
  • $\begingroup$ @Michael Burr So would you consider n = k + 1 and n = k-1? $\endgroup$ – ChristopherW Aug 18 '15 at 19:22
  • 1
    $\begingroup$ Hint: What is the relationship between $\sum\limits_{i=1}^{k+1} a_i$ and $\sum\limits_{i=1}^k a_i$ for an arbitrary sequence $a_n$? $\endgroup$ – Christopher Carl Heckman Aug 18 '15 at 19:22
  • $\begingroup$ @Carl Heckman 2≤n≤k+1? $\endgroup$ – ChristopherW Aug 18 '15 at 19:27
  • $\begingroup$ Hint: Start with $F_{n+2}-1$, rewrite this using the Fibonacci property and they use the inductive hypothesis (somehow). $\endgroup$ – Michael Burr Aug 18 '15 at 19:30
1
$\begingroup$

$$ F_{3} = F_2 + F_{1} \\ F_{4} = F_3 + F_{2} \\ F_{5} = F_4 + F_{3}\\ ... F_{n} = F_{n -1} + F_{n-2}\\ F_{n+1} = F_n + F_{n-1}\\ F_{n+2} = F_{n+1} + F_{n}\\ $$ Now just sum the right side and the left side.

You'll get: $$ \sum_{i=3}^{n+2}F_i = \sum_{i=2}^{n+1}F_i + \sum_{i=1}^{n}F_i $$ Then $$ \sum_{i=3}^{n}F_i + F_{n+1}+ F_{n+2} = \sum_{i=2}^{n+1}F_i + \sum_{i=3}^{n}F_i + F_1 + F_2 $$

$\endgroup$
  • $\begingroup$ But how do you set up the 2 cases for strong induction? $\endgroup$ – ChristopherW Aug 18 '15 at 20:21
  • $\begingroup$ @ChristopherW I don't use strong induction $\endgroup$ – user261263 Aug 18 '15 at 20:23
3
$\begingroup$

We know that $F_{n+2} = F_{n+1} + F_n \implies F_n = F_{n+2} - F_{n+1}$, so ... $$\sum_{i=1}^nF_i = \sum_{i=1}^n\left(F_{i+2} - F_{i+1}\right)$$$$=\left(F_3 - F_2\right) + \left(F_4-F_3\right) + \dots + \left(F_{n+1} - F_{n}\right)+ \left(F_{n+2} - F_{n+1}\right)$$ $$= F_{n+2} + \left(F_{n+1} - F_{n+1}\right) + \dots + \left(F_{3} - F_{3}\right) - F_2$$


If you are determined to use induction, you have already provided a base case.. the step shouldn't be too crazy, you just need to massage some terms around

Assume $\sum_{i=1}^nF_i = F_{n+2} - 1$, then $$\sum_{i=1}^{n+1}F_i =F_{n+1} + \sum_{i=1}^nF_i = F_{n+1} + \left(F_{n+2} - 1\right)$$ $$= \left(F_{n+1} + F_{n+2}\right) - 1 = F_{n+3} - 1$$

$\endgroup$
1
$\begingroup$

For the base case you will need to use $n=1$ if you wish to prove for all $n\in\mathbb{Z^+}$.

$$\sum_{i=1}^{n}{F_i} = \sum_{i=1}^{1}{F_i} = F_1 = 1$$ and $$F_{n+2}-1=F_3-1=2-1=1$$

Proving the base case.

For the induction step (weak induction suffices, note that weak induction is a special case of strong induction), you can assume the IH (induction hypothesis) for $n$ and prove the identity for $n+1$. Let $L(n)$ be the left-hand side of the identity for $n$ and let $R(n)$ be the right-hand side.

Then

$$\begin{align} L(n+1) &= \sum_{i=1}^{n+1}{F_i} \\ &= F_{n+1} + \sum_{i=1}^{n}{F_i} \\[1em] &= F_{n+1} + F_{n+2} - 1 &(\text{by IH for n}) \\[1em] &= F_{n+3} - 1 &(\text{by the recursion relationship}) \\[1em] &= R(n+1) \end{align}$$

This proves the induction step.

$\endgroup$
  • $\begingroup$ how do you use the base case on n=1 if the question is for n≥2? $\endgroup$ – ChristopherW Aug 18 '15 at 20:32
  • $\begingroup$ The identity needs to be proven for $n\in\mathbb{N}$. Proving the identity for $n\ge1$ automatically means you have proven it for $n\ge2$. $\endgroup$ – Marconius Aug 18 '15 at 20:41
  • $\begingroup$ When you did $F_n+2 − 1= F3−1=2−1=1$ Wouldn't that just be 3-1=2? $\endgroup$ – ChristopherW Aug 18 '15 at 20:50
1
$\begingroup$

Combinatorial Proof:

For each $n\in\mathbb{N}_0$, the number of ways to tile an $1$-by-$n$ array with $1$-by-$1$ squares and $1$-by-$2$ dominos is $F_{n+1}$. Hence, the number of ways to tile an $1$-by-$(n+1)$ array in such a manner with at least one domino is given by $F_{n+2}-1$.

Now, let $k$ be the earliest position of the dominos. For each $k$, we are left with the $1$-by-$(n-k)$ array to tile, which can be done in $F_{n-k+1}$ ways. Since $k$ can be anything from $1$ to $n$, we have $$F_{n+2}-1=\sum_{k=1}^n\,F_{n-k+1}=\sum_{i=1}^n\,F_i\,.$$

$\endgroup$

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