Drexel dragonThe Math ForumDonate to the Math Forum

Ask Dr. Math - Questions and Answers from our Archives
_____________________________________________
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.

Thanks in advance,
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

If you have any questions about this or need more help, please write back
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

[Privacy Policy] [Terms of Use]

_____________________________________
Math Forum Home || Math Library || Quick Reference || Math Forum Search
_____________________________________

Ask Dr. MathTM
© 1994-2013 The Math Forum
http://mathforum.org/dr.math/