<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] A combinatorial argument:
The fibonacci number $f_n$ represents the number of paths from 0 to $n - 1$ by taking steps of 1 or 2.
Now for any path for $f_{3n + 2}$, 


*

*it's all ones

*for $0 \leq k < 3n$, it starts with k ones, followed by a 2, followed by one of the paths for $f_{3n - k}$


so
\begin{align*}
f_{3n + 2} &= 1 + \sum_{k = 1}^{3n} f_{k} \\
&= 1 + \sum_{k = 1}^n \left(f_{3k} + f_{3k - 1} + f_{3k - 2} \right) \\
&= 1 + 2\sum_{k = 1}^n f_{3k} \tag{Since $f_i = f_{i - 1} + f_{i - 2}$} \\
f_3 + f_6 + \dots f_{3n} &= \frac{1}{2}(f_{3n + 2} - 1)
\end{align*}
</s>