Fibonacci identity proof I've been struggled for this identity for a while, how can I use combinatorial proof to prove the Fibonacci identity $$F_2+F_5+\dots+F_{3n-1}=\frac{F_{3n+1}-1}{2}$$
I know that $F_n$ is number of tilings for the board of length $n-1$, so if I rewrite the identity and let $f_n$ be the number of tilings for the board of length $n$, then I got $$f_1+f_4+\dots+f_{3n-2}=\frac{f_{3n}-1}{2}$$
the only thing that I know so far is the Right hand side, $f_{3n}-1$ is the number of tilings for the $3n$ board with at least one $(1\times 2)$ tile (or maybe I am wrong), but I have no idea of what the fraction $\frac{1}{2}$ is doing here. Can anyone help?
(P.S.: In general, when it comes to this kind of combinatorial proof question, is it ok to rewrite the question in a different way? Or is it ok to rewrite this question as $2(f_1+f_4+\dots+f_{3n-1})=f_{3n}-1$, then process the proof?
Thank you for all your useful proofs, but this is an identity from a course that I am taking recently, and it is all about combinatorial proof, so some hint about how to find the number of tilings for the board of length $3n$ would be really helpful.
Thanks for dtldarek's help, I finally came up with:
Rewrite the identity as $2F_2+2F_5+\dots+2F_{3n-1}=\frac{F_{3n+1}-1}{2}$, then the Left hand side becomes $F_2+F_2+F_5+F_5+\dots+F_{3n-1}+F_{3n-1}=F_0+F_1+F_2+F_3+\dots+F_{3n-3}+F_{3n-2}+F_{3n-1}=\sum^{3n-1}_{i=0}F_{i}\implies \sum^{3n-1}_{i=0} F_i=F_{3n+1}-1$, and recall that $f_n$ is the number of tilings for the board of length $n$, so we have $\sum^{3n-2}_{i=0}f_i=f_{3n}-1$.
For the Right hand side $f_{3n}$ is the number of tilings for the length of $3n$ board, then $f_{3n}-1$ is the number of tilings for a $3n$ board use at least one $1\times 2$ tile.  Now, for the Left hand side, conditioning on the last domino in the $k^{th}$ cell, for any cells before the $k^{th}$ cell, there are only one way can be done, and all cells after the $k+1$ cell can be done in $f_{3n-k-1}$, finally sum up $k$ from 0 to $3n-1$, which is the Left hand side.
Is it ok? did I change the meaning of the original identity?

This may not be the quickest approach, but it seems fairly simple, using only the recursion equation $F_i+F_{i+1}=F_{i+2}$ and initial conditions, which I take to be $F_0=0$ and $F_1=1$.  Notice first that you can apply the recursion equation to replace, on the left side of your formula, each term by the sum of the two preceding Fibonacci numbers, so this left side is equal to $F_0+F_1+F_3+F_4+F_6+F_7+\dots+F_{3n-3}+F_{3n-2}$, which skips exactly those terms that are present in your formula's left side.  So, adding this form of your left side to the original form, you find that  twice the left side is the sum of all the Fibonacci numbers up to and including $F_{3n-1}$.  So what needs to be proved is that $\sum_{i=0}^{3n-1}F_i=F_{3n+1}-1$.  That can be done by induction on $n$.  The base case is trivial ($0+1+1=3-1$), and the induction step is three applications of the recursion equation.  In $\sum_{i=0}^{3(n+1)-1}F_i$, apply the induction hypothesis to replace all but the last three terms with $F_{3n+1}-1$. To combine that with the last three terms, $F_{3n}+F_{3n+1}+F_{3n+2}$, use the recursion equation to replace $F_{3n}+F_{3n+1}$ and $F_{3n+1}+F_{3n+2}$ with $F_{3n+2}$ and $F_{3n+3}$, respectively, and then again to replace these last two results with $F_{3n+4}=F_{3(n+1)+1}$.
