$F_{2n} = F_{2n-2}+2F_{2n-4}+\dots+n$ rigorous proof

Question

Let $F_{n}$ be n-th fibonacci number($F_{0}$ = 0) and $g_{n} = F_{2n}$ if $n > 0$ $g_{0} = 1$. I want to prove that $g_{n} = g_{n-1}+2g_{n-2}+\dots +ng_{0}$. It's obviously seen from direct evaluation but it's not so rigorous and my attempts to use induction end in failure..

Answer 1

There are many ways to prove this. One way is to notice that $$ F_{2n} = F_{2n-1} + F_{2n-2} = 2F_{2n-2} + F_{2n-3} = 2F_{2n-2} + F_{2n-3} + F_{2n-4} - F_{2n-4} = 3F_{2n-2} - F_{2n-4}. $$ Therefore $$ g_n = 3g_{n-1} - g_{n-2}. $$ Given this, it is easy to prove the claim by induction. Let's rephrase it slightly: $$ g_n = \sum_{i=1}^{n-1} ig_{n-i} + n. $$ In particular, when $n = 0$ we get $g_0 = 0$, and when $n = 1$ we get $g_1 = 1$, both obviously correct. Assuming the claim holds for $n-1,n-2$, we have $$ \begin{align*} g_n &= 3g_{n-1} - g_{n-2} \\ &= 3\sum_{i=1}^{n-2} ig_{n-1-i} + 3(n-1) - \sum_{i=1}^{n-3} ig_{n-2-i} - (n-2) \\ &= \sum_{i=1}^{n-2} i(3g_{n-1-i} - g_{n-2-i}) + 2n-1 \\ &= \sum_{i=1}^{n-2} ig_{n-i} + 2n-1 \\ &= \sum_{i=1}^{n-1} ig_{n-i} - (n-1)g_1 + 2n-1 \\ &= \sum_{i=1}^{n-1} ig_{n-i} + n. \end{align*} $$

Answer 2

For first, prove by induction that: $$ F_0 + F_2 + \ldots + F_{2m} = F_{2m+1}-1. \tag{1}$$ Then sum the previous identities for $m=1,2,\ldots, n$, getting:

$$ n F_0 + (n-1) F_2 + \ldots +F_{2n} = \left( F_3+F_5+\ldots+F_{2n+1}\right)-n.\tag{2}$$ Since we can prove: $$ F_3 + F_5 + \ldots + F_{2n+1} = F_{2n+2}-2 \tag{3}$$ just like we proved $(1)$, by $(2)$ it follows that: $$\sum_{j=0}^{n} (n-j) F_{2j} = \sum_{j=0}^{n} j F_{2n-2j} = F_{2n+2}-(n+2).\tag{4}$$ Now you just need to adjust $(4)$ a bit.