Math of Problem 2

by

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

$\frac{1}{\sqrt{5}} \left( \left( \frac{1+\sqrt{5}}{2}\right)^n -\left( \frac{1-\sqrt{5}}{2}\right)^n \right)$

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

$\frac{1}{\sqrt{5}} \left( \alpha^{3n} -\beta^{3n} \right)$

where

$\alpha=\frac{1+\sqrt{5}}{2}$   and    $\beta=\frac{1-\sqrt{5}}{2}$

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

$\log_{\alpha^3} 4000000 \sqrt{5}=11.0876...$

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= $\frac{1}{\sqrt{5}} \left( \frac{1-\alpha^{36}}{1-\alpha^3} -\frac{1-\beta^{36}}{1-\beta^3} \right)$

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?

Tags:

6 Responses to “Math of Problem 2”

1. sumidiot Says:

Very nice work! I don’t know about supposed to 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…).

2. sumidiot Says:

I don’t see why you take log base $3\alpha$ to determine the bound to go to for $n$. I expect that it is because you are thinking about $\alpha^{3n}$, but I’m not seeing it exactly. I can see that it works, but am still missing why. Any insight?

3. mathapocalypse Says:

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.

4. sumidiot Says:

Ah, ok. Using $\alpha^3$ looks like what I was expecting. And for comparison sake, using $3\alpha$ 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.

5. Problem 2 – various approaches « Leonhard Euler’s Flying Circus Says:

[…] 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 […]

6. Problem 25 – More Fibonacci Numbers « Leonhard Euler’s Flying Circus Says:

[…] 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 , […]