Associated Topics || Dr. Math Home || Search Dr. Math

### Fibonacci Recurred, Composed, Summed

```Date: 02/18/2011 at 15:55:00
From: Aakash
Subject: Summation of f(g(g(n)))

We are given a recurrence -- the Fibonacci sequence:

f(n) = f(n - 1) + f(n - 2)

Further, we know that the sum of the odd elements of the Fibonacci
sequence is

sum {f(2n + 1)} = f(2n)

If I take g(n) = 2n + 1, then

sum {f(g(n))} = f(2n)

What I want to achieve is

sum{f(4n + 3)} = sum{f(4n + 2 + 1)}
= sum{f(2(2n + 1) + 1)}
= sum{f(2(g(n)) + 1)}
= sum{f(g(g(n)))}

But what is sum{f(g(g(n)))}? I can't figure out the solution.

Aakash Johari

```

```
Date: 02/18/2011 at 22:56:39
From: Doctor Vogler
Subject: Re: Summation of f(g(g(n)))

Hi Aakash,

Thanks for writing to Dr. Math.

I would recommend solving problems like this one by using the explicit
formula for f(n). Namely, ...

f(n) = g(a^n - b^n)

... where

g = 1/sqrt(5)
a = (1 + sqrt(5))/2
b = (1 - sqrt(5))/2

So a and b satisfy all of

a + b = 1
a * b = -1
a^2 = a + 1
b^2 = b + 1

And then you use the formula for the sum of a geometric series:

1 + r + r^2 + r^3 + ... + r^(m - 1) = (r^m - 1)/(r - 1).

Let's write this as

sum(n = 0, m - 1) r^n = (r^m - 1)/(r - 1).

Then we can use this to prove the first equation you wrote down:

sum(n = 0, m - 1) f(2n + 1) = f(2m).

We prove it like so:

sum(n = 0, m - 1) f(2n + 1)
= sum(n = 0, m - 1) g(a^(2n + 1) - b^(2n + 1))
= g*a*sum(n = 0, m - 1) (a^2)^n - g*b*sum(n = 0, m - 1) (b^2)^n
= g*a*(a^(2m) - 1)/(a^2 - 1) - g*b*(b^(2m) - 1)/(b^2 - 1)
= g*a*(a^(2m) - 1)/a - g*b*(b^(2m) - 1)/b
= g*(a^(2m) - 1) - g*(b^(2m) - 1)
= g*(a^(2m) - b^(2m))
= f(2m)

Now, if you add up a few terms of f(4n + 3), then you can clearly see that
it doesn't just add up to another Fibonacci number. So you have to expect
a messier formula. But you can apply the same kind of strategy to figure
out what that formula is:

sum(n = 0, m - 1) f(4n + 3)
= sum(n = 0, m - 1) g(a^(4n + 3) - b^(4n + 3))
= g*a^3*sum(n = 0, m - 1) (a^4)^n - g*b^3*sum(n = 0, m - 1) (b^4)^n
= g*a^3*(a^(4m) - 1)/(a^4 - 1) - g*b^3*(b^(4m) - 1)/(b^4 - 1)
= g*(a^(4m) - 1)*(a + 2)/5 - g*(b^(4m) - 1)*(b + 2)/5
= g*(a^(4m + 1) - b^(4m + 1) + 2*a^(4m) - 2*b^(4m) - a + b)/5
= g*(a^(4m + 1) - b^(4m + 1))/5 + 2*g*(a^(4m) - b^(4m))/5 - g*(a - b)/5
= f(4m + 1)/5 + 2*f(4m)/5 - f(1)/5
= (f(4m + 1) + 2*f(4m) - 1)/5

Now that you've figured out the formula, you could prove it by induction if
you preferred that method. But it's harder to figure out what the formula
is using induction.

You can also write it in slightly different ways, like

sum(n = 0, m - 1) f(4n + 3)
= (f(4m + 1) + 2*f(4m) - 1)/5
= (f(4m + 2) + f(4m) - 1)/5
= (f(4m + 3) - f(4m - 1) - 1)/5

and show me what you have been able to do, and I will try to offer further
suggestions.

- Doctor Vogler, The Math Forum
http://mathforum.org/dr.math/
```
Associated Topics:
High School Fibonacci Sequence/Golden Ratio

Search the Dr. Math Library:

 Find items containing (put spaces between keywords):   Click only once for faster results: [ Choose "whole words" when searching for a word like age.] all keywords, in any order at least one, that exact phrase parts of words whole words

Submit your own question to Dr. Math
Math Forum Home || Math Library || Quick Reference || Math Forum Search