Raisonnement par récurrence

bulledesavon · August 2017

Bonjour,

Je me place au début de la terminale S, lorsque l'on introduit le raisonnement par récurrence.

Le problème est le suivant :
On considère la propriété $P(n):"2^n$ est divisible par $3"$, où $n\in\mathbb{N}$.
L'affirmation "la propriété est toujours fausse" est-elle vraie ou est-elle fausse ?

Ma réponse serait : $2^n$ et $3$ n'ont aucun facteur premier en commun, ils sont donc premiers entre eux. Par conséquent 3 ne divise pas $2^n$ quelque soit l'entier $n$.

Mon problème : les élèves de début de terminale n'ont pas fait d'arithmétique (et seuls ceux qui vont suivre la spé maths vont voir la notion de nombres premiers entre eux).

Comment répond-on rigoureusement à cette question à ce moment là ?

Merci par avance pour vos contributions.

gerard0 · August 2017

Bonjour.

Que connaissent-ils en arithmétique ? Bien entendu, on ne peut faire une preuve arithmétique sans aucune connaissance d'arithmétique.

Cordialement.

Nanard13 · August 2017

Bonjour, c'est un peu ridicule mais on peut faire un raisonnement par récurrence

On considère la propriété $Q(n):"2^n$ n' est pas divisible par 3", où n est un entier naturel.

Initialisation : n=0
$Q(0)$ est vraie, 3 ne divise pas 1

Hérédité :
Supposons que pour un entier n quelconque $Q(n)$ est vraie.
On peut donc écrire :

$2^n = 3q + r$ avec $r=1$ ou $r=2$
D'où : $2^{n+1}$ = $3$ x $2q + 2r$
1er cas : si r=1 alors $2^{n+1}$ = $3$ x $2q + 2$ ce qui prouve que 3 ne divise pas $2^{n+1}$
1er cas : si r=2 alors $2^{n+1}$ = $3$ x $2q + 4$ = $3(2q+1) + 1$ ce qui prouve que 3 ne divise pas $2^{n+1}$

Conclusion :
Pour tout entier n, $Q(n)$ est vraie

Fin de partie · August 2017

Est-ce que c'est un bon exemple pour introduire le raisonnement par récurrence?

On a l'impression (fausse) qu'on peut se passer du raisonnement par récurrence ici.
Par ailleurs, on obtient des résultats spectaculaires grâce à une simple récurrence.
Ne serait-il pas plus judicieux de considérer un exemple plus probant de la puissance du concept?

acetonik · August 2017

Bonjour à tous,

bulledesavon a écrit:

la propriété P(n):"$2^n$ est divisible par 3", où n appartient à N .

En toute rigueur , P(n) n'est pas une propriété , on disait forme propositionnelle de mon temps ...

par contre:
P: "pour tout n appartenant à N , $2^n$ est divisible par 3"
est une bien une propriété (fausse bien sûr).

Cordialement

PS/ Par simple négation , il n'y a absolument pas besoin de récurrence ici.

Chaurien · August 2017

Moi je dirais une proposition, ou une assertion, bref quelque chose qu'on affirme comme « $\pi $ est rationnel ». Mais ceci dit, je ne vois pas l'intérêt de tout ça pour l'enseignement de la récurrence.

acetonik · August 2017

@Chaurien
Je suis d'accord .
J'ai repris le mot propriété qui était employé, mais je préfère aussi proposition (ou assertion) .
Propriété me semble réservé à une proposition vraie... ce qui n'est pas le cas dans cet exemple

Dom · August 2017

Remarque : je trouve bizarre de dire "toujours" sauf peut-être à l'oral.
Mieux vaut-il quantifier proprement.

gerard0 · August 2017

OK, Bulledesavon,

tu supposes donc connue la division euclidienne.

Cordialement.

flipflop · August 2017

Salut,

$$ 2^n= (3-1)^n = \sum_{k=0}^n {n \choose {k}} (-1)^{n-k}3^k = 3q+(-1)^n$$

Je sais pas si y'a la formule du binôme :-S

Edit : Ah mince j'avais pas vu la récurrence sorry !

christophe c · August 2017

acetonik a écrit:

Propriété me semble réservé à une proposition vraie... ce qui n'est pas le cas dans cet exemple

Un bel exemple des dégâts du fléau pédagogiste B-)

Pas du tout, une propriété c'est un ensemble (ou une collection). Par exemple certains rectangles ont la propriété d'être carrés et d'autres non, etc.

Par contre, il serait plus correct de noter $n\mapsto P(n)$ à la place de $P(n)$ pour parler de propriété (et encore ce qui revient strictement au même $\{n\mid P(n)\}$)

Un truc prouvé s'appelle un théorème (et non pas "propriété" comme de mauvais livre du secondaire le disent parfois, induisant de nombreux contre-sens). Une phrase (vraie ou fausse ou peu importe) peut être considérée comme une propriété d'arité 0.

Peux-tu par ailleurs, préciser ton but bulle de savon? Veux prouver l'axiome de récurrence avant de l'utiliser? Veux-tu l'utiliser sans le prouver? Bref, pas trop compris où tu veux en venir. Et quel intérêt particulier y a-t-il à évoquer spécialement que $3$ ne divise pas $2^n$ dans ce contexte général?

Si tu veux un exemple "édifiant" d'application de l'axiome de récurrence: tout nombre qui n'est pas pair est suivi par un nombre pair.

acetonik · August 2017

re-bonjour @cc

J'ai été prudent en disant "il me semble" ...on ne va pas recommencer ce fil que je connaissais:

Reconnais seulement que les avis ne sont pas unanimes.

Cordialement

PS/
Une propriété (mathématique) , c'est une qualité d'un objet (mathématique), elle s' exprime par une proposition vraie.

Par abus de langage on confond la propriété (par exemple :distributivité d'une loi par rapport à une autre ) et la proposition (vraie) qui énonce cette propriété.

C'est tout , et pour moi c'est clair !!

christophe c · August 2017

Je réagissais surtout pour les lecteurs en réaction à cette avalanche de champ intitulés "propriétés" que l'on voit dans les manuels scolaires, utilisés de manière invalide (en gros ils ont substitué le mot "propriété" au mot "théorème" en titre de champ).

J'imagine que pour ta part, tu es majeur et vacciné et fais ce que tu veux, mais ça me semblait mériter d'être signalé car ton post pouvait avoir l'air de corroborer l'erreur des manuels.

zenxbear · August 2017

les exercices niaiseux du style de OP, ou genre $1+2+ ... +n = \frac{n(n+1)}{2}$ illustrent certes la méthode, mais sont vraiment agaçant, car substituables par une démonstration directe qui est bien plus limpide.
Ton exemple d'illustration serait meilleur si tu le remplace par "Montrer que 3 divise $4^n-1$"...

le raisonnement par récurrence est basé sur l'axiome de well ordering de $\mathbb{N}$. Et cet axiome vient avant la division euclidienne avec reste, vu que justement il sert à démontrer le théorème de la division euclidienne.
le principe d'induction est une conséquence de cet axiome, par utilisation d'un raisonnement par l'absurde.

des choses en combinatoire sont peut être plus intelligentes pour illustrer. Par exemple "Un ensemble de n éléments admet $2^n$ sous-ensembles".
ou par exemple si tu fais des graphes ca apparaît souvent. Mais tu peux contourner toute la présentation des graphes en donnant
"n joueurs jouent entre eux, pas d'égalité. montrer qu'il y a au moins un joueur le plus fort , c.a.d tel que tout autre joueur j, a soit perdu contre le numéro 1, soit perdu contre un joueur qui a perdu contre le numéro 1". je ne suis pas sur que c'est juste, mais ca ressemble au théorème du chemin hamiltonien orienté dans un graphe simple complet orienté.

tu peux aussi démontrer la division euclidienne par induction, à condition de leur montrer un principe d'induction complet c.à,d
1/ P(0) est vraie
2/ si P(j) est vraie pour $0\leq j < n$ alors P(n) est aussi vraie.

par ailleurs l'axiome est utilisé pour démontrer des théorèmes du style "tout entier différent de 0 et +1, et -1 se décompose en produit de nombre premiers". Que tu peux maintenant redémontrer par une récurrence.

bon après, je ne sais pas comment les tocards de term S se débrouillent, ni s'ils sont capables de réfléchir. Je commence bientôt en prof stagiaire au collège

GaBuZoMeu · August 2017

Une version ludique (pour faire plaisir à Christophe) du "$3$ divise $4^n-1$" : montrer qu'on peut recouvrir un échiquier ($8\times 8$ cases) par des triminos (trois cases en "L") en laissant un trou d'une seule case.

christophe c · August 2017

Ludiquet probablement bien plus difficile. La forme rigide ajoute une dure contrainte. Merci pour le cadeau!

Krokop · August 2017

GaBuZoMeu: 3 divise 2^3-1 ici ? :-D; Joli exercice.

GaBuZoMeu · August 2017

Krokop, tu devrais réapprendre à compter : $8\times 8$, ça fait $64$, et $64 -1 = 3\times {?}$ (:D

acetonik · August 2017

Pour faciliter les choses on peut aussi jouer sur les mots et faire un dessin, GBZM a écrit " montrer" et non "démontrer" ...

PS /
Pour la notion de "propriété", on trouve aussi " propriété portant sur un ensemble E" , pour signifier que " pour tout x appartenant l'ensemble E, la propriété P(x) est vraie" , ce qui est incorrect, à mon sens, car P(x) n'est pas une propriété mais une forme propositionnelle (à une variable)

GaBuZoMeu · August 2017

C'est plus pénible de faire le dessin que le raisonnement par récurrence ...

acetonik · August 2017

Le raisonnement pour la divisibilité OK , mais quid de la contrainte en L ?

Edit: Dessin en 2min en considérant des L et leurs symétriques (donc possibilité de retournement)

Dom · August 2017

@cc
Un fléau ? Pas vraiment.
Si les gens disent que leurs propriétés du cahier sont les théorèmes du logicien je ne vois pas vraiment le problème.
Même si je sais que tu pestes après lorsque l'on annonce une propriété fausse.
Mais ce sont les théorèmes faux du logicien non ? (il me semble t'avoir lu utilisant cette allocution "théorème faux" dans plusieurs fils et si ce n'est pas le cas, alors mea culpa).

GaBuZoMeu · August 2017

Raisonnement par récurrence en 15 secondes.
L'énoncé :
Pour tout entier naturel $n$, pour toute case enlevée d'un échiquier de $2^n\times 2^n$ cases, ce qui reste se pave par des triminos de 3 cases (pas besoin de "retournement" bien sûr, les déplacements suffisent).

PS. Pour cet énoncé dans le cas $n=3$, un seul dessin ne suffit pas. Question subsidiaire : Combien de temps est nécessaire, à raison de 2 minutes par dessin (On peut tenir compte des symétries du carré) ?

acetonik · August 2017

Oui bien sûr , mais je taquinais un peu sur la différence entre montrer et démontrer :-)

Math Coss · August 2017

Ce qui est amusant dans cette histoire de triminos, c'est de transformer la preuve en un programme informatique qui dessine effectivement le pavage.

GaBuZoMeu · August 2017

à condition de leur montrer un principe d'induction complet c.à,d
1/ $P(0)$ est vraie
2/ si $P(j)$ est vraie pour $0\leq j<n$ alors $P(n)$ est aussi vraie.

Le 1) est superflu !

b.b · August 2017

20 minutes ?

GaBuZoMeu · August 2017

(tu)

zenxbear · August 2017

bein non, il faut l'initialisation.

GaBuZoMeu · August 2017

Tu te trompes. Énonçons plus proprement :
On suppose que pour tout entier naturel $n$, si pour tout entier naturel $p<n$ $P(p)$ alors $P(n)$.
Alors, pour tout entier naturel $n$, $P(n)$.
Pas d'initialisation sous cette forme !!!

PS. Un exemple d'utilisation : démontrer que pour tout espace vectoriel $E$ de dimension finie et pour toute famille d'endomorphismes diagonalisables de $E$ commutant deux à deux (aucune hypothèse sur le cardinal de cette famille), il existe une base de diagonalisation simultanée de tous les endomorphismes de la famille.

zenxbear · August 2017

le 2 est " SI P(0) à P(n-1) sont vraies, alors P(n) l'est aussi.
je n'énonce rien sur le critère vrai ou faux de P(0).
il me faut 1/

GaBuZoMeu · August 2017

Non, il ne te faut pas 1°). Pour la raison toute bête que si $n=0$, alors $P(p)$ est trivialement vérifié pour tout entier naturel $p<n$ !

As-tu essayé l'exercice d'application ?

PS. Tu n'es pas le seul à être persuadé - à tort - qu'il faut une initialisation pour cette forme de récurrence. J'ai rencontré le même genre de croyance chez pas mal d'agrégatifs.

christophe c · August 2017

@zen: suite a ta premiere phrase, tu peux d'ailleurs l'expérimenter sur ton ordi car un langage de programmation bien implémenté te renverra vrai à la demande:

R:=true;
forme i:=0 to -1 do R:=false done ;
Renvoyer R

zenxbear · August 2017

l'exercice de la division euclidienne? bein on vérifie que l'affirmation est vraie pour a<d ...

dans ta manière de lire le 2/, tu dois vérifier que "affirmation vide => P(0) est vraie", implication vraie que si tu vérifies que P(0) est vraie. tu n'échappes pas à cette vérification.

si tu veux, je rajoute à 2/ "pour n $\geq 1$".
Et le 1/ n'est plus superflu.

GaBuZoMeu · August 2017

Je parle de l'exercice sur la base de diagonalisation simultanée qui figure dans mon message. Tu n'as pas dû le lire avec beaucoup d'attention.

dans ta manière de lire le 2/, tu dois vérifier que "affirmation vide => P(0) est vraie", implication vraie que si tu vérifies que P(0) est vraie.

Tu as l'air d'avoir quelques petits soucis de logique. La valeur de vérité de $\forall p\in \N\quad p<0\implies P(p)$ est "vrai". Si tu n'es pas d'accord, trouve moi un entier naturel $p<0$ tel que $P(p)$ soit faux !
Donc, si $\forall n\in \N\ \left((\forall p\in \N\quad p<n\implies P(p)) \implies P(n)\right)$ est vrai, forcément $P(0)$ est vrai. Il est superflu de l'ajouter.

si tu veux, je rajoute à 2/ "pour n >=1".
Et le 1/ n'est plus superflu.

C'est idiot pour la raison que je viens d'expliquer. Tant qu'à faire, tu pourrais mettre aussi pour $n\geq 2$ et ajouter $P(1)$ à l'"initialisation". :-D

zenxbear · August 2017

ok. je vois comment déduire l'axiome de well ordering de N à partir de 2/ uniquement sans problème. donc tu as raison.

je vois sur ton exercice. Je présume que la récurrence se fait sur la dimension n de E.

tu vas prendre un élément de la famille ces endomorphismes. une vap, l'espace propre associé. et faire sortir une projection sur la base complétée, et appliquer une récurrence sur la famille des endomorphisme composée avec la projection...
dans ce cas néanmoins tu vérifies le 2/, pour tout $n\geq 1$.
En gros on substitue la vérification de P(1) dans une récurrence normale, par une discussion (avec la récurrence complète) du cas ou l'espace propre associé est égal à E en entier.

GaBuZoMeu · August 2017

Non, ce n'est pas tout à fait comme ça.
La récurrence se fait effectivement sur la dimension $n$ de l'espace, avec le schéma de récurrence qu'on a discuté (sans initialisation !).
On suppose que pour toute famille d'endomorphismes diagonalisables commutant deux à deux de n'importe quel espace de dimension $<n$, il y a une base de diagonalisation simultanée.
Soit $(f_i)_{i\in I}$ une famille d'endomorphismes diagonalisables commutant deux à deux d'un espace vectoriel $E$ de dimension $n$. Si tous les $f_i$ sont des homothéties, n'importe quelle base de $E$ convient. Sinon, Soit $i_0\in I$ tel que $f_{i_0}$ n'est pas une homothétie. Les sous-espaces propres $E_j$ ($j=1,\ldots,r$) pour $f_{i_0}$ sont stables par tous les $f_i$, et tous de dimension $<n$. D'après l'hypothèse de récurrence, on a pour chaque $j$ une base de diagonalisation simultanée des $f_i|_{E_j}$. Ces bases mises bout à bout forment une base de diagonalisation simultanée des $f_i$.

On voit bien sur cet exemple qu'il n'y a nul besoin d'"initialiser".

b.b · August 2017

J'avais lu une preuve un peu compliquée de ce résultat dans un bouquin qui démontrait d'abord le cas $I$ fini par récurrence en supposant $I=\{1,\dots, p\}$ puis le cas $I$ infini, mais celle-là est bien plus simple.

Raisonnement par récurrence

Réponses

Bonjour!

Catégories

In this Discussion

Qui est en ligne 23