Fibonacci Recurred, Composed, SummedDate: 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/ |
Search the Dr. Math Library: |
[Privacy Policy] [Terms of Use]
Ask Dr. Math^{TM}
© 1994-2015 The Math Forum
http://mathforum.org/dr.math/