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

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.

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.

• You say: "Because that summation is a symmetric polynomial in α,β,γ with integer coefficients, so it must be an integer polynomial of s1=α+β+γ=0, s2=αβ+αγ+βγ=−1 and s3=αβγ=1." -- that's pretty much exactly the step I don't understand, and exactly the question I'm asking. – C D Wright May 13 '15 at 11:30
• If $x^3-x-1=(x-\alpha)(x-\beta)(x-\gamma)$, then multiply it out. You get $x^3-x-1=x^3-s_1x^2+s_2x-s_3$. @CDWright – Thomas Andrews May 13 '15 at 11:33
• That tells me that $s_1$, $s_2$, and $s_3$ are integers. That's fine. I don't see why the summation involving $\alpha$, $\beta$, and $\gamma$ can be re-written with $s_1$, $s_2$, and $s_3$. Naively the summation is of non-integral terms, and being able to re-write it using the coefficients of the characteristic polynomial would obviously then imply that it's an integer. I don't see how it's obvious one can do that. If it's simply a case of "that's the clue, now go do it" then I'll go and see if I can do it, but people seem to think it's obvious. – C D Wright May 13 '15 at 11:40
• Look up the fundamental theorem of symmetric polynomials. – Thomas Andrews May 13 '15 at 11:43
• Right, that's what the other answer says, along with "Vieta's formulas", so I guess that's where I need to go and start. It's always a problem, knowing what the magic terms are to get the search started. Thanks for the responses. – C D Wright May 13 '15 at 11:46