I. IntroductionL’idée du raisonnement par récurrence est simple :
« Si on peut se placer sur la 1re marche d’un escalier et si on peut passer d’une marche quelconque à la suivante, alors on peut gravir toutes les marches de l’escalier. »
Une démonstration par récurrence se fait donc en deux étapes :
Première étape : on vérifie que la proposition est vraie pour un certain naturel n0 (généralement 0 ou 1), c’est-à-dire que Pn0 est vraie. Ce qui revient à dire que l’on peut se placer sur la marche n0 d’un escalier représentant l’ensemble des naturels.
Deuxième étape : on suppose que, pour un naturel quelconque n avec n≥n0, la proposition Pn est vraie, et on démontre alors, sous cette hypothèse que la proposition Pn+1 est vraie.
En d’autres termes si on a atteint une marche quelconque alors on est capable de passer à la suivante.
Lorsque ces deux étapes sont réalisées, on admet que la proposition Pn est vraie pour tout naturel n≥n0.
Dans notre cas, on souhaite identifier parmi une suite de termes mathématiques une relation permettant de passer du terme de rang n au suivant, et connaissant la valeur du terme initial, en déduire la valeur d’un terme quelconque.
On veut également obtenir, toujours à l’aide d’un raisonnement par récurrence, la formule générale donnant la valeur du terme de rang n directement à partir de n.
Finalement, la relation de récurrence va nous permettre d’écrire une fonction récursive en Python et la formule générale une fonction itérative.
Note importante : dans notre exemple de sommes d’entiers on part de n=0, mais on peut également partir de n=1 pour aboutir aux mêmes résultats.
On inclut aussi zéro dans l’ensemble des entiers naturels : 0, 1, 2, 3...
II. Somme des premiers entiers naturels
Considérons la suite (Sn) de terme général Sn défini par :
Sn = 0 + 1 + 2 + 3 + ... + n
Il s’agit de la somme des n+1 premiers entiers naturels.
On souhaite déterminer une relation de récurrence permettant de passer de Sn à Sn+1.
Soit donc la suite de sommes partielles :
S0 = 0
S1 = 0 + 1
S2 = 0 + 1 + 2
...
Sn = 0 + 1 + 2 + ... + n
Sn+1 = (0 + 1 + 2 + ... + n) + (n+1)
...
On constate qu’on peut obtenir Sn+1 en ajoutant n+1 à la somme Sn des n+1 premiers naturels.
D’où la relation de récurrence :
Sn+1 = Sn + n+1
Cette relation est donc vraie pour tout entier naturel.
En partant de la 1re "marche" :
S0 = 0
Et en utilisant la relation :
Sn+1 = Sn + n+1
On peut ainsi connaître la valeur de Sn pour tout n≥0.
La somme des n+1 premiers entiers naturels :
Sn = 0 + 1 + 2 + 3 + ... + n
Représente également la somme des n+1 premiers termes d’une suite arithmétique de 1er terme 0 et de raison 1.
Par conséquent, on a :
Sn = 0 + 1 + 2 + 3 + ... + n = (0+n)(n+1)/2
On obtient ainsi la formule générale de la somme :
Sn = n(n+1)/2
On peut également démontrer ce résultat par récurrence en utilisant la relation vue précédemment :
Sn+1 = Sn + n+1
On obtient successivement :
Sn+1 = Sn + n+1
Sn+1 = n(n+1)/2 + n+1
Sn+1 = n(n+1)/2 + 2(n+1)/2
Sn+1 = (n(n+1) + 2(n+1))/2
Sn+1 = (n+1)(n+2)/2
Sn+1 = (n+1)((n+1)+1)/2
Et pour la suite de termes, on a de la même manière :
S0 = 0 = 0(0+1)/2
S1 = 0 + 1 = 1(1+1)/2
S2 = 0 + 1 + 2 = 2(2+1)/2
...
Sn = 0 + 1 + 2 + ... + n = n(n+1)/2
III. Somme à l’ordre k des premiers entiers naturels
Soit la suite (Skn) de terme général Skn tel que :
S0n = n
S1n = 0 + 1 + 2 + ... + n-1 + n
S2n = 0 + (0 + 1) + (0 + 1 + 2) + (0 + 1 + 2 + 3) + ... + (0 + 1 + 2 + 3 + ... + n-1) + (0 + 1 + 2 + 3 + ... + n-1 + n)
...
On obtient ainsi le tableau des sommes à l’ordre 0, 1, 2, ..., k des premiers entiers naturels :
On voit sur le tableau que pour n>0 :
S1n = S1n-1 + n
Ou encore :
S1n = S1n-1 + S0n
On en déduit le terme général pour la somme à l’ordre 0 et pour n>0 :
S0n=n
Note : on étendra par la suite cette propriété à l’ensemble des naturels.
On a également la formule de récurrence à l’ordre 2 :
S2n = S2n-1 + S1n
Et plus généralement à l’ordre k pour n>0 :
Skn = Skn-1 + Sk-1n
Ou encore pour n≥0 :
skn+1 = Skn + Sk-1n+1
Déterminons maintenant la formule générale de Skn :
On obtient ainsi la formule valable pour n≥0 :
Skn = Ck+1n+k = Ak+1n+k / (k+1)!
Avec en particulier pour k=0 :
S0n = n
Note importante : La différence étant l’opération inverse de la somme, on peut représenter les différences successives des sommes à l’aide du schéma :
On voit sur le schéma que la différence arrière entre deux sommes, notée ∇, nous donne :
∇Skn = Skn - Skn-1 = Sk-1n
Et la différence arrière à l’ordre k vaut :
∇kSkn = S0n = n
IV. Implémentation en Python
La fonction récursive somme_ordre_k_v1(k,n) renvoie la somme à l’ordre k des n+1 premiers entiers naturels ou des n premiers entiers non nuls.
Elle se base sur la relation de récurrence :
Skn+1 = Skn + Sk-1n+1
| Code Python : | Sélectionner tout |
1 2 3 4 5 6 7 8 9 10 11 12 | def somme_ordre_k_v1(k,n): # calcul de la somme à l’ordre k des n premiers entiers non nuls égale à la somme des n+1 premiers naturels if k==0: # si l’ordre vaut 0 on renvoie n return n else: # sinon s=0 # initialisation de la somme à l’ordre k for i in range(1,n+1): # parcours des n premiers entiers non nul # appel récursif de la somme à l’ordre k-1 des i premiers entiers non nuls s = s + somme_ordre_k_v1(k-1,i) return s # renvoie de la somme à l’ordre k des n premiers entiers non nuls |
La fonction itérative somme_ordre_k_v2(k,n) renvoie la somme à l’ordre k des n+1 premiers entiers naturels ou des n premiers entiers non nuls.
Elle se base sur la formule générale :
Skn = Ak+1n+k / (k+1)!
| Code Python : | Sélectionner tout |
1 2 3 4 5 6 7 8 9 10 11 12 | def somme_ordre_k_v2(k,n): # calcul de la somme à l’ordre k des n premiers entiers non nuls # formule générale : C(k+1,n+k) = A(k+1,n+k) / (k+1)! # initialisation des variables, a : arrangements de k+1 parmi (n+k), p : permutations de k+1 a=1;p=1 for i in range(k+1): # parcours des ordres de 0 à k a=a*(n+i) # on multiplie a par (n+i) p=p*(i+1) # on multiplie p par (i+1) # on retourne a/p : A(k+1,n+k) / (k+1)! return int(a/p) |
Module de test des fonctions :
| Code Python : | Sélectionner tout |
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 | def somme_ordre_k_v1(k,n): # calcul de la somme à l’ordre k des n premiers entiers non nuls égale à la somme des n+1 premiers naturels if k==0: # si l’ordre vaut 0 on renvoie n return n else: # sinon s=0 # initialisation de la somme à l’ordre k for i in range(1,n+1): # parcours des n premiers entiers non nul # appel récursif de la somme à l’ordre k-1 des i premiers entiers non nuls s = s + somme_ordre_k_v1(k-1,i) return s # renvoie de la somme à l’ordre k des n premiers entiers non nuls def somme_ordre_k_v2(k,n): # calcul de la somme à l’ordre k des n premiers entiers non nuls # formule générale : C(k+1,n+k) = A(k+1,n+k) / (k+1)! # initialisation des variables, a : arrangements de k+1 parmi (n+k), p : permutations de k+1 a=1;p=1 for i in range(k+1): # parcours des ordres de 0 à k a=a*(n+i) # on multiplie a par (n+i) p=p*(i+1) # on multiplie p par (i+1) # on retourne a/p : A(k+1,n+k) / (k+1)! return int(a/p) def generer_somme_ordre_k(k,n): # génère la somme à l’ordre k des n+1 premiers naturels sous la forme pour l’ordre 2 : 0 + (0+1) + (0+1+2) + ... + (0+1+2+...+n) if k==0: # si l’ordre vaut 0 on renvoie n return str(n) else: # sinon s = "(0" for i in range(1, n+1): # parcours des n premiers entiers non nul # appel récursif à l’ordre k-1 : S(k-1,i) s = s + " + " + generer_somme_ordre_k(k-1, i) return s + ")" # test des fonctions k=3 n=3 print("Test des fonctions sommes pour k=" + str(k) + " et n=" + str(n) + " :") print ("") print ("Somme à l’ordre " + str(k) + " des " + str(n) + " premiers entiers non nuls - fonction récursive :") s1 = somme_ordre_k_v1(k,n) # appel de la fonction récursive print ("S(" + str(k) + "," + str(n) + ") = " + str(s1)) print ("") print ("Somme à l’ordre " + str(k) + " des " + str(n) + " premiers entiers non nuls - fonction itérative :") s2 = somme_ordre_k_v2(k,n) # appel de la fonction itérative print ("S(" + str(k) + "," + str(n) + ") = " + "C(" + str(k+1) + "," + str(n+k) + ") = " + str(s2)) print ("") print ("Structure de la somme à l’ordre " + str(k) + " des " + str(n+1) + " premiers entiers naturels (0 compris) :") s = generer_somme_ordre_k(k,n) print ("S(" + str(k) + "," + str(n) + ") = " + s[1:-1]) |
Résultat obtenu :
Test des fonctions sommes pour k=3 et n=3 :
Somme à l’ordre 3 des 3 premiers entiers non nuls - fonction récursive :
S(3,3) = 15
Somme à l’ordre 3 des 3 premiers entiers non nuls - fonction itérative :
S(3,3) = C(4,6) = 15
Structure de la somme à l’ordre 3 des 4 premiers entiers naturels (0 compris) :
S(3,3) = 0 + (0 + (0 + 1)) + (0 + (0 + 1) + (0 + 1 + 2)) + (0 + (0 + 1) + (0 + 1 + 2) + (0 + 1 + 2 + 3))
V. Conclusion
Après avoir présenté le principe du raisonnement par récurrence, nous avons pu l’utiliser pour obtenir une relation permettant de passer d’une somme d’entiers Sn à une somme Sn+1, et ceci pour tout naturel n.
Ce raisonnement nous a également permis de déterminer la formule générale donnant la valeur de la somme Sn en fonction de n.
Nous avons ensuite pu généraliser ces formules à l’ordre k, pour finalement les implémenter en Python.
Sources :
https://fr.wikipedia.org/wiki/Raison...%C3%A9currence
https://en.wikipedia.org/wiki/Mathematical_induction
https://fr.wikipedia.org/wiki/Somme_...emiers_entiers
https://fr.wikipedia.org/wiki/Diff%C3%A9rence_finie