Fibonacci is Fun

n = 0 F n 3 n = ? \sum_{n=0}^{\infty} \frac{F_{n}}{3^{n}}= \ ?

Details and Assumptions

F n F_{n} is the n th n^\text{th} Fibonacci number, with F 1 = F 2 = 1 F_{1} = F_{2} = 1 .


The answer is 0.6.

This section requires Javascript.
You are seeing this because something didn't load right. We suggest you, (a) try refreshing the page, (b) enabling javascript if it is disabled on your browser and, finally, (c) loading the non-javascript version of this page . We're sorry about the hassle.

3 solutions

Jake Lai
Apr 3, 2015

There is an algebraic solution (manipulation), as well a GP solution (Binet's), but here's Jake's quick-n-easy solution by generating functions.

It is well-known (and easily proven) result that

g ( x ) = x 1 x x 2 = n = 0 F n x n g(x) = \frac{x}{1-x-x^{2}} = \sum_{n=0}^{\infty} F_{n}x^{n}

for all x < 1 ϕ 0.618 |x| < \frac{1}{\phi} \approx 0.618 , where ϕ = 1 + 5 2 \phi = \frac{1+\sqrt{5}}{2} is the golden ratio.

Since 1 3 |\frac{1}{3}| is clearly less than 0.618 0.618 , we can just substitute x = 1 3 x = \frac{1}{3} . Thus,

n = 0 F n 3 n = 1 3 1 1 3 1 3 2 = 0.6 \sum_{n=0}^{\infty} \frac{F_{n}}{3^{n}} = \frac{\frac{1}{3}}{1-\frac{1}{3}-\frac{1}{3^{2}}} = \boxed{0.6}

Moderator note:

All three solutions are fantastic. Well done!

Solution by algebraic manipulation:

Let S = n = 0 F n 3 n \displaystyle S = \sum_{n=0}^{\infty} \frac{F_{n}}{3^{n}} . It can be seen that

n = 0 F n 3 n + 2 + n = 0 F n 3 n + 1 + F 0 3 0 + F 1 3 1 F 0 3 1 = n = 2 F n 3 n \sum_{n=0}^{\infty} \frac{F_{n}}{3^{n+2}} + \sum_{n=0}^{\infty} \frac{F_{n}}{3^{n+1}} + \frac{F_{0}}{3^{0}} + \frac{F_{1}}{3^{1}} - \frac{F_{0}}{3^{1}} = \sum_{n=2}^{\infty} \frac{F_{n}}{3^{n}}

since F n 2 + F n 1 = F n F_{n-2} + F_{n-1} = F_{n} (plus we have some leftover terms), implying

S 9 + S 3 + F 0 3 0 + F 1 3 1 F 0 3 1 = 4 S 9 + 1 3 = S \frac{S}{9} + \frac{S}{3} + \frac{F_{0}}{3^{0}} + \frac{F_{1}}{3^{1}} - \frac{F_{0}}{3^{1}} = \frac{4S}{9} + \frac{1}{3} = S

Solving the obtained equation gives us

S = n = 0 F n 3 n = 0.6 S = \sum_{n=0}^{\infty} \frac{F_{n}}{3^{n}} = \boxed{0.6}

Jake Lai - 6 years, 2 months ago

Log in to reply

I was so close to this when I gave up!! Beautiful solution! thank you :D

Aditya Pappula - 6 years, 2 months ago

Solution by geometric progression:

Recall that n = 0 x n = 1 1 x \displaystyle \sum_{n=0}^{\infty} x^{n} = \frac{1}{1-x} for all x < 1 |x| < 1 , and that F n = ϕ n ( ϕ ) n 5 F_{n} = \frac{\phi^{n}-(-\phi)^{-n}}{\sqrt{5}} .

Thus, we can rewrite our sum as

n = 0 F n 3 n = 1 5 ( n = 0 ϕ n 3 n n = 0 ( ϕ ) n 3 n ) \sum_{n=0}^{\infty} \frac{F_{n}}{3^{n}} = \frac{1}{\sqrt{5}} \left( \sum_{n=0}^{\infty} \frac{\phi^{n}}{3^{n}} - \sum_{n=0}^{\infty} \frac{(-\phi)^{-n}}{3^{n}} \right)

Both sums clearly satisfy the criterion x < 1 |x| < 1 , so we can proceed.

1 5 ( n = 0 ϕ n 3 n n = 0 ( ϕ ) n 3 n ) = 1 5 ( 1 1 ϕ 3 1 1 + 1 3 ϕ ) \frac{1}{\sqrt{5}} \left( \sum_{n=0}^{\infty} \frac{\phi^{n}}{3^{n}} - \sum_{n=0}^{\infty} \frac{(-\phi)^{-n}}{3^{n}} \right) = \frac{1}{\sqrt{5}} \left( \frac{1}{1-\frac{\phi}{3}} - \frac{1}{1+\frac{1}{3\phi}} \right)

After a bit of fiddling, we get that

1 5 ( 1 1 ϕ 3 1 1 + 1 3 ϕ ) = 0.6 \frac{1}{\sqrt{5}} \left( \frac{1}{1-\frac{\phi}{3}} - \frac{1}{1+\frac{1}{3\phi}} \right) = \boxed{0.6}

Jake Lai - 6 years, 2 months ago

Log in to reply

For those who want to know how to derive the general formula of the nth Fibonacci number, take a look at this amazing note by Daniel Chiu

Julian Poon - 6 years, 2 months ago

who is " Challenge master " ? Is Calvin sir ?

Karan Shekhawat - 6 years, 2 months ago

Log in to reply

Yeah. _

Julian Poon - 6 years, 2 months ago
Jason Hughes
Apr 4, 2015

Let the sum be expressed by S . S. S = F 0 3 0 + F 1 3 1 + F 2 3 2 + . . . S=\frac{F_{0}}{3^0}+\frac{F_{1}}{3^1}+\frac{F_{2}}{3^2}+... with F 0 = 0 F_{0}=0 3 S = 3 F 0 + F 1 3 0 + F 2 3 1 + F 3 3 2 + . . . 3S=3F_{0} + \frac{F_{1}}{3^0}+\frac{F_{2}}{3^1}+\frac{F_{3}}{3^2}+...

Adding the two yields

4 S = 3 F 0 + F 0 + F 1 3 0 + F 1 + F 2 3 1 + F 2 + F 3 3 2 + . . . 4S= 3F_{0} + \frac{F_{0} + F_{1}}{3^0}+\frac{F_{1} +F_{2}}{3^1}+\frac{F_{2}+F_{3}}{3^2}+...

4 S = 3 F 0 + F 2 3 0 + F 3 3 1 + F 4 3 2 + . . . 4S= 3F_{0} + \frac{F_{2}}{3^0}+\frac{F_{3}}{3^1}+\frac{F_{4}}{3^2}+...

9 S = 9 F 0 + 3 F 1 + F 2 3 0 + F 3 3 1 + F 4 3 2 + . . . 9S= 9F_{0} + 3F_{1}+ \frac{F_{2}}{3^0}+\frac{F_{3}}{3^1}+\frac{F_{4}}{3^2}+...

9 S 9 F 0 3 F 1 = F 2 3 0 + F 3 3 1 + F 4 3 2 + . . . 9S-9F_{0} - 3F_{1}= \frac{F_{2}}{3^0}+\frac{F_{3}}{3^1}+\frac{F_{4}}{3^2}+...

4 S = 9 S + 3 F 0 9 F 0 3 F 1 4S= 9S+ 3F_{0}-9F_{0}-3F_{1}

5 S = 3 F 1 5S=3F_{1}

S = 3 F 1 5 = 3 1 5 = 3 5 = 0.6 S=\frac{3F_{1}}{5}=\frac{3*1}{5}= \frac{3}{5}=0.6

Good job, Jason It is possible to reduce one or two steps.

Jeganathan Sriskandarajah - 5 years, 6 months ago

Log in to reply

Yes can go from

4 S = 3 F 0 + F 2 3 0 + F 3 3 1 + F 4 3 2 + . . . 4S= 3F_{0} + \frac{F_{2}}{3^0}+\frac{F_{3}}{3^1}+\frac{F_{4}}{3^2}+...

add 6 F 0 + 3 F 1 6F_{0}+3F_{1} to both sides and get

4 S + 6 F 0 + 3 F 1 = 9 F 0 + 3 F 1 + F 2 3 0 + F 3 3 1 + F 4 3 2 + . . . 4S+6F_{0}+3F_{1}= 9F_{0}+3F_{1}+ \frac{F_{2}}{3^0}+\frac{F_{3}}{3^1}+\frac{F_{4}}{3^2}+...

this equals 4 S + 6 F 0 + 3 F 1 = 9 S 4S+6F_{0}+3F_{1}= 9S which when F 0 F_{0} and F 1 F_{1} values are plugged in

5 S = 3 F 1 5S=3F_{1}

S = 3 F 1 5 = 3 1 5 = 3 5 = 0.6 S=\frac{3F_{1}}{5}=\frac{3*1}{5}= \frac{3}{5}=0.6

but I am not sure if reduces any steps or not.

Jason Hughes - 5 years, 6 months ago
Somesh Singh
Apr 5, 2015

an unreliable but a pretty easy method... adding the first 6 or 7 terms of the series would give you 0.58somethin.. As you go on adding you realise that the series converges since the succeeding terms go on becoming smaller and smaller. Hence the most logical convergence point for this series would be 0.6!!!

Yeah... that is what an engineer like me does, and it works for the ordinary world... but it come too short for the realms of Math. The 3 solutions posted by Jake Lai are brilliant... the first one a masterpiece.

I got the answer 0.6 following your method, then almost sure of the result I backtracked for the procedure and I struggled for the whole afternoon. Finally I got the answer, my solution is very similar to Jason Hughes, mine not at neat , somewhat more peasant but far from the excellence of the others.

Mariano PerezdelaCruz - 6 years, 2 months ago

0 pending reports

×

Problem Loading...

Note Loading...

Set Loading...