0

Fib sequence is below

\begin{cases} 0 & n = 0 \\ 1 & n = 1 \\ F(n-1) + F(n-2) & n > 1 \end{cases}

for any $n \in \mathbb N$, $F(2n) = \sum_{i=1}^{n} F(2i - 1)$

for $n \geq 1$

I'll prove this using induction

Base Case:

Let n = 1

$F(2(1)) = F(2) = 1 + 0 = 1 = F(1) = \sum_{i=1}^{1} F(2i - 1)$ [By def of fib seq]

as wanted

Inductive step: Let $n > 1$

Suppose $F(2j) = \sum_{i=1}^{j} F(2i - 1)$ whenever $1 \leq j < n$ [I.H]

What to show: $F(2n) = \sum_{i=1}^{n} F(2i-1)$

$F(2n) = F(2n-1) + F(2n-2)$ [Could somebody tell me how to get this]

$= F(2n-1) + F(2(n-1))$

$= F(2n-1) + \sum_{i=1}^{n-1} F(2i-1)$ [I.H]

$= F(2n-1) + F(1) + F(3) + \cdots + F(2(n-1) - 1)$ [Sigma properties]

$= \sum_{i=1}^{n} (2i-1)$ [Nvm I get this part, I just don't get how $F(2n) = F(2n-1) + F(2n-2)$

Tinler
  • 1,061
  • What do you get when you substitute $n\mapsto 2n$ in $F(n)=F(n-1)+F(n-2)$, the recurrence relation for the Fibonacci sequence ? – Prasun Biswas Sep 24 '17 at 07:31
  • If it was $F(2n+1)$, then would this be right: $$F(2n+1) = F(2n+1-1) + F(2n+1-2) = F(2n) + F(2n-1)$$ – Tinler Sep 24 '17 at 07:33
  • Yes, that's correct. We don't really need induction though. Here's a simple direct proof: $$\begin{align}F(2n)&=F(2n-1)+F(2n-2)\&=F(2n-1)+F(2n-3)+F(2n-4)\ &~~~\vdots \& =F(2n-1)+F(2n-3)+\ldots +F(3)+F(1)+F(0)\&=\sum_{i=1}^n F(2i-1)\end{align}$$ where we use $F(2)=F(1)+F(0)$ and $F(0)=0$ – Prasun Biswas Sep 24 '17 at 07:35

1 Answers1

1

Assuming it is true for $n$: $$F(2n)=\sum_{i=1}^n F(2i-1)$$ we must prove for $n+1$: $$F(2(n+1))=\sum_{i=1}^{n+1} F(2(n+1))=$$ $$\sum_{i=1}^n F(2i-1) +F(2(n+1)-1)=$$ $$F(2n)+F(2n+1),$$ which is true by definition of the Fibonacci sequence.

farruhota
  • 31,482