1
$\begingroup$

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?

$\endgroup$
8
  • 3
    $\begingroup$ 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$ $\endgroup$ – lulu Aug 31 '15 at 14:42
  • $\begingroup$ Sorry, didn't understand the notation. Can you please elaborate more? $\endgroup$ – Aditya Agarwal Aug 31 '15 at 14:43
  • $\begingroup$ I'll write it out in more detail and post it as a solution. $\endgroup$ – lulu Aug 31 '15 at 14:44
  • $\begingroup$ Sure! (y) TYSM.. $\endgroup$ – Aditya Agarwal Aug 31 '15 at 14:44
  • $\begingroup$ Perhaps this formula will be useful: $F_n=\frac{{(\frac{1+\sqrt{5}}{2})}^{n}-{(\frac{1-\sqrt{5}}{2})}^{n}}{\sqrt{5}}$ $\endgroup$ – Oussama Boussif Aug 31 '15 at 14:46
7
$\begingroup$

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

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

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.

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

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

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.