# Find the series: $\frac{-1}{4}+\left(\frac12+\frac14+\frac28+\frac3{16}+\frac5{32}+\cdots\right)$

Find the series: $$\frac{-1}{4}+\left(\frac12+\frac14+\frac28+\frac3{16}+\frac5{32}+\cdots\right)$$ Evidently, this is a Fibonacci Sequence with a Geometric Sequence.
But I don't think there is a formula for the sum of Fibonacci Sequence..

Also, I have heard about Binet's formula, but we can't use these formulas. We just have to use elementary, basic things like $S_n-\frac12S_n$ and all. I tried:
$$S_n=\left(\frac12+\frac14+\frac18+\cdots\right)+\left(\frac18+\frac2{16}+\cdots\right)$$ $$S_n=1+\left(\frac18+\frac2{16}+\cdots\right)$$

I keep on repeating that, but what happens is that the Fibonacci Sequence gets shifted till infinity. So what to do please tell?

• Hint: Look at the generating function for the Fibonacci numbers, $$F(x)=\sum F_n\,x^n$$. Easy to get an explicit form for that. Then let $x=\frac 12$ – lulu Aug 31 '15 at 14:42
• Sorry, didn't understand the notation. Can you please elaborate more? – Aditya Agarwal Aug 31 '15 at 14:43
• I'll write it out in more detail and post it as a solution. – lulu Aug 31 '15 at 14:44
• Sure! (y) TYSM.. – Aditya Agarwal Aug 31 '15 at 14:44
• Perhaps this formula will be useful: $F_n=\frac{{(\frac{1+\sqrt{5}}{2})}^{n}-{(\frac{1-\sqrt{5}}{2})}^{n}}{\sqrt{5}}$ – Oussama Boussif Aug 31 '15 at 14:46

$$S=\frac{F_1}{2^1}+\frac{F_2}{2^2}+\cdots$$ We want to use the property $F_n+F_{n+1}=F_{n+2}$. Add the sum to itself in such a way that you can use a common denominator: $$S+\frac{S}{2}=\frac{F_1}{2^1}+\frac{F_1+F_2}{2^2}+\frac{F_2+F_3}{2^3}+\cdots$$ $$\frac{3}{2}S=\frac{F_1}{2}+\underbrace{\frac{F_3}{2^2}+\frac{F_4}{2^3}+\cdots}_{2(S-F_1/2-F_2/4)}$$ Recognize a part of the original sum (with two missing terms and a factor of 2): $$\frac{3}{2}S=\frac{F_1}{2}+2\left(S-\frac{F_1}{2}-\frac{F_2}{4}\right)$$ Just express $S$, given $F_1=F_2=1$.

$$\frac32S-2S=\frac{1}2-1-\frac12$$ $$\frac{S}{2}=1$$ $$S=2$$

Now your required series will be $$2-\frac14=\frac74$$

• A nice, basic solution. This would serve as a good introduction to the more general generating function approach. – marty cohen Aug 31 '15 at 16:06

Let $F_n$ denote the $n^{th}$ Fibonacci number. So we have the recursion:

$$F_n=F_{n-1}+F_{n-2}\;\;\;F_0=1=F_1$$

Define a power series $$F(x)=\sum F_n\,x^n=1+x +2x^2+3x^3+5x^4+...$$

We want a simple expression for $F(x)$. But use the recursion and match coefficients of $x^n$...we have $$F(x)=xF(x)+x^2F(x)+1\;\;\Rightarrow\;\;F(x)=\frac{1}{1-x-x^2}$$

Note: Check this! Easy to drop a term. Now compare $F(\frac 12)$ to your desired sum.

• (+1) Sorry, you answer was good, but I wanted an elementary answer, so.. – Aditya Agarwal Aug 31 '15 at 14:59

You have the generating function of the Fibonacci sequence:

$$F_{n + 2} = F_{n + 1} + F_n \qquad F_0 = 0, F_1 = 1$$

\begin{align} F(z) &= \sum_{n \ge 0} F_n z^n \\ &= \frac{z}{1 - z - z^2} \end{align}

This series converges for $\lvert z \rvert < (\sqrt{5} - 1)/2 \approx 0.618$.

Your sum is essentially $F(1/2)$.