Prove for all $n\in \mathbb{N}$ that $\sum_{i=0}^{n} i\cdot F_{2i} = (n+1)F_{2n + 1} - F_{2n + 2}$.

73 Views Asked by At

$F_n$ denotes the Fibonacci sequence where $n$ is the term of the Fibonacci number in the sequence. ($F_0=0$, $F_1=1$, $F_2=1$, $F_3=2$, $F_4=3$, ... $F_n=F_{n-1} + F_{n-2}$)

I want to prove this using strong induction and have formulated base cases for when $n=0$ and when $n=1$.

My induction hypothesis is that for all $k\in \mathbb{N}$, $k\geq 1$ we can assume that for $k-1$, $\sum_{i=0}^{k-1} i\cdot F_{2i} = (k)F_{2k - 1} - F_{2k}$ and that for $k$, $\sum_{i=0}^{k} i\cdot F_{2i} = (k + 1)F_{2k + 1} - F_{2k + 2}$.

For my induction step I want to show that for $k+1$, $\sum_{i=0}^{k+1} i\cdot F_{2i} = (k+2)F_{2k + 3} - F_{2k + 4}$. I've been stuck on the equation below for the past couple of hours trying to figure out how I can derive the equation for $k + 1$.

\begin{align*} \sum_{i=0}^{k+1} i\cdot F_{2i} &= (k + 1)\cdot F_{2k + 2} + \sum_{i=0}^{k} i\cdot F_{2i}\\ &= (k + 1)\cdot F_{2k + 2} + (k + 1)F_{2k + 1} - F_{2k + 2} + \sum_{i=0}^{k - 1} i\cdot F_{2i}\\ &= (k + 1)\cdot F_{2k + 2} + (k + 1)F_{2k + 1} - F_{2k + 2} + (k)F_{2k - 1} - F_{2k}\\ \end{align*}

Any help is appreciated.

1

There are 1 best solutions below

1
On BEST ANSWER

\begin{align} \sum_{i=0}^{k+1}iF_{2i}&=(k+1)F_{2k+2}+(k+1)F_{2k+1}-F_{2k+2}\\ &=kF_{2k+2}+(k+1)(F_{2k+3}-F_{2k+2})\\ &=(k+1)F_{2k+3}-F_{2k+2}\\ &=(k+1)F_{2k+3}-(F_{2k+4}-F_{2k+3})\\ &=(k+2)F_{2k+3}-F_{2k+4}. \end{align}