I solved it using Recursive method, i.e. $$E=\frac12(E+1)+\frac14(E+2)+\frac14*2$$
Which gave the answer $E=6$
I Also found probablity that it ends in $n$ tosses is $\frac{F_{n-1}}{2^n}$
Thus $$E[X]=\sum_{n=0}^\infty\frac{n\,F_{n-1}}{2^n}$$ where $F_n$ is the nth Fibonacci number with $F_0=0$, $F_1=1$
Is there a nice way to solve this summation?
The standard generating function for the Fibonacci numbers is $$1+x+2x^2+3x^3+\cdots =\frac 1{1-(x+x^2)}$$
See this question for example.
Note that this expression is using $F_0=F_1=1$ so, as you are using $F_0=0, F_1=1$ we need to consider the function $$F(x)=x+x^2+2x^3+\cdots =\frac x{1-(x+x^2)}=\sum_0^{\infty} F_nx^n$$
Where, to stress, we are using your version of the $F_n$.
We then remark that $$xF(x)=\sum_0^{\infty} F_nx^{n+1}\implies \left(xF(x)\right)'=\sum_0^{\infty} (n+1)F_nx^n$$
$$\implies \left(xF(x)\right)'\Big \vert_{x=\frac 12}=\sum_0^{\infty}\frac {(n+1)F_n}{2^n}=\sum_1^{\infty}\frac {nF_{n-1}}{2^{n-1}}$$
$$\implies \sum_1^{\infty}\frac {nF_{n-1}}{2^{n}}=\frac 12\times \left(xF(x)\right)'\Big \vert_{x=\frac 12}$$
We then remark that $$\left(xF(x)\right)'=\frac {(2-x)x}{(1-x-x^2)^2}\implies \left(xF(x)\right)'\Big \vert_{x=\frac 12}=12$$ and we are done.