Project Euler Q2 - Sum of even Fibonacci numbers

Question

I'm very new at F#, and am using Project Euler to help me learn. Question #2 kept me going for a while, as my initial attempt at an answer was very slow and inelegant. Then I learnt about Seq.unfold, and a whole new vista unfolded in front of me!

The problem statement is as follows (source):

Each new term in the Fibonacci sequence is generated by adding the previous two terms. By starting with 1 and 2, the first 10 terms will be:

1, 2, 3, 5, 8, 13, 21, 34, 55, 89, ...

By considering the terms in the Fibonacci sequence whose values do not exceed four million, find the sum of the even-valued terms.

Please can you comment on this code. Bear in mind I'm very new at this, so I may be doing it completely wrong!

let fibEvenSum max =
  let rec fibEven n =
    match n with
    | 0 -> 0
    | 1 -> 2
    | n -> 4 * (fibEven (n - 1)) + (fibEven (n - 2))
  1 |> Seq.unfold (fun n -> Some(fibEven n, n+1))
    |> Seq.takeWhile (fun n -> n < max)
    |> Seq.sum

If I run it like this, I get the right answer:

sumOfEvenFibs 4000000I

Is there a better way to do it?

Answer 1

Daniel's solution to another question applies here equally.

On another question, I showed that the sum is equal to

$$ \frac{F_{3n+2} - 1}{2} $$

where \$3n\$ is the largest multiple of \$3\$ not to exceed the maximum.

If you wish to use this for asymptotic improvements, note that since the Fibonacci sequence has a closed-form solution, you can use it to find an approximate bound for \$3n\$, and then use fast exact mechanisms to find the exact value of \$F_{3n+2}\$.

$$ F_{3n} \approx \phi^{3n}/\sqrt 5 \\ 3n \approx \log_\phi \left(F_{3n} \sqrt 5 \right) $$

Finding a lower bound for \$n\$ thus takes very little time.

Personally I'd stick with the simple, slower solution, but it's interesting to note how far you can get with a bit of mathematical analysis.