A Fibonacci Sum

Let x be the desired sum. Then

$2x=1+\frac{1}{2}+\frac{2}{4}+\frac{3}{8}+\frac{5}{16}+\frac{8}{32}+\ldots$

Subtracting the series that $x$ represents from the $2x$ series above yields

$2x-x=1+\frac{1}{4}+\frac{1}{8}+\frac{2}{16}+\frac{3}{32}+\ldots,$

which is equal to $1+\frac{1}{2}x$ . So solving the equation $x=1+\frac{1}{2}x$ for $x$ yields $x=2=\frac{2}{1}$ . Therefore the answer is $2+1=\boxed{3}$ .

Well since I cannot be beautiful I'll just beLet's see the property of Fibonacci Sum:

$F_{k-1}+F_k=F_{k+1}$

Then, we can apply this to the sum, then the sums will look like $\frac{1}{2} + \frac{1}{4} +\frac{1+1}{8} +\frac {1+2}{16} +\frac{2+3}{32} + ...$ $=\frac{1}{2} + \frac{1}{4} +\frac{1}{8}+\frac{1}{8} +\frac {1}{16}+\frac{2}{16} +\frac{3}{32} + \frac{2}{32} ...$ $=\frac{1}{2} +(\frac{1}{4} +\frac{1}{8} +\frac{2}{16} +\frac{3}{32}+...) +(\frac{1}{8} +\frac{1}{16} +\frac{2} {32} +\frac{3}{64}+...)$ Then we can change the second and third term and express as $\sum_{k=1}^\infty \frac{F_k} {2^{k}}=\frac{1}{2} + \sum_{k=1}^\infty \frac{F_k} {2^{k+1}}+\sum_{k=1}^\infty \frac{F_k} {2^{k+2}}$ $\sum_{k=1}^\infty \frac{F_k} {2^{k}}=\frac{1}{2} + \frac{1}{2} \sum_{k=1}^\infty \frac{F_k} {2^{k}}+\frac{1}{4}\sum_{k=1}^\infty \frac{F_k} {2^{k}}$ $\frac{1}{4}\sum_{k=1}^\infty \frac{F_k} {2^{k}}=\frac{1}{2}$ $\sum_{k=1}^\infty \frac{F_k} {2^{k}}=\frac{2}{1}$ Thus the answer is $\boxed{3}$

The generating function for the Fibonacci numbers is $F(x)=\sum_{k=0}^{\infty}F_n x^n=\frac{x}{1-x-x^2}$ and the sum is equal to $\sum_{k=1}^{\infty}F_k \left (\frac{1}{2}\right )^k=\sum_{k=0}^{\infty}F_k \left (\frac{1}{2}\right )^k=F\left (\frac{1}{2}\right )=2=\frac{1}{2}$ .

Some solutions here assume that the series converges - here's a solution using probabilities to 'avoid' that issue:

Suppose A and B are playing a game consisting of several rounds. They both have a $\frac{1}{2}$ chance of winning any round. Suppose the game ends when one of the players wins three consecutive rounds. Let $S_n$ be a set containing the sequences of winners of each round such that the game ends in $n$ rounds, where $n\ge 3$ , e.g. $S_5 = \{AABBB, ABAAA, BABBB, BBAAA\}$ . Let $T_n$ be a subset of $S_n$ containing the sequences that start with two different winners, e.g. $T_5 = \{ABAAA, BABBB\}$ .

Let $m\ge 4$ . There is bijection between $T_m$ and $S_{m-1}$ , by just removing the first player in each sequence of $T_m$ (the inverse is to prepend the other player who is not the initial winner for each sequece of $S_{m-1}$ to that same sequence). Furthermore, there is a bijection between $S_m\backslash T_m$ and $T_{m-1}$ , by removing the first player in each sequence of $S_m\backslash T_m$ (the inverse is to prepend the same player who is the initial winner for each sequence of $T_{m-1}$ to that same sequence). Thus we know that $|S_m|=|T_m|+|S_m\backslash T_m|=|S_{m-1}|+|T_{m-1}|$

Define the Fibonacci sequence by $F_0=0, F_1=1, F_i=F_{i-1}+F_{i-2}$ for $i\ge 2$ . Now observe that $|S_3|=2, |T_3|=0$ . We claim that $|S_n|=2F_{n-2},|T_n|=2F_{n-3}$ . We can prove this by induction, for which the base case $n=3$ is already done. The inductive step is essentially the last equation in the previous paragraph.

The probability that the game ends in $n$ rounds is therefore $\frac{|S_n|}{2^n}=\frac{F_{n-2}}{2^{n-1}}$ . Since the sum of probabilities is $1$ , we conclude that $\sum_{k=1}^\infty \frac{F_k}{2^k}=\sum_{n=3}^\infty \frac{F_{n-2}}{2^{n-2}}=2\sum_{n=3}^\infty \frac{F_{n-2}}{2^{n-1}}=2\sum_{n=3}^\infty\text{probability that game ends in }n\text{ rounds}=2$

$S = \frac{1}{2} + \frac{1}{4} + \frac{2}{8} + \frac{3}{16} + ....... \infty$

$\frac{S}{4} = \frac{1}{8} + \frac{1}{16} + \frac{2}{32} + \frac{3}{64} + ....... \infty$

$S - \frac{S}{4} = \frac{1}{2} + \frac{1}{4} + \frac{1}{8} + \frac{2}{16} + \frac{3}{32} +....\infty$

Now for the 4th term of the above series to be a perfect term of GP we need to subtract the above series with $\frac{S}{8}$ and so on.

$S - (\frac{S}{4} + \frac{S}{8} + \frac{S}{16} +....\infty) = \frac{1}{2} + \frac{1}{4} + \frac{1}{8} + \frac{1}{16} + \frac{1}{32} +....\infty$

Now, we have 2 G.P.s and so just use the GP formula both times to get the answer.

$S - \frac{\frac{S}{4}}{1-\frac{S}{2}} = \frac{\frac{1}{2}}{1-\frac{1}{2}}$

$\frac{S}{2} = 1$

$S = 2$

We can also use this :

If we call S the sum of this quantity, so :

$S = \sum{k=1}^\infty \frac {F{k}}{2^{k}} \\ = \sum_{k=0}^\infty \frac {F_{k}}{2^{k}} (F_{0}=0)\\ = \frac 12F_{1} + \sum_{k=2}^\infty \frac {F_{k-1}+F_{k-2}}{2^{k}}\\ = \frac {1}{2} + \sum_{k=2}^\infty \frac {F_{k-1}}{2^{k}} + \sum_{k=2}^\infty \frac {F_{k-2}}{2^{k}}\\ = \frac {1}{2} + \frac {1}{2} \times \sum_{k=0}^\infty \frac {F_{k}}{2^{k}} + \frac {1}{2^{2}} \times \sum_{k=0}^\infty \frac {F_{k}}{2^{k}}\\ = \frac {1}{2} + \frac 12S + \frac 12^{2}S\\$

Then, $S = \frac {2}{2^{k} - 2 - 1} = 2 = \frac {2}{1}$

a+b = 2+1 = 3

There has been a saying says: "Violence is Art." So i'll give out a violent solution.

As everybody knows, the Fibonacci number has a fomula: $F_n=\frac{1}{\sqrt{5}}\left(\left(\frac{1+\sqrt{5}}{2}\right)^n-\left(\frac{1-\sqrt{5}}{2}\right)^n\right)$

So do a little deform:

$\begin{aligned} \sum_{n=1}^{\infty}\frac{F_n}{2^n}&=\sum_{n=1}{\infty}\frac{\frac{1}{\sqrt{5}}\left(\left(\frac{1+\sqrt{5}}{2}\right)^n-\left(\frac{1-\sqrt{5}}{2}\right)^n\right)}{2^n}\\ &=\frac{1}{\sqrt{5}}\sum_{n=0}^{\infty}\frac{(1+\sqrt{5})^n-(1-\sqrt{5})^n}{4^n}\\ &=\frac{1}{\sqrt{5}}\left(\sum_{n=0}^{\infty}\left(\frac{1+\sqrt{5}}{4}\right)^n-\sum_{n=0}^{\infty}\left(\frac{1+\sqrt{5}}{4}\right)^n\right) \end{aligned}$

and it is a normal geometric sequence. Easy to know that it is 2, which is $\frac{2}{1}$

so the answer is $1+2=3$

I used a little bit of Python to get to my answer.

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14

from fractions import Fraction as frac
memo = {1:1,2:1}
def fib(x):
    if x in memo:
        return memo[x]
    memo[x] = fib(x-1) + fib(x-2)
    return memo[x]
total = 0
k = 1
infinity = 1000
while k <= infinity:
    total += frac(fib(k),2**k)
    k += 1
print "Answer:",float(total)