The nth term of the Fibonacci sequence is given by the formula

Every third Fibonacci number is even and all of the rest are odd, so the nth even Fibonacci number is given by the formula

where

and

Alpha is larger than one and beta is smaller than one (in absolute value). So the alpha term in the equations above is dominant while the beta term is almost negligible. To figure out how many even Fibonacci numbers are below four million, we compute

which tells us that we will obtain the largest even Fibonacci number less than 4000000 when we take n=11. Since our formula for the nth even Fibonacci number is a difference of geometric series, we can compute directly

Sum=

I punched this into my Ti-83 and it gave me the right answer. Are we not supposed to post the answers? What’s with that?

### Like this:

Like Loading...

*Related*

Tags: prob2

This entry was posted on May 15, 2009 at 3:13 pm and is filed under Uncategorized. You can follow any responses to this entry through the RSS 2.0 feed.
You can leave a response, or trackback from your own site.

May 15, 2009 at 6:00 pm |

Very nice work! I don’t know about

supposedto post answers. I’m neither going to encourage or discourage it, personally.Now, off to code the ideas of the solution up, and see how they work out, time-wise. This seems to be along the lines of a constant time algorithm, independant of the upper bound (4000000 in this case), making it noticeably better than the other solutions so far (as well as the one I wrote but have not yet posted…).

May 15, 2009 at 11:12 pm |

I don’t see why you take log base to determine the bound to go to for . I expect that it is because you are thinking about , but I’m not seeing it exactly. I can see

thatit works, but am still missingwhy. Any insight?May 15, 2009 at 11:18 pm |

I think I just made a typo. It should be alpha cubed, not three alpha. I’m just throwing out the beta term and solving for the value of n that makes the alpha term equal to four million.

May 16, 2009 at 10:10 am |

Ah, ok. Using looks like what I was expecting. And for comparison sake, using gives a log around 10.132, so from a programming standpoint, the difference (at least with a bound of 4000000) is the difference between ceil() and floor(). Anyway, good times.

May 20, 2009 at 5:49 pm |

[…] other solution I’d like to give code for is the generalization of Tim’s mathematical solution to any bound. Again trimming out some import (you need to import math for this to work in pure […]

September 19, 2009 at 9:16 am |

[…] instead of the number itself. We’ve already visited Fibonacci numbers in problem 2, and had useful work there. For this problem, it will be helpful to note that the number of digits of can be found as , […]