Raisonnement par récurrence ? Un escalier ! (4/4)

Dans ce dernier article de la série sur les suites, on va parler de raisonnement par récurrence. Tu le sais déjà, mais c'est le type de démonstration qu'on utilise majoritairement pour montrer qu'une suite a telle ou telle propriété

En effet, quand on ne connaît pas le terme général d'une suite, il est impossible de montrer directement des propriétés. Par contre, on peut le faire grâce au raisonnement par récurrence, qui comme son nom l'indique, va faire intervenir la formule de récurrence de la suite.

Dans cet article, je t'explique pourquoi un escalier est le moyen mnémotechnique parfait pour comprendre comment fonctionne le raisonnement par récurrence. Je ne l'ai pas inventé... Mon prof de Maths du lycée l'utilisait et on dirait que ça a bien fonctionné pour moi 😉 !

Si t'as pas encore lu les autres articles de la série, c'est le moment ! 

Le raisonnement par récurrence est)il juste une histoire d'escalier ?

La récurrence, une histoire d'escalier ?

Oui, un escalier, tu as bien lu ! Si tu peux monter sur la première marche de l'escalier et que tu sais passer d'une marche à l'autre, alors tu pourras monter tout l'escalier... même s'il est infini !

L'escalier, c'est la propriété que tu veux démontrer. Donc si tu peux monter l'escalier, la propriété est vraie pour tous les rangs. Si c'est pas encore clair pour toi, reste concentré, ça va s'éclaircir !

Une bonne manière de comprendre le principe.

Pour montrer grâce au raisonnement par récurrence une propriété sur une suite, tu dois montrer que cette propriété est vraie au rang 0 et qu'elle reste vraie quand tu passes du rang n au rang n+1.

Donc si tu fais l'analogie entre ‹‹ poser le pied sur une marche ›› et ‹‹ la propriété est vérifiée ››, tu vois que le raisonnement par récurrence, c'est montrer que tu sais "monter sur la première marche de l'escalier" et que tu sais aussi "passer d'une marche à la suivante".

Comprendre le raisonnement par récurrence grâce à un escalier !

En conséquence, la démonstration ne marche pas quand...

Avec ça en tête, impossible d'oublier le principe de démonstration par récurrence ! Tu vois tout de suite, que si tu n'es pas capable d'atteindre la première marche, tu ne pourras pas monter l'escalier et la propriété que tu regardes ne sera donc pas vraie.

De la même façon, si tu sais monter sur la première marche mais que tu ne sais pas passer d'une marche à l'autre, tu ne pourras pas monter l'escalier. Autrement dit, tu ne pourras pas démontrer que la propriété est vraie pour tous les rangs...

Les 3 étapes du raisonnement par récurrence

Les 3 étapes du raisonnement par récurrence.

Bon, le truc de l'escalier c'est pratique pour te rappeler du principe... Mais ça te dit pas comment faire une démonstration par récurrence dans les exercices !

Alors maintenant on passe à la pratique, et ça se fait en 3 étapes. Pour illustrer ce que je te raconte, je vais utiliser la suite définie par récurrence par :

Définition de la Suite exemple

Et on va démontrer ensemble la propriété suivante est vérifiée pour tout n entier naturel :

Définition de la propriété exemple

Étape 1. Peut-on monter sur la première marche ? (Initialisation)

Comme dans la vraie vie, tu vas devoir commencer par monter sur la première marche de l'escalier ! C'est-à-dire que tu vas devoir montrer que la propriété est vraie pour le terme initial U_0 de ta suite.

En général, c'est rare qu'il faille vraiment réfléchir pour montrer que P_0 est vraie. Dans mon exemple c'est très clair, U_0 = 0 et n/(n+1) = 0/(0+1) = 0 donc U_0 = 0/(0+1). Autrement dit, P_0 est vraie.

La seule chose qu'il y a besoin d'avoir assimiler est la différence entre n en tant qu'indice de la suite et n en tant que nombre dans les formules. Si t'es pas certain de toi sur ça, vas relire le premier article de cette série !


Étape 2. Peut-on passer d'une marche à la suivante ? (Hérédité)

La deuxième partie du raisonnement par récurrence consiste à vérifier que tu sais passer d'une marche à la suivante. Autrement dit, à montrer que si la propriété est vraie au rang n, elle reste vraie quand tu passes au rang n+1. Et ce sera toujours la partie la plus difficile de la démonstration !

Pour autant, l'idée est simple : tu considères que P_n est vraie et tu te débrouilles pour arriver à P_{n+1} vraie en utilisant la formule de récurrence de la suite. Il y a 2 manières possibles de t'y prendre :

  • Méthode 1 : ‹‹ de P_n à P_{n+1} ››
    Tu pars en écrivant P_n (qui contient U_n) et tu enchaînes les opérations qui permettent de passer de U_n à U_{n+1}. Une fois que tu es arrivé à U_{n+1}, tu vérifies que tu as bien P_{n+1} !
  • Méthode 2 : ‹‹ de U_{n+1} à P_{n+1} ››
    Là, tu pars de la formule de récurrence qui donne U_{n+1} en fonction de U_n et tu remplaces U_n par ce que te donne P_n. Puis tu vérifies que tu as bien obtenu P_{n+1} !

Suivant la situation, l'une peut être bien plus simple que l'autre. Dans l'exemple que j'ai choisi ici, c'est assez équivalent comme tu peux le voir ci-dessous. Par contre, dans l'exemple que j'ai mis dans la Fiche Récap, c'est bien plus simple en utilisant la méthode 1.

Exemple d'hérédité dans un raisonnement par récurrence

Démonstration de l'hérédité pour l'exemple considéré avec les 2 méthodes. (Clique pour zoomer)


Étape 3. On sait monter l'escalier ! (Conclusion)

Pour finir, il ne faut pas oublier de conclure ! C'est pour ça que je l'ai mis en tant qu'étape alors qu'en fait c'est juste une phrase. Mais si tu ne conclues pas, tu n'auras pas tous les points...

Mais au fait, pourquoi est-ce qu'on a démontré que c'était vrai pour tout entier naturel plus grand que le rang initial ??? 

Eh bien, parce qu'on a montré qu'on savait monter sur l'escalier et passer d'une marche à l'autre. Autrement dit, la propriété est vraie pour U_0 et elle est aussi vraie pour U_1 grâce à l'hérédité et elle est donc aussi vraie pour U_2 grâce à l'hérédité et elle est donc aussi vraie pour U_3 grâce à l'hérédité... T'as compris le truc !

Enfin pas besoin d'être créatif dans la rédaction pour cette étape. Contente-toi d'une simple phrase du type : "On a montré que P_0 est vraie et que P_{n+1} est vraie si P_n est vraie, donc la propriété P_n est vraie pour tout entier naturel n supérieur à 0.".


Remarque : J'ai tout fait ici avec 0 comme rang initial. Évidemment, si on te demande de montrer une propriété pour tout n entier naturel plus grand que 10, tu devras faire l'étape 1 avec U_{10} ! Et ta conclusion sera que la propriété est vraie pour tout n plus grand que 10. En gros, le numéro de la première marche de l'escalier dépend du contexte.

Retrouve un autre exemple complet dans la Fiche Récap. basé sur cette suite mais pour une propriété différente.

Comment ne pas mélanger les arguments

Comment y arriver à tous les coups ?

Comme je viens de te le dire, démontrer l'hérédité est toujours la partie la plus difficile. Et la raison principale est qu'il est facile de t'emmêler les pinceaux entre ce que tu sais, ce que tu supposes vrai et ce que tu veux. Alors j'ai décidé de te donner une méthode toute simple pour que ça n'arrive pas !

Tu dois bien avoir compris ce que je t'ai raconté plus haut sur le raisonnement par récurrence pour que ce qui suive te soit utile. Donc si ce n'est pas le cas, prends le temps de relire et/ou de me poser des questions dans les commentaires !

➫ Ce que tu sais, ce que tu supposes vrai et ce que tu veux.

Alors, comment avoir l'esprit super clair quand tu attaques l'étape "hérédité" de ton raisonnement par récurrence ? En utilisant ton brouillon à fond ! Pour ça, tu vas y noter toutes les informations importantes dans les 3 catégories suivantes :

  • Ce que tu sais : 
    Là tu trouves toutes les informations dont tu es absolument sûr. C'est à cette catégorie que la formule de récurrence de la suite appartient. Mais n'oublie pas de prendre aussi en compte les autres informations de l'énoncé ou par exemple, les propriétés que tu as démontré sur la suite dans les questions précédentes.
  • Ce que tu supposes vrai :
    Ici il n'y a qu'une seule chose : la propriété P_n. C'est la base de cette étape. Tu vas pouvoir utiliser cette information comme si elle était vraie, même si en fait tu n'en sais rien ! C'est comme si on t'avait téléporté sur une marche de l'escalier sans être passé par les précédentes...
  • Ce que tu veux :
    Enfin, il faut que tu notes ce que tu veux obtenir à la fin pour pouvoir dire que l'hérédité est vérifiée. Et il n'y a qu'une seule chose que tu veux obtenir : P_{n+1} vraie. Donc écris sur ton brouillon ce qu'est P_{n+1}.

En faisant cela, tu auras sous les yeux ce que tu peux utiliser et ce que tu veux obtenir. Il ne te restera qu'à les relier ! Et écrire est la meilleure façon de donner les moyens à ton cerveau de trouver le chemin.

➫ Démo sur notre exemple !

Pour que tout soit bien clair, voici ce que ça donne dans le cas de notre exemple :

  • Ce que tu sais :                 U_{n+1} = 1/(2-U_n)          (formule de récurrence)
  • Ce que tu supposes vrai : U_n = n/(n+1)                (propriété P_n)
  • Ce que tu veux :                U_{n+1} = (n+1)/(n+2) (propriété P_{n+1})

Donc si tu utilises la Méthode 1, tu vois que tu vas partir de ce que tu supposes vrai et que tu vas utiliser ce que tu sais. Alors que si tu utilises la Méthode 2, tu pars de ce que tu sais et tu utilises ce que tu supposes vrai. Dans tous les cas, il te reste à faire quelques calculs pour arriver à ce que tu veux.

Et le fait d'avoir sous les yeux ce que tu veux obtenir va te rendre les choses plus simples. En effet, c'est toujours plus facile de trouver quels calculs ou simplifications faire quand tu sais à quoi tu veux arriver ! 

Voilà, tu sais tout sur le raisonnement par récurrence, mets tout ça en application et tu devrais devenir un Dieu de la démonstration par récurrence 😉 !

Est-ce que l'analogie de l'escalier va te permettre de t'en rappeler ? Y a-t-il encore des points pas clairs ? Dis-moi tout dans les commentaires !

Au plaisir de t'aider à Réussir,
Steven