# Calculate the value of $\frac{1}{2}+\frac{1}{4}+\frac{2}{8}+\frac{3}{16}+....+\frac{F_n}{2^n}+....$ [duplicate]

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

• Thanks for posting this.
– user655800
Oct 3, 2019 at 8:09
• Oct 3, 2019 at 11:08
• Are you coming india for the itmo test this 14th . Oct 3, 2019 at 11:23
• @AkshajBansal yeah I am Oct 3, 2019 at 20:16
• Oh great i am of city montessori school gomtinagar only and would be taking part in the competion all the best for the exam will see you soon Oct 3, 2019 at 20:17

Replace $$F_n$$ with $$F_{n-1}+F_{n-2}$$, now you have two series that are both similar to $$S$$

• To expand on this, show that $S(x)=\sum_{k=0}^\infty F_kx^k$ is given by $S(x)-xS(x)-x^2S(x)=1$ for all small complex numbers $x$. Oct 3, 2019 at 8:53

Hint: if you know that the generating function for the Fibonacci sequence is:

$$\displaystyle \sum_{n=0}^\infty F_nx^n = \frac{x}{1-x-x^2}$$

then you can substitute $$x=\frac 1 2$$ and you immediately have

$$\displaystyle \sum_{n=0}^\infty \frac{F_n}{2^n} = \frac{\frac 1 2}{1-\frac 1 2 -\frac 1 4} =2$$

So to answer questions like this quickly, you should learn about generating functions.

• I think the OP looks for the steps towards a solution ; the knowledge of the generating function is no pre-knowledge for the OP, I think. Oct 3, 2019 at 11:24
• @GottfriedHelms So this might prompt the OP to learn about generating functions ... I have edited my answer to make this clear. Oct 3, 2019 at 12:17
• Very well! Upvoted. Oct 3, 2019 at 13:27
• +1 for using a generating function. Readers not familiar with generating functions might be interested in this question and its answers: math.stackexchange.com/questions/3142386/… Oct 3, 2019 at 17:48

Hint: $$F_n{={\frac {\Phi ^{n}-\Psi ^{n}}{\sqrt {5}}}={\frac {1}{\sqrt {5}}}\left(\left({\frac {1+{\sqrt {5}}}{2}}\right)^{n}-\left({\frac {1-{\sqrt {5}}}{2}}\right)^{n}\right)}$$

$$S = \sum_{n=1}^{\infty}\dfrac{F_n}{2^n}=\dfrac{1}{\sqrt{5}}\sum_{n=1}^{\infty}\left[\left(\dfrac{\Phi}{2}\right)^n- \left(\dfrac{\Psi}{2}\right)^n\right]$$

• The sign in the middle should be $-$. Oct 3, 2019 at 9:08
• @Dr Zafar Ahmend DSc Thank you for spotting the typo. Oct 7, 2019 at 18:45

$$F_n=\frac{a^n-b^n}{\sqrt{5}},~ a+b=1, ~ab=-1,~ a,b=\frac{1\pm\sqrt{5}}{2}.$$ The required sim $$s=\sum_{n=1}^{\infty} \frac{F_n}{2^n}= \frac{1}{\sqrt{5}} \sum_{n=1}^{\infty} \left ( \frac{a^n}{2^n}-\frac{b^n}{2^n} \right) =\frac{1}{\sqrt{5}}\left(\frac{a}{2-a}-\frac{b}{2-b}\right)= \frac{1}{\sqrt{5}}~\frac{2(a-b)}{4-2(a+b)+ab}=\frac{2 \sqrt{5}}{\sqrt{5}}=2.$$

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)$$