« Maths, Informatique, Jeux » - Sommes de N entiers élevés à une certaine puissance

1) On peut le démontrer facilement en calculant le double et en montrant que

2 \times \sum_{i = 1}^{N} i = N (N + 1)

2 × (1 + 2 + 3 + ... + (N - 2) + (N - 1) + N) =
1 + 2 + 3 + ... + (N - 2) + (N - 1) + N +
N + (N - 1) + (N - 2) + ... 3 + 2 + 1 =
[1 + N] + [2 + (N - 1)] + [3 + (N - 2)] ... + [(N - 2) + 3] + [(N - 1) + 2] + [N + 1] = N(N + 1)
Et en divisant par 2, on trouve (1 + 2 + 3 + 4 + ... + N) =

\frac{N (N + 1)}{2} = \frac{1}{2} N^{2} + \frac{1}{2} N

2) On peut aussi le démontrer par récurrence : Au rang 1,

\frac{N (N + 1)}{2} = \frac{1 (1 + 1)}{2} = 1

. Si la propriété est vraie à un rang N, alors

\sum_{i = 1}^{N + 1} i = \frac{N (N + 1)}{2} + (N + 1) = \frac{(N + 1) (N + 2)}{2} = \frac{(N + 1) ((N + 1) + 1)}{2}

et la propriété est vraie au rang N + 1.

Somme des carrés des N premiers entiers

Proposition

Démonstration

Pour démontrer cela, on va utiliser une autre méthode, qui aurait aussi bien pu être utilisé précedemment. On sait que

{(X + 1)}^{3} = X^{3} + 3 X^{2} + 3 X + 1

. Observons alors ces égalités :

{(1 + 1)}^{3} = 1^{3} + 3 \times 1^{2} + 3 \times 1 + 1

{(2 + 1)}^{3} = 2^{3} + 3 \times 2^{2} + 3 \times 2 + 1

{(3 + 1)}^{3} = 3^{3} + 3 \times 3^{2} + 3 \times 3 + 1

{(4 + 1)}^{3} = 4^{3} + 3 \times 4^{2} + 3 \times 4 + 1

...

{(N + 1)}^{3} = N^{3} + 3 \times N^{2} + 3 \times N + 1

En additionnant tous les membres, on en déduit :

\sum_{i = 2}^{N} i^{3} + {(N + 1)}^{3} = 1 + \sum_{i = 2}^{N} i^{3} + 3 \times \sum_{i = 1}^{N} i^{2} + 3 \times \sum_{i = 1}^{N} i + N

(N^{3} + 3 \times N^{2} + 3 \times N + 1) = 1 + 3 \times \sum_{i = 1}^{N} i^{2} + 3 \times \frac{N (N + 1)}{2} + N

3 \times \sum_{i = 1}^{N} = N^{3} + \frac{3}{2} N^{2} + \frac{1}{2} N

\sum_{i = 1}^{N} i^{2} = \frac{1}{3} N^{3} + \frac{1}{2} N^{2} + \frac{1}{6} N

Cqfd

Cas général

Rappels

Proposition

\sum_{i = 1}^{M} i^{N - 1} = \frac{1}{N} \times (\sum_{i = 1}^{N} (\begin{matrix} N \\ i \end{matrix}) M^{i} - \sum_{i = 0}^{N - 2} (\begin{matrix} N \\ i \end{matrix}) \sum_{j = 1}^{M} j^{i})

ou encore

\sum_{i = 1}^{M} i^{N} = \frac{1}{N + 1} \times (\sum_{i = 1}^{N + 1} (\begin{matrix} N + 1 \\ i \end{matrix}) M^{i} - \sum_{i = 0}^{N - 1} (\begin{matrix} N + 1 \\ i \end{matrix}) \sum_{j = 1}^{M} j^{i})

Démonstration

\sum_{i = 1}^{M} {(i + 1)}^{N} = \sum_{i = 1}^{M} \sum_{j = 0}^{N} (\begin{matrix} N \\ j \end{matrix}) i^{j} 1^{N - j}

\sum_{i = 2}^{M} i^{N} + {(M + 1)}^{N} = \sum_{i = 1}^{M} (\sum_{j = 0}^{N - 2} (\begin{matrix} N \\ j \end{matrix}) i^{j} + (\begin{matrix} N \\ N - 1 \end{matrix}) i^{N - 1} + (\begin{matrix} N \\ N \end{matrix}) i^{N})

\sum_{i = 2}^{M} i^{N} + \sum_{i = 0}^{N} (\begin{matrix} N \\ i \end{matrix}) M^{i} 1^{N - i} = \sum_{i = 1}^{M} \sum_{j = 0}^{N - 2} (\begin{matrix} N \\ j \end{matrix}) i^{j} + \sum_{i = 1}^{M} N \times i^{N - 1} + \sum_{i = 1}^{M} i^{N}

\sum_{i = 2}^{M} i^{N} + (\begin{matrix} N \\ 0 \end{matrix}) M^{0} + \sum_{i = 1}^{N} (\begin{matrix} N \\ i \end{matrix}) M^{i} = \sum_{i = 1}^{M} \sum_{j = 0}^{N - 2} (\begin{matrix} N \\ j \end{matrix}) i^{j} + N \times \sum_{i = 1}^{M} i^{N - 1} + 1 + \sum_{i = 2}^{M} i^{N}

\sum_{i = 1}^{N} (\begin{matrix} N \\ i \end{matrix}) M^{i} = \sum_{i = 1}^{M} \sum_{j = 0}^{N - 2} (\begin{matrix} N \\ j \end{matrix}) i^{j} + N \times \sum_{i = 1}^{M} i^{N - 1}

\sum_{i = 1}^{M} i^{N - 1} = \frac{1}{N} (\sum_{i = 1}^{N} (\begin{matrix} N \\ i \end{matrix}) M^{i} - \sum_{i = 1}^{M} \sum_{j = 0}^{N - 2} (\begin{matrix} N \\ j \end{matrix}) i^{j})

\sum_{i = 1}^{M} i^{N - 1} = \frac{1}{N} (\sum_{i = 1}^{N} (\begin{matrix} N \\ i \end{matrix}) M^{i} - \sum_{j = 0}^{N - 2} (\begin{matrix} N \\ j \end{matrix}) \sum_{i = 1}^{M} i^{j})

On retrouve alors notre première formule en inversant les rôles de i et j dans la dernière partie, et la seconde en remplaçant N par N + 1.

Remarques supplémentaires

Les calculs de

\frac{1}{N}

et de

\sum_{i = 1}^{N} (\begin{matrix} N \\ i \end{matrix}) M^{i}

ne posent pas de problème.
Par contre, pour trouver

\sum_{i = 0}^{N - 2} (\begin{matrix} N \\ i \end{matrix}) \sum_{j = 1}^{M} j^{i}

il faut connaitre

\sum_{j = 1}^{M} j^{i}

pour j variant de 0 à N - 2, c'est à dire avoir trouvé auparavant, les formules donnant la somme des N premiers entiers, des M premiers entiers élevés au carré, au cube, à la puissance 4, et ainsi de suite, jusqu'à la puissance N - 2.
On trouve alors

\sum_{i = 1}^{M} i^{N - 1}

autrement dit la somme des M premiers entiers élevés à la puissance N - 1.
Une petite astuce permettant de vérifier que le polynôme est correct :

Si a₁, a₂, a₃, ... ,a_N sont les coefficients du polynôme trouvé, alors on a :
a₁ M¹ + a₂ M² + a₃ M³ + ... + a_N M^N = 1^{(N - 1)} + 2^{(N - 1)} + 3^{(N - 1)} + ... + M^{(N - 1)}
donc pour M = 1, a₁ 1¹ + a₂ 1² + a₃ 1³ + ... + a_N 1^N = 1^{(N - 1)}, c'est-à-dire a₁ + a₂ + a₃ + ... + a_N = 1

La somme des coefficients du polynôme obtenu est égale à 1 !
Remarquons encore que

a^{N} = \frac{1}{M}

, il suffit de regarder la formule pour le comprendre.

Sommaire

Somme des N premiers entiers

Rappel

Proposition

Démonstrations

Somme des carrés des N premiers entiers

Proposition

Démonstration

Cas général

Rappels

Proposition

Démonstration

Remarques supplémentaires

Calculer les formules à l'aide de votre ordinateur