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'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.

share|improve this question
    
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

2 Answers 2

up vote 2 down vote accepted

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.

share|improve this answer
1  
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)\;.$$

share|improve this answer
    
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

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.