récurrence (raisonnement par).

récurrence (raisonnement par). MATHÉMATIQUES : raisonnement permettant de démontrer une propriété pour tous les entiers de #. Nous l'exposons d'abord sur un exemple. Soit Sn = 1 + 2 + 3... + n, la somme des n premiers entiers, que l'on veut calculer en fonction de n. On a de bonnes raisons de penser que Pour démontrer qu'il en est bien ainsi, voici ce que l'on fait : pour n = 1, S1 = 1, et la formule donne la formule est donc exacte pour n = 1. Supposons alors que la formule soit vraie pour n = p (c'est-à-dire que l'on ait ) et calculons Sp + 1. Sp+1 = 1 + 2 +... + p + (p + 1) = (1 + 2 +... + p) + (p + 1) = Sp + (p + 1) = Ainsi, Sp +1 = + (p + 1 ) , résultat que l'on aurait obtenu en remplaçant n par p + 1 dans la formule à établir. Si donc cette formule est vraie pour n = p, on en déduit qu'elle est vraie pour n = p + 1. Comme on a constaté que la formule est vraie pour n = 1, on en conclut qu'elle est vraie pour n = 2 ; de ce qu'elle est vraie pour n = 2, l'on déduit qu'elle est vraie pour n = 3, et ainsi de suite, indéfiniment. Le schéma du raisonnement est formellement le suivant : soit p(x) une propriété à démontrer. « Raisonner par récurrence », c'est démontrer que : P(1) et, pour tout n >= 1, P(n) h P(n + 1).