<s>[INST] Fibonacci sequence proof Prove the following:
$$f_3+f_6+...f_{3n}= \frac 12(f_{3n+2}-1) \\ $$
For $n \ge 2$
Well I got the basis out of the way, so now I need to use induction: So that $P(k) \rightarrow P(k+1)$ for some integer $k \ge 2$
So, here are my first steps:
$$ \begin{align} & \frac 12(f_{3k+2}-1) + f_{3k+3} = \\ 
   & = \frac 12(f_{3k+2}-1) + f_{3k+1} + f_{3k} +  f_{3k+1} \\
   & = \frac 12(f_{3k+2}-1) + f_{3k+1} + \frac 12(f_{3k+2}-1) +  f_{3k+1} \\
   & = f_{3k+2}-1 + 2 \cdot f_{3k+1} 
   \end{align} $$
And the fun stops around here. I don't see how to get to the conclusion: $\frac 12(f_{3k+5}-1) \\ $. Any help from this point would be great.
 [/INST] One way to derive/prove these identities is to start from
$$\begin{pmatrix} f_{n-1} & f_n \\ f_n &f_{n+1} \end{pmatrix} = \begin{pmatrix} 0 & 1 \\ 1 & 1 \end{pmatrix}^n$$
Note that
\begin{align}
& \begin{pmatrix} 0 & 2 \\ 2 & 2 \end{pmatrix} \begin{pmatrix} f_2+f_5+ \ldots +f_{3n-1} & f_3+f_6+ \ldots +f_{3n} \\ f_3+f_6+\ldots +f_{3n} & f_4+f_7+\ldots+f_{3n+1} \end{pmatrix} \\
& =\left( \begin{pmatrix} 0 & 1 \\ 1 & 1 \end{pmatrix}^3 - I \right)\left(\begin{pmatrix} 0 & 1 \\ 1 & 1 \end{pmatrix}^3+\begin{pmatrix} 0 & 1 \\ 1 & 1 \end{pmatrix}^6+\ldots +\begin{pmatrix} 0 & 1 \\ 1 & 1 \end{pmatrix}^{3n}\right) \\
& =\begin{pmatrix} 0 & 1 \\ 1 & 1 \end{pmatrix}^{3n+3}-\begin{pmatrix} 0 & 1 \\ 1 & 1 \end{pmatrix}^3 \\
&=\begin{pmatrix} f_{3n+2} & f_{3n+3} \\ f_{3n+3} & f_{3n+4} \end{pmatrix}-\begin{pmatrix} 1 & 2 \\ 2 & 3 \end{pmatrix}
\end{align}
</s>