Raisonnement par récurrence
dans Arithmétique
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.
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.
Connectez-vous ou Inscrivez-vous pour répondre.
Réponses
Que connaissent-ils en arithmétique ? Bien entendu, on ne peut faire une preuve arithmétique sans aucune connaissance d'arithmétique.
Cordialement.
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
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?
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.
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
Mieux vaut-il quantifier proprement.
tu supposes donc connue la division euclidienne.
Cordialement.
$$ 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 !
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.
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 !!
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.
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
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)
Edit: Dessin en 2min en considérant des L et leurs symétriques (donc possibilité de retournement)
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).
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é) ?
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.
je n'énonce rien sur le critère vrai ou faux de P(0).
il me faut 1/
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.
R:=true;
forme i:=0 to -1 do R:=false done ;
Renvoyer R
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.
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. 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
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.
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".