오늘의 계산 ?? - A Recurrence Relation

Today I want to deal with a problem which does not lie in analysis. It would be easy for those who are adapted to algebra, but for those with algebra trauma like me, it was rather a challenge.

Problem. Let $m$ be an integer and $(u_n)$ be a sequence defined by \begin{equation}\label{eqn:recur} u_0 = 1, \quad u_1 = m \quad \text{and} \quad u_{n+2} = mu_{n+1} + u_n. \end{equation} Prove that

1. for any prime $p$ not dividing $m^2 + 4$, we have $p \mid u_{p-2}u_p$, and
2. for any prime $p$ dividing $m^2 + 4$, we have $p \mid u_{p-2}u_{p}+1$.

Proof. We first prove the part 1. If $p = 2$, then $p$ does not divide $m^2 + 4$ if and only if $m$ is odd. For odd $m$, we find that $u_{p-2}u_{p} = u_0 u_2 = m^2 + 1$ is divisible by $2$, proving the claim for $p = 2$.

Now assume $p > 2$ is an odd prime. Let $\phi(x) = x^2 - mx - 1$ be the characteristic polynomial of the recurrence relation \eqref{eqn:recur}. In $\bar{\Bbb{F}}_p$, it has a double zero if and only if $\phi(x) = 0$ and $\phi'(x) = 0$ has common zero. But since $\phi'(x) = 2x - m$, this is equivalent to say that $\phi(\frac{m}{2}) = 0$, which is again equivalent to $m^2 + 4 = 0$. Thus if $p$ does not divide $m^2 + 4$, $\phi(x)$ has distinct zero in $\bar{\Bbb{F}}_p$.

Let $\alpha$ and $\beta$ be two distinct zeros of $\phi(x)$ in $\bar{\Bbb{F}}_p$. They are elements of $\Bbb{F}_p(\alpha)$, which is either $\Bbb{F}_p$ itself or ites degree 2 extension. Then standard theory of recurrence relation shows that the general term of $(u_n)$ is of the form

$$ u_n = A \alpha^n + B \beta^n. $$

Comparing with the initial condition $u_0 = 1$ and $u_1 = m = \alpha + \beta$, we have

\begin{equation}\label{eqn:gen_term} u_n = \frac{\beta^{n+1} - \alpha^{n+1}}{\beta - \alpha}. \end{equation}

Also, since $\alpha + \beta = m$ and $\alpha \beta = -1$, we have

$$ \frac{\beta}{\alpha} + \frac{\alpha}{\beta} = \frac{(\alpha+\beta)^2}{\alpha\beta} - 2 = -m^2-2$$

and hence

$$ \beta^2 + (m^2+2)\alpha\beta + \alpha^2 = 0.$$

Now we are ready. Plugging \eqref{eqn:gen_term} to $u_{p-2}u_p$, we have

\begin{align*}u_{p-2}u_p &= \frac{\beta^{p-1} - \alpha^{p-1}}{\beta - \alpha} \cdot \frac{\beta^{p+1} - \alpha^{p+1}}{\beta - \alpha} \\ &= \frac{\beta^{2p} + (m^2+2)\alpha^p\beta^p + \alpha^{2p}}{(\beta - \alpha)^2} \\ &= \frac{\left(\beta^2 + (m^2+2)\alpha\beta + \alpha^2\right)^p}{(\beta - \alpha)^2} = 0. \end{align*}

Here, we have used the fact that the mapping $x \mapsto x^p$ is an automorphism on $\Bbb{F}_p(\alpha)$ which fixes $\Bbb{F}_p$. Therefore $p$ divides $u_{p-2}u_p$.

Now we prove the part 2. We deal with the case $p = 2$ separately. Assume that $2$ divides $m^2 + 4$. Then $m$ is even. Then $u_{n+2} \equiv u_n \ (\mathrm{mod} \ 2)$. Since $u_0 = 1$, this implies $u_{2n} \equiv 1 \ (\mathrm{mod} \ 2)$. Thus the conclusion follows for $p = 2$.

Thus it suffices to consider odd prime $p$ only. In part 1, we found that $p$ divides $m^2 + 4$ if and only if $\phi(x)$ has a double zero in $\bar{\Bbb{F}}_p$, namely $\alpha = \frac{m}{2}$. Then the standard theory of recurrence relation shows that $(u_n)$ is of the form

$$ u_n = (an+b)\alpha^n. $$

Again, comparing with the initial condition $u_0 = 1$ and $u_1 = 2\alpha$, we find that

\begin{equation}\label{eqn:gen_term2} u_n = (n+1)\alpha^n \end{equation}

in $\Bbb{F}_p$. Therefore we have

$$ u_{p-2}u_{p} = (p-1)\alpha^{p-2} \cdot (p+1)\alpha^{p} = (p^2-1)\alpha^{2p-2} = -1, $$

where we have used the Fermat's little theorem to obtain $\alpha^{p-1} = 1$. Therefore the conclusion follows.

Any alternative proof that only uses elementary number theory would be greatly appreciated!

References

1. A hard sequence. in "AoPS Forum"