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.
 A: 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*}
A: 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}
A: We have
$$f_k = \dfrac{\phi^k - (-\phi)^{-k}}{\sqrt5}$$
Use this along with geometric series to conclude what you want.
A: define 
$$B_n = \sum_{k=1}^{3n} f_k$$
LEMMA $$B_n = f_{3n+2} - 1$$
PROOF by induction. 
(A) for $n=1$ we have $f_1+f_2+f_3 = 1+1+2=4 = 5-1=f_5-1$
(B) suppose true for $n$, then:
$$B_{n+1} = B_n +f_{3n+1} +f_{3n+2}+f_{3n+3} \\
= f_{3n+2} - 1 +f_{3n+1} +f_{3n+2}+f_{3n+3} \\
= (f_{3n+1} +f_{3n+2}) +(f_{3n+2}+f_{3n+3})-1\\
= f_{3n+3} +f_{3n+4}  -1\\
= f_{3n+5} -1\\
= f_{3(n+1)+2} -1 \\
$$
qed
now define $S_n = \sum_{k=1}^n f_{3k}$
clearly $B_n=2S_n$ since $f_1+f_2+f_3 = 2f_3$ etc.
and the result follows.
