Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

I recently took a look a project euler, and I am trying to think of a smart way to do number 2. I looked at the sequence, and I saw that the question is basically asking for $$ \sum_{i=1}^n F_{3i} $$

For whatever n is gives me the nth even under a million. So, I did some fiddling around with this, and I got this to be equivalent to

$$ \sum_{i=0}^{n-1} F_{3i-1}(3^{n-i}-1) $$

I was wondering, is there even a closed form for something like this? Or am I wasting my time? I couldn't find a closed form online anywhere.

share|improve this question
1  
Find the Binet formula for the Fibonaccis, and you'll see this can be done using geometric series. –  Gerry Myerson Mar 7 '13 at 0:05
1  
What do you mean with "a smart way to do number $2$"?. I hope you don't mean that number $2$... –  Matemáticos Chibchas Mar 7 '13 at 1:07

3 Answers 3

up vote 7 down vote accepted

This answer does not give a closed form, but does give an approach to computing this sum.

The general closed form is still not always useful for computation, because you need to be able to compute some real values to great precision.

Also note that I start at $i=0$. This doesn't affect anything since $F_0=0$.

This answer requires somewhat sophisticated knowledge about linear recurrences.

There is a closed form for $F_n = a_1\alpha_1^n + a_2\alpha_2^n$ for some real numbers $a_1,\alpha_1,a_2,\alpha_2$. Then:

$$\begin{align}G_n = \sum_{i=0}^n F_{3i} &= a_1\frac{\alpha_i^{3n+3} -1}{\alpha_1-1}+a_2\frac{\alpha_2^{3n+3} -1}{\alpha_2-1}\\ &=b_1\alpha_1^{3n} + b_2\alpha_2^{3n} + b_3\cdot 1^n \end{align}$$

for some $b_1,b_2,b_3$.

Now you need to know a bit about this sort of recursive linear relationship, but if you look at the polynomial $(x-\alpha_1^3)(x-\alpha_2^3)(x-1) = (x^2-4x-1)(x-1) = x^3-5x^2+3x+1$, this yields a recurrence relationship:

$$G_{n+3} = 5G_{n+2} -3G_{n+1} - G_{n}$$

That gives you a recursive way to compute your sum, $G_n$ in general.

Another approach is to use the matrix formula:

$$\left(\begin{matrix}1 & 1\\1&0\end{matrix}\right)^n = \left(\begin{matrix}F_{n+1}&F_n\\F_n&F_{n-1}\end{matrix}\right)$$

If $A=\left(\begin{matrix}1 & 1\\1&0\end{matrix}\right)$, then the series $\sum_{i=0}^n A^{3i}$ has, in the off diagonal, the sum that you want.

But you get the normal sum of a geomtric series:

$$\sum_{i=0}^n A^{3i} = (A^{3n+3}-I)(A^3-I)^{-1}$$

Now, $A$ satisfies an equation, $A^2 - A - I = 0$, and therefore $A^3-I=2A$. Also $A^{-1} = A-I$, so you want to compute: $$\frac{1}{2}(A^{3n+3} - I)(A-I)$$

Now, it might not seem much easier to compute $A^{3n+3}$, but you can do that with only $O(\log(3n+3))$ multiplications by using the method of exponentiation by squaring.

once you've computed this matrix, take the value off the diagonal.

Ivan Loh below noted that we can do better in a comment in the other answer, and it applies here, too. We know $A^{3n+3}$, so we can write this all as:

$$\begin{align}(A^{3n+3}-I)(A-I) &= \frac 1 2 \left(\begin{matrix}F_{3n+4}-1&F_{3n+3}\\F_{3n+3}&F_{3n+2}-1\end{matrix}\right)\left(\begin{matrix}0 & 1\\ 1 & -1\end{matrix}\right)\\ &=\frac{1}{2}\left(\begin{matrix}*&*\\F_{3n+2}-1&*\end{matrix}\right) \end{align}$$

(We don't care about the other entries.)

So the sum we are looking for is $\frac{F_{3n+2}-1}{2}$.

share|improve this answer
    
The above is far more complex computationally than just calculating the answer using the definition of the Fibonacci numbers in the obvious way. –  Rob Arthan Mar 7 '13 at 0:54
    
Do you mean "harder" computationally (in terms of time computing,) or harder to understand? I think $O(\log n)$ is pretty good in the matrix approach. (It's probably a bit more than that, but certainly better than $O(n)$, which the bull-headed approach would give you.) @RobArthan –  Thomas Andrews Mar 7 '13 at 0:56
    
I just meant complex in the informal sense and was reading "smart" in the question as appropriate for a Project Euler problem, i.e. finding the answer to a specific problem efficiently. The problem in question is about quite small numbers, so a fairly "smart" solution is the naive one. –  Rob Arthan Mar 7 '13 at 1:11
2  
A lot of the PE problems have answers like this. For example, some of the earlier problems have answers that are $O(1)$ where the bull-headed answer is $O(n)$. It depends on what your goal is when solving PE problems - if you just want to code an answer, then of course, the linear approach is often faster. If you want a learning experience, a lot of PE problems give you room to explore. This poster in particular clearly wanted to explore. @RobArthan –  Thomas Andrews Mar 7 '13 at 1:20
    
This is great! this is exactly what I was looking for! I would have never thought about doing this with matrices. –  Broseph Mar 7 '13 at 18:27

$$F_k=\frac{\left(1+\sqrt{5}\right)^k}{2^k\sqrt{5}}-\frac{\left(1-\sqrt{5}\right)^k}{2^k\sqrt{5}}$$ $$\sum_{k=1}^nF_{3k}=\sum_{k=1}^n\frac{\left(1+\sqrt{5}\right)^{3k}}{2^{3k}\sqrt{5}}-\sum_{k=1}^n\frac{\left(1-\sqrt{5}\right)^{3k}}{2^{3k}\sqrt{5}}$$ $$=\frac{1}{\sqrt5}\sum_{k=1}^n\left(\frac{1+\sqrt{5}}{2}\right)^{3k}-\frac{1}{\sqrt5}\sum_{k=1}^n\left(\frac{1-\sqrt{5}}{2}\right)^{3k}$$ $$\text{ but we have , } x^3+x^6+x^9...x^{3n}=x^3\frac{x^{3n}-1}{x^3-1}$$ $$\text{ so then, }$$ $$=\frac{1}{\sqrt5}\sum_{k=1}^n\left(\frac{1+\sqrt{5}}{2}\right)^{3k}-\frac{1}{\sqrt5}\sum_{k=1}^n\left(\frac{1-\sqrt{5}}{2}\right)^{3k}$$ $$=\frac{1}{\sqrt5}\left(\left(\frac{1+\sqrt{5}}{2}\right)^3\frac{\left(\frac{1+\sqrt{5}}{2}\right)^{3n}-1}{\left(\frac{1+\sqrt{5}}{2}\right)^3-1}-\left(\frac{1-\sqrt{5}}{2}\right)^3\frac{\left(\frac{1-\sqrt{5}}{2}\right)^{3n}-1}{\left(\frac{1-\sqrt{5}}{2}\right)^3-1}\right)=\frac{F_{3n+2}-1}{2}$$

$$=\sum_{k=1}^{n}F_{3k}$$

share|improve this answer
    
Note that if $\alpha=\frac{1\pm \sqrt{5}}{2}$ then $\alpha^3 - 1 = 2\alpha$, so you can simplify this a bit. –  Thomas Andrews Mar 7 '13 at 1:02
    
+1. But this answer woul be easier to read with "\left(...\right)" rather than default parentheses sizes. –  Thomas Andrews Mar 7 '13 at 1:06
    
@Ethan you do realise this can actually be simplified to $\sum\limits_{k=1}^{n}{F_{3k}}=\frac{F_{3n+2}-1}{2}$? (which incidentally can be computed in $O(log(n))$ time) –  Ivan Loh Mar 7 '13 at 2:43
    
Thanks, @Ivan, I missed that formula, even though it obviously falls out of my matrix formula. –  Thomas Andrews Mar 7 '13 at 3:00

For variety, if $\varphi$ is the golden ratio, then

$$ \varphi^n = F_{n-1} + F_n \varphi $$

(where $F_0 = 0$ and $F_1 = 1$... and $F_{-1} = 1$) The same equation holds for $\bar{\varphi}$, the other root of $x^2 = x+1$. (not the complex conjugate)

Therefore

$$\sum_{i=0}^n \varphi^{3i} = (\cdots) + \left(\sum_{i=0}^n F_{3i} \right) \varphi $$

We can get rid of the unwanted term by by subtracting off its conjugate:

$$\sum_{i=0}^n \varphi^{3i} - \bar{\varphi}^{3i} = \left(\sum_{i=0}^n F_{3i} \right) (\varphi - \bar{\varphi}) $$

And then you can do whatever you like from there. This is, of course, similar to the other answers; I just like how it's organized.

share|improve this answer
    
It's also similar to my matrix answer, since $A^n = F_{n-1}I+F_nA$ - essentially, since $A$ has $\phi$ and $\bar\phi$ as eigenvalues, it stands in for both of them simultaneously. –  Thomas Andrews Mar 7 '13 at 19:25

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.