1
$\begingroup$

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.

  • 0
    @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.2012-11-20

2 Answers 2

3

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.

  • 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.2012-11-20
3

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)\;.$

  • 0
    I should be able to pick it up from here. :)2012-11-20