<s>[INST] Calculate the value of $\frac{1}{2}+\frac{1}{4}+\frac{2}{8}+\frac{3}{16}+....+\frac{F_n}{2^n}+....$ The Fibonacci sequence starts with 1, 1, 2, 3, 5, 8, 13, ... .(Start from the 3rd term,
each term is the sum of the two previous terms). Let $F_n$ be the $n$th term of this sequence. $S$ is defined as $S=\frac{1}{2}+\frac{1}{4}+\frac{2}{8}+\frac{3}{16}+....+\frac{F_n}{2^n}+....$
Calculate the value of $S$
I have no idea how to solve this, hints aswell as solutions would be appreciated 
Taken from the 2013 AITMO
 [/INST] To expand on the hint of @empy2:                    
$$\begin{array}{rlll}
  S(z) &= 1 + & 1z +& 2z^2 + 3z^3 + 5z^4 + ... \\\
z S(z) &=     & 1z +& 1z^2 + 2z^3 + 3z^4 + 5z^5 + ... \\\
S(z)-zS(z)-1 &=     && 1z^2 + 1z^3 + 2z^4 + 3z^5   \\\ 
\end{array} \\\
\begin{array}{rlll} \hline
S(z)-zS(z)-1 &= z^2 S(z) &\qquad & \phantom{sdfsdfsdfsdfs} \\\
S(z)(1-z-z^2)& =1 \\\
S(z) &= 1/(1-z-z^2) 
\end{array}
$$
Now insert $1/2$ for $z$ and compute $1/2 S(1/2)$
</s>