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