Fibonacci sum

Calculus Level 4

∑ n = 1 ∞ F n 2 n \large \sum^{\infty}_{n=1}{\dfrac{F_n}{2^n}}

Find the sum above, where F n F_n is the n th n^{\text{th}} Fibonacci number that is F 0 = 0 F_0 = 0 , F 1 = 1 F_1 = 1 and F n = F n − 1 + F n − 2 F_n = F_{n-1} + F_{n-2} for n ≥ 2 n \geq 2 .


The answer is 2.

Akeel Howell by Akeel Howell , 22, USA

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.

1 solution

Chew-Seong Cheong
Mar 26, 2017

S = ∑ n = 1 ∞ F n 2 n S converges (see note) = 1 2 + ∑ n = 2 ∞ F n 2 n = 1 2 + ∑ n = 0 ∞ F n + F n + 1 2 n + 2 = 1 2 + 1 4 ∑ n = 0 ∞ F n 2 n + 1 2 ∑ n = 0 ∞ F n + 1 2 n + 1 Note that F 0 = 0 = 1 2 + 1 4 ∑ n = 1 ∞ F n 2 n + 1 2 ∑ n = 1 ∞ F n 2 n Note that S = ∑ n = 1 ∞ F n 2 n = 1 2 + S 4 + S 2 ⟹ S 4 = 1 2 ⟹ S = 2 \begin{aligned} S & = \sum_{n=1}^\infty \frac {F_n}{2^n} & \small \color{#3D99F6} S \text{ converges (see note)} \\ & = \frac 12 + \sum_{\color{#3D99F6}n=2}^\infty \frac {F_n}{2^n} \\ & = \frac 12 + \sum_{\color{#D61F06}n=0}^\infty \frac {F_n+F_{n+1}}{2^{n+2}} \\ & = \frac 12 + \frac 14 \sum_{\color{#D61F06}n=0}^\infty \frac {\color{#3D99F6}F_n}{2^n} + \frac 12 \sum_{\color{#D61F06}n=0}^\infty \frac {F_{n+1}}{2^{n+1}} & \small \color{#3D99F6} \text{Note that }F_0 = 0 \\ & = \frac 12 + \frac 14 \sum_{\color{#3D99F6}n=1}^\infty \frac {F_n}{2^n} + \frac 12 \sum_{\color{#3D99F6}n=1}^\infty \frac {F_n}{2^n} & \small \color{#3D99F6} \text{Note that } S = \sum_{n=1}^\infty \frac {F_n}{2^n} \\ & = \frac 12 + \frac S4 + \frac S2 \\ \implies \frac S4 & = \frac 12 \\ \implies S & = \boxed{2} \end{aligned}

Ratio Test as suggested by @Tapas Mazumdar

L = lim ⁡ n → ∞ ∣ a n + 1 a n ∣ = lim ⁡ n → ∞ ∣ F n + 1 F n ⋅ 2 n 2 n + 1 ∣ = 1 2 lim ⁡ n → ∞ F n + 1 F n = φ 2 < 1 where φ = 1 + 5 2 is the golden ratio. \small \begin{aligned} L & = \lim_{n \to \infty} \left| \frac {a_{n+1}}{a_n} \right| \\ & = \lim_{n \to \infty} \left| \frac {F_{n+1}}{F_n} \cdot \frac {2^n}{2^{n+1}} \right| \\ & = \frac 12 \color{#3D99F6} \lim_{n \to \infty} \frac {F_{n+1}}{F_n} \\ & = \frac {\color{#3D99F6}\varphi}2 < 1 & \small \color{#3D99F6} \text{where }\varphi = \frac {1+\sqrt 5}2 \text{ is the golden ratio.} \end{aligned}

Therefore, S = ∑ n = 1 ∞ F n 2 n \small \displaystyle S = \sum_{n=1}^\infty \frac {F_n}{2^n} converges.

10 Helpful 0 Interesting 0 Brilliant 0 Confused

Sir, isn't is so that before assigning a variable to an infinite sum, you must show that the sum is converging as well?

Tapas Mazumdar - 4 years, 2 months ago

Log in to reply

You are right. But I don't know how. It is given here (eqn. 16) that ∑ n = 0 ∞ F n x n = x 1 − x − x 2 \displaystyle \sum_{n=0}^\infty F_n x^n = \frac x{1-x-x^2}

Chew-Seong Cheong - 4 years, 2 months ago

Log in to reply

Maybe by the ratio test it can be proven. This is the idea which I have in mind:

Let a n a_n denote the n th n^{\text{th}} term of this sequence. If lim ⁡ n → ∞ a n + 1 a n < 1 \displaystyle \lim_{n \to \infty} \dfrac{a_{n+1}}{a_n} < 1 , we have absolute convergence.

We can show that lim ⁡ n → ∞ F n + 1 x n + 1 F n x n < 1 \displaystyle \lim_{n \to \infty} \dfrac{F_{n+1} x^{n+1}}{F_n x^n} < 1 like this

lim ⁡ n → ∞ F n + 1 x n + 1 F n x n = lim ⁡ n → ∞ F n + 1 F n ⋅ lim ⁡ n → ∞ x = ϕ ⋅ x \lim_{n \to \infty} \dfrac{F_{n+1} x^{n+1}}{F_n x^n} = \lim_{n \to \infty} \dfrac{F_{n+1}}{F_n} \cdot \lim_{n \to \infty} x = \phi \cdot x

Which absolutely converges for x < 1 ϕ ≈ 0.618 x < \dfrac{1}{\phi} \approx 0.618 .

Since in this problem it was given that x = 1 2 x = \dfrac 12 , so it satisfies the absolute convergence.

Tapas Mazumdar - 4 years, 2 months ago

Log in to reply

@Tapas Mazumdar – Nicely done, Tapaz! (Root test also works here!) As a difficult challenge, try to prove that it converges using Cauchy condensation test as well.

It's uncommon to see that people are willing to write down the complete solution these days. People should aspire to be like you. You'll make a good mathematician one day~!

Pi Han Goh - 4 years, 2 months ago

Log in to reply

@Pi Han Goh – I'm unfamiliar with Cauchy condensation test as of now. I would get some knowledge on this and then get back to your challenge.

PS, can you suggest some external web links that can help me (I searched for it or Brilliant but couldn't find any)?

And thank you sir! :-)

Tapas Mazumdar - 4 years, 2 months ago

Log in to reply

Everyone who attempted got this right

Aakash Khandelwal - 4 years, 2 months ago

0 pending reports

×

Problem Loading...

Note Loading...

Set Loading...