<s>[INST] $F_{2n} = F_{2n-2}+2F_{2n-4}+\dots+n$ rigorous proof 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..
 [/INST] 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*}
$$
</s>