La récurrence est un outil très performant pour démontrer des formules qui dépendent d'un nombre entier. Lorsqu'on l'enseigne on est content si les étudiants en ont compris le principe et savent rédiger correctement une preuve par récurrence. Mais il arrive que des preuves par récurrence sont un peu mécaniques et ont une valeur pédagogique pauvre car elles n'apprennent pas beaucoup sauf à écrire des transformations de termes. Un exemple bien connu est la formule du petit Gauß:

1+2+3+\cdots+n=\frac{n(n+1)}2.

Bien évidemment une preuve par récurrence est possible et je la fais souvent dans mes cours; mais elle n'est pas belle et n'apprend pas grande chose au niveau mathématique. Bien évidemment je présente à mes étudiants aussi la méthode utilisée par le petit Gauß à l'âge de neuf ans. On écrit la somme en montant, puis en descendant; on constate que les deux termes qui se trouvent un au-dessus de l'autre ont toujours la somme n+1 :

Somme petit Gauss

Par conséquence 2S=n(n+1) et la formule est démontrée.

Maintenant je prie mes lecteurs d'aller un peu plus loin en démontrant, toujours sans récurrence, la formule de la somme des nombres cubes:

1^3+2^3+3^3+\cdots+n^3=(1+2+3+\cdots+n)^2.

Indication: On pourra dénombrer les rectangles contenus dans la carré \llbracket0,n\rrbracket\times\llbracket0,n\rrbracket de sorte que les cotés soient parallèles aux axes de coordonnées. Une méthode pour dénombrer consiste à distinguer les rectangles selon la position du sommet nord-est par rapport à la diagonale du carré.

grille

D'ailleurs je serais intéressé de connaître une preuve combinatoire pour la somme des nombres carrés.
Autre remarque: C'est un exercice classique de prépa de déduire de la formule du petit Gauß la formule pour la somme des nombres carrés, puis déduire de la formule de la somme des nombres carrés celle de la somme des nombres cubes, etc. C'est-à-dire, on établit de manière récursive la formule avec exposant r à partir de celle avec exposant r-1.