# Computing $\left\lfloor\sum_{k = 1}^{n}{\varphi^{3k}}\right\rfloor$

I'm trying to find $\left\lfloor\sum_{k = 1}^{n}{\varphi^{3k}}\right\rfloor$ mod $m$. $\varphi = \frac{1 + \sqrt{5}}{2}$ and $\varphi^3 = 2 + \sqrt{5}$.

But honestly I'm not even sure where to start. I can see spending some time and finding a pattern for $\varphi^{3k}$ but I I need a way to compute the summation in case $n$ is large.

Any help is appreciated. Thank you.

P.S. My background is not in this. Sorry if this question is easy.

-
I’m not sure what you mean by $x\bmod m$ when $x$ is not an integer, but a closed expression for the sum is no problem: see my answer for that. –  Brian M. Scott Nov 20 '12 at 8:10
@BrianM.Scott Ah! I meant to floor the function. Will edit. Say if m = 100, I can get the last two digits before the decimal point. –  McTrafik Nov 20 '12 at 8:11

By running the Berlekamp-Massey algorithm on the sequence given by the first values of $$A_n=\left\lfloor\sum_{k=1}^{n}\varphi^{3k}\right\rfloor$$ it looks like the characteristic polynomial of the sequence is $$p_A(x) = x^3-5x^2+3x+1 = (x-1)(x-(2+\sqrt{5}))(x-(2-\sqrt{5})),$$ giving $$A_{n+3} = 5 A_{n+2} - 3 A_{n+1} - A_n$$ or $$A_{n+2} = 4 A_{n+1} + A_n + 6,$$ that leak a lot of information about the arithmetic behaviour of the sequence $\{A_n\}_{n\in\mathbb{N}}\pmod{p}.$ In perfect analogy with the case of Fibonacci numbers, this arithmetic behaviour strongly depends on whether $5$ is a quadratic residue $\pmod{p}$ or not, i.e. on the structure of the ring $$\mathbb{F}_p[x]_{/((x-1)(x^2-4x-1))}=\mathbb{F}_p\times \mathbb{F}[x]_{/(x^2-4x-1)}.$$ In any case, $A_n\pmod{m}$ can be computed by taking the $n$-th power $\pmod{m}$ of the companion matrix associated to the polynomial $p_A(x)$, that can be done using the classical repeated-squaring algorithm.

-
That recurrence equation is what I was looking for! Thank you. I don't quite understand the last two paragraphs, but I'll sleep on it. –  McTrafik Nov 20 '12 at 19:37

You’re just summing a finite geometric series with ratio $\varphi^3$:

$$\sum_{k=1}^n\varphi^{3k}=\frac{\varphi^{3(n+1)}-\varphi^3}{\varphi^3-1}=\frac{\varphi^3\left(\varphi^{3n}-1\right)}{\varphi^3-1}=\frac{2+\sqrt5}{1+\sqrt5}\left(\varphi^{3n}-1\right)=\frac14\left(3+\sqrt5\right)\left(\varphi^{3n}-1\right)\;.$$

-
Thank you. This is incredibly helpful. So now I just need to figure out how to compute $\varphi^{3n}$ mod $m$. :) –  McTrafik Nov 20 '12 at 8:17
@McTrafik: You’re welcome. Unfortunately, that last bit may not be easy to do in a nice way. –  Brian M. Scott Nov 20 '12 at 8:20
I should be able to pick it up from here. :) –  McTrafik Nov 20 '12 at 8:27