Shortlist 2009, N6¶

Domaine : Théorie des nombres · Difficulté : ★★★★☆ · Proposé par : Turkey

Concepts : Polynômes à coefficients entiers · Congruences, théorèmes de Fermat et d'Euler · Suites et récurrences

Solution officielle : Shortlist officielle 2009 (avec solutions), p. 78 (page 80 du PDF)

Énoncé¶

Let $k$ be a positive integer. Show that if there exists a sequence $a_0, a_1, \ldots$ of integers satisfying the condition

\[a_n = \frac{a_{n-1} + n^k}{n} \qquad \text{for all } n \geq 1,\]

then $k - 2$ is divisible by $3$.

Indices : les idées clés

Polynôme auxiliaire : il existe $P_k \in \mathbb{Z}[x]$ et un entier $q_k$ tels que $xP_k(x) = x^k + P_k(x - 1) + q_k$.
Récurrence résolue : $a_n - P_k(n) = \frac{a_0 - P_k(0)}{n!} - q_k\sum_{i=0}^{n-1}\frac{i!}{n!}$, donc des $a_n$ entiers imposent $q_k = 0$.
Réduction modulo $2$ : $q_{k+2} \equiv q_{k+1} + q_k \pmod 2$ avec $q_1 = -1$, $q_2 = 0$ ; ou bien (solution 2) on évalue l'identité dans le corps $\mathbb{F}_4$, d'où $(\alpha + 1)^{k-1} = \alpha^k$.

Solutions

Les solutions ci-dessous suivent les solutions officielles de la Shortlist 2009 (deux solutions et trois remarques).

Solution 1¶

Partie A. Pour tout entier $k > 0$, il existe un polynôme $P_k$ de degré $k - 1$ à coefficients entiers, c'est-à-dire $P_k \in \mathbb{Z}[x]$, et un entier $q_k$ tels que l'identité polynomiale

\[xP_k(x) = x^k + P_k(x - 1) + q_k \tag{$I_k$}\]

soit vérifiée. Pour le prouver, pour $k$ fixé, on écrit

\[P_k(x) = b_{k-1}x^{k-1} + \cdots + b_1x + b_0\]

et l'on détermine successivement les coefficients $b_{k-1}, b_{k-2}, \ldots, b_0$ et le nombre $q_k$. Évidemment, $b_{k-1} = 1$. Pour $m = k - 1, k - 2, \ldots, 1$, l'identification des coefficients de $x^m$ dans l'identité $(I_k)$ donne une expression de $b_{m-1}$ comme combinaison linéaire entière de $b_{k-1}, \ldots, b_m$, et enfin $q_k = -P_k(-1)$.

Partie B. Soit $k$ un entier strictement positif, et soit $a_0, a_1, \ldots$ une suite de réels vérifiant la récurrence de l'énoncé. Cette récurrence peut s'écrire

\[a_n - P_k(n) = \frac{a_{n-1} - P_k(n - 1)}{n} - \frac{q_k}{n} \qquad \text{pour tout } n \geq 1,\]

ce qui donne, par récurrence,

\[a_n - P_k(n) = \frac{a_0 - P_k(0)}{n!} - q_k\sum_{i=0}^{n-1}\frac{i!}{n!} \qquad \text{pour tout } n \geq 1.\]

Les nombres $a_n$ ne sont donc entiers pour tout $n \geq 1$ que si

\[a_0 = P_k(0) \qquad \text{et} \qquad q_k = 0.\]

Partie C. En multipliant l'identité $(I_k)$ par $x^2 + x$ et en lui retranchant les identités $(I_{k+1})$, $(I_{k+2})$ et $q_kx^2 = q_kx^2$, on obtient

\[xT_k(x) = T_k(x - 1) + 2x\big(P_k(x - 1) + q_k\big) - (q_{k+2} + q_{k+1} + q_k),\]

où les polynômes $T_k \in \mathbb{Z}[x]$ sont définis par $T_k(x) = (x^2 + x)P_k(x) - P_{k+1}(x) - P_{k+2}(x) - q_kx$. Donc

\[xT_k(x) \equiv T_k(x - 1) + q_{k+2} + q_{k+1} + q_k \pmod 2, \qquad k = 1, 2, \ldots\]

En comparant les degrés, on voit facilement que cela n'est possible que si $T_k$ est le polynôme nul modulo $2$, et

\[q_{k+2} \equiv q_{k+1} + q_k \pmod 2 \qquad \text{pour } k = 1, 2, \ldots\]

Comme $q_1 = -1$ et $q_2 = 0$, ces congruences terminent la preuve : $q_k$ est pair exactement quand $k \equiv 2 \pmod 3$. $\blacksquare$

Solution 2¶

Parties A et B. Soit $k$ un entier strictement positif, et supposons qu'il existe une suite $a_0, a_1, \ldots$ comme voulu. Montrons qu'il existe un polynôme $P \in \mathbb{Z}[x]$, c'est-à-dire à coefficients entiers, tel que $a_n = P(n)$, $n = 0, 1, \ldots$, et $xP(x) = x^k + P(x - 1)$.

Pour le prouver, on écrit $P(x) = b_{k-1}x^{k-1} + \cdots + b_1x + b_0$ et l'on détermine successivement les coefficients $b_{k-1}, b_{k-2}, \ldots, b_0$ de sorte que

\[xP(x) - x^k - P(x - 1) = q,\]

où $q = q_k$ est un entier. L'identification des coefficients de $x^m$ donne une expression de $b_{m-1}$ comme combinaison linéaire entière de $b_{k-1}, \ldots, b_m$.

En posant $c_n = a_n - P(n)$, on obtient

\[P(n) + c_n = \frac{P(n - 1) + c_{n-1} + n^k}{n}, \qquad \text{c'est-à-dire} \qquad q + nc_n = c_{n-1},\]

donc

\[c_n = \frac{c_0}{n!} - q \cdot \frac{0! + 1! + \cdots + (n - 1)!}{n!}.\]

On en conclut que $\lim_{n \to \infty} c_n = 0$, ce qui, avec $c_n \in \mathbb{Z}$, implique $c_n = 0$ pour $n$ assez grand. On obtient donc $q = 0$ et $c_n = 0$, $n = 0, 1, \ldots$

Partie C. Supposons $q = q_k = 0$, c'est-à-dire $xP(x) = x^k + P(x - 1)$. Pour considérer cette identité en des arguments $x \in \mathbb{F}_4$, on écrit $\mathbb{F}_4 = \{0, 1, \alpha, \alpha + 1\}$. On obtient alors

\[\alpha P_k(\alpha) = \alpha^k + P_k(\alpha + 1) \qquad \text{et} \qquad (\alpha + 1)P_k(\alpha + 1) = (\alpha + 1)^k + P_k(\alpha),\]

donc

\[\begin{aligned} P_k(\alpha) = 1 \cdot P_k(\alpha) = (\alpha + 1)\alpha P_k(\alpha) &= (\alpha + 1)P_k(\alpha + 1) + (\alpha + 1)\alpha^k \\ &= P_k(\alpha) + (\alpha + 1)^k + (\alpha + 1)\alpha^k. \end{aligned}\]

Or $(\alpha + 1)^{k-1} = \alpha^k$ implique $k \equiv 2 \pmod 3$ (car $\alpha + 1 = \alpha^2$ et $\alpha^3 = 1$). $\blacksquare$

Remarques¶

Remarque 1. Pour $k = 2$, la suite donnée par $a_n = n + 1$, $n = 0, 1, \ldots$, vérifie les conditions du problème.

Remarque 2. Les premiers polynômes $P_k$ et entiers $q_k$ sont

\[\begin{aligned} &P_1(x) = 1, \quad q_1 = -1, \\ &P_2(x) = x + 1, \quad q_2 = 0, \\ &P_3(x) = x^2 + x - 1, \quad q_3 = 1, \\ &P_4(x) = x^3 + x^2 - 2x - 1, \quad q_4 = -1, \\ &P_5(x) = x^4 + x^3 - 3x^2 + 5, \quad q_5 = -2, \\ &P_6(x) = x^5 + x^4 - 4x^3 + 2x^2 + 10x - 5, \quad q_6 = 9, \\ &q_7 = -9, \quad q_8 = -50, \quad q_9 = 267, \quad q_{10} = -413, \quad q_{11} = -2180. \end{aligned}\]

Une recherche dans l'Encyclopédie en ligne des suites d'entiers (A000587) révèle que la suite $q_1, -q_2, q_3, -q_4, q_5, \ldots$ est connue sous le nom de nombres d'Uppuluri-Carpenter. Le résultat selon lequel $q_k = 0$ implique $k \equiv 2 \pmod 3$ figure dans Murty, Summer : On the $p$-adic series $\sum_{n=0}^{\infty} n^k \cdot n!$, CRM Proc. and Lecture Notes 36, 2004. Comme l'a montré Alexander (Non-Vanishing of Uppuluri-Carpenter Numbers, prépublication, 2006), les nombres d'Uppuluri-Carpenter s'annulent au plus deux fois.

Remarque 3. Les nombres $q_k$ s'écrivent à l'aide des nombres de Stirling de seconde espèce. Pour le montrer, on fixe les notations de sorte que

\[x^k = S_{k-1,k-1}x(x - 1) \cdots (x - k + 1) + S_{k-1,k-2}x(x - 1) \cdots (x - k + 2) + \cdots + S_{k-1,0}x, \tag{$*$}\]

par exemple $S_{2,2} = 1$, $S_{2,1} = 3$, $S_{2,0} = 1$, et l'on pose

\[\Omega_k = S_{k-1,k-1} - S_{k-1,k-2} + - \cdots.\]

En remplaçant $x$ par $-x$ dans $(*)$, on obtient

\[x^k = S_{k-1,k-1}x(x + 1) \cdots (x + k - 1) - S_{k-1,k-2}x(x + 1) \cdots (x + k - 2) + - \cdots \pm S_{k-1,0}x.\]

En définissant

\[\begin{aligned} P(x) = {} &S_{k-1,k-1}(x + 1) \cdots (x + k - 1) + (S_{k-1,k-1} - S_{k-1,k-2})(x + 1) \cdots (x + k - 2) \\ &+ (S_{k-1,k-1} - S_{k-1,k-2} + S_{k-1,k-3})(x + 1) \cdots (x + k - 3) + \cdots + \Omega_k, \end{aligned}\]

on obtient

\[xP(x) - P(x - 1) = S_{k-1,k-1}x(x + 1) \cdots (x + k - 1) - S_{k-1,k-2}x(x + 1) \cdots (x + k - 2) + - \cdots \pm S_{k-1,0}x - \Omega_k = x^k - \Omega_k,\]

d'où $q_k = -\Omega_k$.