IdentifiantMot de passe
Loading...
Mot de passe oublié ?Je m'inscris ! (gratuit)
Voir le flux RSS

User

[Actualité] Raisonnement par récurrence et programmation

Note : 3 votes pour une moyenne de 3,67.
par , 08/11/2022 à 11h54 (16583 Affichages)
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. »

Nom : escalier.png
Affichages : 7644
Taille : 16,3 Ko

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 :

Nom : tableau_sommes_ordre_k.png
Affichages : 5294
Taille : 17,4 Ko

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 :

Nom : tableau_formule_generale.png
Affichages : 5412
Taille : 35,0 Ko

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 :

Nom : schema_differences.png
Affichages : 5494
Taille : 5,1 Ko

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 - Visualiser dans une fenêtre à part
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 - Visualiser dans une fenêtre à part
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 - Visualiser dans une fenêtre à part
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

Envoyer le billet « Raisonnement par récurrence et programmation » dans le blog Viadeo Envoyer le billet « Raisonnement par récurrence et programmation » dans le blog Twitter Envoyer le billet « Raisonnement par récurrence et programmation » dans le blog Google Envoyer le billet « Raisonnement par récurrence et programmation » dans le blog Facebook Envoyer le billet « Raisonnement par récurrence et programmation » dans le blog Digg Envoyer le billet « Raisonnement par récurrence et programmation » dans le blog Delicious Envoyer le billet « Raisonnement par récurrence et programmation » dans le blog MySpace Envoyer le billet « Raisonnement par récurrence et programmation » dans le blog Yahoo

Mis à jour 22/11/2022 à 14h34 par User

Catégories
Programmation , Python , Algorithmique

Commentaires

  1. Avatar de web bea
    • |
    • permalink
    Merci pour ce rappel sur le raisonnement par récurrence.
    Toutefois je souhaiterais préciser un point sur la définition que tu donnes :

    Lorsque ces deux étapes sont réalisées, on admet sans démonstration que la proposition Pn est vraie pour tout naturel n≥n0.
    Le principe du raisonnement par récurrence c'est que si on a démontré que P(n0) est vraie et que P(n) entraine P(n+1) alors on a démontré que P(n) était vraie pour tout entier naturel n >= n0
    Du coup l'emploi de l'expression "on admet sans démonstration" alors que l'on vient précisément de fournir une démonstration ne me paraît pas vraiment approprié


    Il convient aussi de mentionner que tout problème qui possède une solution récursive possède aussi une solution itérative (et réciproquement).
    Ainsi une fonction python récursive peut toujours être réécrite sous une forme purement itérative (ça ne sera pas forcément simple à faire, mais en tout cas c'est toujours faisable).
  2. Avatar de User
    • |
    • permalink
    C'est vrai que le mot est en trop, je n'avais pas vérifié, je te remercie, je corrige