: , , … Quel est le plus grand entier qui semble diviser tous les () ?
Notions de logique · Leçon 5
Raisonnement par récurrence
Tous les énoncés et corrigés
: , , … Quel est le plus grand entier qui semble diviser tous les () ?
Voir le corrigé
, donc le diviseur commun ne peut pas dépasser . Et semble diviser tous les termes : c'est la conjecture à démontrer.
La clé de l'hérédité
Pour faire apparaître , quelle égalité est correcte ?
Voir le corrigé
Remets dans l'ordre (attention aux pièges) : divise .
Voir le corrigé
- Initialisation : pour , et divise . Donc est vraie.
- Hérédité : soit . Supposons que divise : il existe tel que .
- Alors .
- Comme , divise : est vraie.
- Conclusion : d'après le principe de récurrence, pour tout , divise .
Touche la ligne où ce raisonnement devient faux.
Voir le corrigé
Ligne 5 : L'initialisation n'a pas été faite, et elle est fausse : n'est pas divisible par .
Hérédité sans initialisation = des dominos qui se feraient tomber les uns les autres… mais dont aucun n'est poussé.
Pour montrer que divise , lesquelles de ces égalités permettent de conclure l'hérédité ?
Voir le corrigé
Les deux premières sont correctes et est un multiple de . Il y a souvent plusieurs bonnes façons de faire apparaître l'hypothèse.
Pour : « divise », calcule pour (initialisation).
Voir le corrigé
, divisible par : est vraie.
Soit définie par et . Calcule .
Voir le corrigé
, , . Et : la formule est cohérente.
Hérédité : on suppose . Quel calcul de est correct ?
Voir le corrigé
Soit . Supposons . Alors . Donc la propriété est vraie au rang .
Teste pour à . Pour quelle valeur est-elle fausse ?
Voir le corrigé
. C'est pour cela que la récurrence est initialisée à ().
On suppose . Quel calcul est correct ?
Voir le corrigé
: « divise ». Initialisation : calcule .
Voir le corrigé
: divise , donc est vraie.
Hérédité : on suppose . Quelle écriture de est correcte ?
Voir le corrigé
Remets dans l'ordre : pour tout , divise .
Voir le corrigé
- Initialisation : . Vrai.
- Hérédité : soit . Supposons avec entier.
- Alors .
- Donc divise .
- Conclusion : pour tout , divise .
On suppose . Alors
Voir le corrigé
On suppose . Alors . Pourquoi ?
Voir le corrigé
- Car .
La somme des carrés
On veut montrer que pour tout :
Vérifier la formule pour et pour .
Démontrer la formule par récurrence.
Voir le corrigé
Pour : et .
Pour : et .
Initialisation. Pour , la formule est vraie (question 1).
Hérédité. Soit . Supposons . Alors :
Or . Donc la somme vaut : c'est la formule au rang .
Conclusion. Pour tout : .
Deux divisibilités par récurrence
Démontrer chaque propriété par récurrence.
Pour tout , divise .
Pour tout , divise .
Voir le corrigé
Initialisation. Pour : . Vrai.
Hérédité. Soit . Supposons que divise : avec . Alors : Donc divise .
Conclusion. Pour tout , divise .
Initialisation. Pour : . Vrai.
Hérédité. Soit . Supposons avec . Alors : Donc divise .
Conclusion. Pour tout , divise .