Mathématiques et Python - Raisonnement par récurrence et programmation

Un billet blog de Denis Hulo

I. Introduction

L’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. »

628570

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 :

628519

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 :

628544

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 :

628482

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

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)!

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 :

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/Raisonnement_par_r%C3%A9currence
https://en.wikipedia.org/wiki/Mathematical_induction
https://fr.wikipedia.org/wiki/Somme_(arithm%C3%A9tique)#Somme_des_premiers_entiers
https://fr.wikipedia.org/wiki/Diff%C3%A9rence_finie