A question about the proof that for prime p, p divides k(p), where k() is the Perrin sequence Define the Perrin sequence by $k(1)=0$, $k(2)=2$, $k(3)=3$, and $k(n)=k(n-2)+k(n-3)$.  We find that mostly $n$ divides $k(n)$ iff $n$ is prime, although there are a few exceptions called "Perrin Pseudo-primes."
But the obvious conjecture only fails for $n$ composite, for we find that whenever $p$ is prime, $p | k(p)$.  However, the usual proof goes as follows.
Let $\alpha$, $\beta$, and $\gamma$ be the roots of the characteristic polynomial $x^3-x-1$.  Then a simple induction argument shows that $k(n)=\alpha^n+\beta^n+\gamma^n.$
Now consider $(\alpha+\beta+\gamma)^p = \alpha^p+\beta^p+\gamma^p+p\sum(things)$.  Since we have $p$ times something, when we consider this module $p$ we get:
$$(\alpha+\beta+\gamma)^p = \alpha^p+\beta^p+\gamma^p$$
and we're done, because $\alpha+\beta+\gamma = 0$.  And that would be fine if the things in the summation were integers.
But they're not.
So my question is: why is that summation always considered to be an integer, when the things in the summation are the roots of the cubic, and not integral?
All the papers I've read seem to take this for granted, so I'm sure I must be missing something simple.
Thank you.
 A: Because that summation is a symmetric polynomial in $\alpha,\beta,\gamma$ with integer coefficients, so it must be an integer polynomial of $s_1=\alpha+\beta+\gamma=0$, $s_2=\alpha\beta+\alpha\gamma+\beta\gamma=-1$ and $s_3=\alpha\beta\gamma=1$.
You can actually write the formula precisely as:
$$\begin{align}\alpha^p+\beta^p+\gamma^p &= \sum_{i+2j+3k=p}\frac{p}{i+j+k}\binom{i+j+k}{i,j,k}s_i^i(-s_2)^js_3^k\\
\end{align}$$
When $\alpha+\beta+\gamma=0$, this becomes:
$$\alpha^p+\beta^p+\gamma^p = p\sum_{2j+3k=p} \frac{1}{j+k}\binom{j+k}{k}(-s_2)^js_3^k$$
If course, it takes some effort to prove that $\frac{1}{j+k}\binom{j+k}{k}$ is an integer when $2j+3k$ is prime, or you can apply the general theorem about symmetric polynomials.
Now, one way to see this in this case is to examine the generating function:
$$\begin{align}\sum_{n=0}^{\infty} (a^n+b^n+c^n)z^n &= \frac{1}{1-az}+\frac{1}{1-bz}+\frac{1}{1-cz}\\
&=\frac{1-2s_1z+s_2z^2}{1-s_1z+s_2z^2-s_3z^3}\\
&=(1-2s_1z+s_2z^2)\sum_{n=0}^\infty \left(s_1z-s_2z^2+s_3z^3\right)^n
\end{align}$$
Only a finite number of terms on the right side contribute to any single term of the left.
A: If instead of $\alpha,\beta,\gamma$ we consider variables $x,y,z$, then what you have denoted by $\sum(things)$ is actually a symmetric polynomial in $x,y,z$ with integer coefficients. There is a theorem, called fundamental theorem of symmetric polynomials which states that such a polynomial can be also expressed as a polynomial with integer coefficients not in $x,y,z$, but in $e_1(x,y,z),e_2(x,y,z),e_3(x,y,z)$, elementary symmetric polynomials in $x,y,z$.
Now you can easily see that $e_1(\alpha,\beta,\gamma), e_2(\alpha,\beta,\gamma), e_3(\alpha,\beta,\gamma)$ are, by Vieta's formulas, exactly the coefficients of the characteristic polynomial, which are integers. So we know that $\sum(things)$ can be expressed as a polynomial with integer coefficients with integer variables, so is an integer.
