1
$\begingroup$

Use Mathematical Induction to show that

$$\sum\limits_{i=1}^n F_{2i}=F_{2n+1}-1$$

for all integer $n\geq1$.

My answer:

Base case:

for n = 1

$$\sum_{i = 1}^{n} F_{2i} = \sum_{i = 1}^{1} F_{2i} = F_{2 \cdot 1} = F_{3-1} = F_{2n+1} -1$$

Inductive Step:

$$\sum_{i = 1}^{n + 1} F_{2i} = F_2 + F_4 + \ldots + F_{2(n + 1)} = F_{2(n + 1) + 1} - 1$$

$\endgroup$
12
  • 1
    $\begingroup$ Is $F_j$ the $j$-th Fibonacci number? $\endgroup$ Oct 7, 2015 at 7:13
  • $\begingroup$ @Bens. Yeah it is :D $\endgroup$
    – BriannaXD
    Oct 7, 2015 at 7:14
  • 1
    $\begingroup$ Hint: Use $\sum_{i=1}^{n+1}F_{2i}=F_{2(n+1)}+\sum_{i=1}^nF_{2i}$. $\endgroup$ Oct 7, 2015 at 7:29
  • $\begingroup$ @bens. how do i apply that to the question? i tried working it out, but didnt really get anywhere. Im sorta new to mathematical induction, sigma and fionacci? thanks for the hint though! xo $\endgroup$
    – BriannaXD
    Oct 7, 2015 at 8:44
  • $\begingroup$ Have you done the base case? What is your induction assumption? Where are you stuck? $\endgroup$ Oct 7, 2015 at 10:10

1 Answer 1

1
$\begingroup$

Let $P(n)$ be the statement $$\sum_{k = 1}^n F_{2k} = F_{2n + 1} - 1$$

To prove the statement holds for each positive integer $n$ by mathematical induction, we must show that $P(1)$ holds and that $P(m + 1)$ holds whenever $P(m)$ holds since then we will have established the chain of implications $$P(1) \Rightarrow P(2) \Rightarrow P(3) \Rightarrow \cdots$$

In this case, we will need to use the properties of the Fibonacci sequence, which is defined recursively by \begin{align*} F_1 & = 1\\ F_2 & = 1\\ F_{n} & = F_{n - 1} + F_{n - 2}, \text{if $n \geq 3$} \end{align*} In particular, we have $$F_3 = F_{3 - 1} + F_{3 - 2} = F_2 + F_1 = 1 + 1 = 2$$

Base case: We show that $P(1)$ holds.

If $n = 1$, then $$\sum_{k = 1}^{1} F_{2k} = F_{2 \cdot 1} = F_2 = 1 = 2 - 1 = F_{3} - 1 = F_{2 \cdot 1 + 1} - 1$$ so $P(1)$ holds.

Inductive hypothesis:

Since $P(1)$ holds, we may assume $P(m)$ holds for some positive integer $m$. Thus, $$\color{green}{\sum_{k = 1}^{m} F_{2k} = F_{2m + 1} - 1}$$

Inductive step: We must show that $P(m) \Rightarrow P(m + 1)$ for each positive integer $m$.

Let $n = m + 1$. Then \begin{align*} \sum_{k = 1}^{m + 1} F_{2k} & = \color{green}{\sum_{k = 1}^{m} F_{2k}} + F_{2(m + 1)}\\ & = \color{green}{F_{2m + 1} - 1} + F_{2m + 2}\\ & = F_{2m + 3} - 1\\ & = F_{2(m + 1) + 1} - 1 \end{align*} Hence, $P(m) \Rightarrow P(m + 1)$ for each positive integer $m$.

Since $P(1)$ holds and $P(m) \Rightarrow P(m + 1)$ for each positive integer $m$, $P(n)$ holds for each positive integer $n$.$\blacksquare$

Note we have used the fact that $F_{n} = F_{n - 1} + F_{n - 2}$ when $n = 2m + 3$ to establish that $F_{2m + 3} = F_{2m + 2} + F_{2m + 1}$.

$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .