Forum de mathématiques - Bibm@th.net

Bonsoir,

Ce n'est pas faux, mais resituer une question dans son cadre théorique idéal n'est pas forcément incongru pour tout le monde et son intérêt dépend étroitement du niveau des interlocuteurs, rarement indiqué.
Celui de ibn al-banna m'a semblé très correct d'emblée puisqu'il s'est interrogé sur une phrase à la sémantique douteuse.
Rectifier le tir sur une phrase de l'historien Djebbar qui finalement mathématiquement est une coquille vide m'a semblé indispensable.

Après, sur un plan sociologique,  si ce qui te dérange dans la vie te fait aussi rigoler, tu dois sans doute avoir l'impression quasi permanente d'être environné de clowns... vue la conjoncture ce n'est effectivement pas plus mal!

Bonne journée
A.

Bonsoir,

C'est toujours ça ;-).

@ibn al-banna: pour "inducter" sur des couples d'entiers il faut avoir une règle sur les couples pour indiquer comment on passe d'un couple (ou d'un ensemble de couples) à un autre couple, vis à vis de la propriété étudiée. Sans ce préalable, la question n'a pas de sens: il n'y a pas d'induction "absolue" , en tout cas si je comprends bien la question.
Dans N on a un ordre naturel prêt à l'emploi, possédant la bonne propriété (et même plus, bon ordre ).
Sur NxN on a par exemple un ordre total (0,0) < (0,1)<(1,0) <(1,1) etc, mais rien ne dit que ça serve pour la propriété à étudier...

Revenons à la question de dénombrement, qu'on souhaite prouver par récurrence.
Soit P( n,p) la propriété portant sur les couples d'entiers non nuls , avec p au plus égal à n  , de vérifier la formule habituelle
du nombre de parties à p éléments parmi n: je ne la réécris pas.
On note Q(p) ssi P(n,p) est vraie pour tout n au moins égal à p.
On montre Q(0)  par récurrence sur n: première récurrence.
C'est une autre façon de dire que P(0,0), P(0,1) , etc sont vraies.
On montre ensuite que Q(p) => Q(p+1).
Cela suffit ( seconde récurrence) pour conclure que Q(p) est vraie pour tout p.
En traduisant une dernière fois: pour tout p, pour tout n au moins égal à p, on a P(n,p).
On a appliqué les quantificateurs d'abord sur n, à p donné, puis sur p, mais on aurait pu procéder dans l'autre sens ( en inversant aussi l'inégalité).
Tu peux visualiser graphiquement la démarche en regardant les points (n,p) sous et sur la diagonale.
On veut montrer que tous ces points conviennent.
D'abord tout ce qui est sur la même ligne que (0,0) à sa droite est ok, c'est la première récurrence.
La seconde récurrence consiste à prouver que si toute la ligne à droite d'un point de la diagonale convient, c'est aussi le cas en montant d'un cran sur la diagonale, d'où le résultat attendu.
L'autre sens consistait à raisonner en colonnes... C'est similaire.
Enfin une autre approche consiste à étendre les coefficients binomiaux à la valeur 0 quand p dépasse n, et ne pas limiter les récurrences sous la diagonale. A voir.

Pour finir sur la question essentielle, le caractère non absolu de la réponse à ton interrogation telle qu'elle est formulée, pour une autre propriété P' que la formule donnant les coefficients binomiaux, vous auriez peut-être dû avancer par un tout autre moyen, par exemple:
Montrer P'(0,0) puis que P'(n,n) => P'( n+1,n+1) ( 1 ière récurrence), obtenant la diagonale principale Do.
Puis montrer que si P' est vraie sur une diagonale parallèle, elle est vraie aussi pour la diagonale juste à côté... càd passer de
D(i ) à D(i+1)( 2 ième récurrence), puis conclusion...
On en revient à mon post de départ, il faut pouvoir progresser dans un certain ordre sur les éléments qui nous intéressent, ça dépend fondamentalement de l'ensemble lui-même ( Y-a-t-il un bon ordre ou un ordre bien fondé dessus, n'en déplaise à Roro, et sa tendance marquée à la rigolade * ), ainsi que de la propriété elle-même considérée à démontrer ( faire avancer le schmilblick... ?)

(*) On passerait son temps à se rouler par terre de rire en faisant des maths si on s'attardait à l'armada gigantesque des mots techniques indispensables qui l'émaillent, tous domaines confondus. @Roro dans ton cas, j'ose espérer que ton exubérance joyeuse est dûe aux feux d'artifice tout récents... :-), sinon franchement c'est plutôt ballot...

Bonne soirée
A.

Bonjour,

Quand je relis la demande initiale de ibn al-banna

et que je lis la dernière réponse de bridgslam qui parle d'ordre artinien, d'induction noethérienne ou de principe d'induction "transfinie" sur les ordinaux, je ne suis pas certain que ça réponde à la question (même si ce n'est probablement pas faux).

Ça m'a juste bien fait rigoler !

Roro.

Bonsoir :
Une analogie classique : l'écroulement d'une file de dominos
https://www.youtube.com/watch?v=o_L0yqFWR7M
On fait tomber le premier domino. La chute d'un domino entraîne celle du suivant  ... et à la fin tous les dominos sont tombés.
On démontre P(0). On démontre que si P(k), alors P(k+1) ... et à la fin on a démontré P(n) pour tout entier n

Disons qu'on rédige autrement.
La version visible dans ton pdf fonctionne un peu sur le principe, on voit bien comment cela fonctionne sur les premiers termes, on imagine facilement que cela va continuer à fonctionner de proche en proche donc c'est démontré

Maintenant, comme je te l'ai fait, on rédige séparément :
- initialisation
- supposition que la propriété est vraie pour p (que n soit fixé ou non) pour démontrer que sous cette supposition alors la propriété est vraie pour p+1
- conclusion

Tout à fait, si tu regardes la 2ème induction sur p, qui est exactement sa démonstration en fait, on considère n quelconque (mais supérieur à p quand même) puis p porte la récurrence quand il passe de p à p+1
La 1ere induction est facultative, le résultat peut être considéré comme connu, je me suis dit que cela pouvait être intéressant pour toi de voir d'abord une induction à un seul indice n.

Bonjour ibn al-banna, je vais partir de ton document pour essayer de t'expliquer, ce sera long mais compréhensible si tu prends le temps de lire attentivement (enfin j’espère) :
Avec $n$ lettres différentes dans un alphabet : $a_1,a_2,a_3...a_n$ on essaye de trouver le nombre de combinaisons différentes de $p$ lettres possibles.

Par exemple avec $n=3$ lettres dans l'alphabet, si on veut des combinaisons avec uniquement $p=2$ lettres, on aura $\{a_1,a_2\}$, $\{a_1,a_3\}$ et $\{a_2,a_3\}$ soit $3$ combinaisons et puis c'est tout. On ne comptera pas $\{a_2,a_1\}$ car au final ce sont les mêmes lettres que dans le premier cas.

Il faut faire une induction à double indice car 2 choses peuvent varier : la taille de l'alphabet $n$ et le nombre de lettres choisies pour les combinaisons $p$. Par la suite, je te refais la démonstration mais l'idée, s’arrête ici en fait, $n$ et $p$ doivent pouvoir augmenter autant qu'on veut.

1ere induction sur $n$ : généraliser l'exemple pour $n$ lettres différentes dans l'alphabet mais toujours avec uniquement $2$ lettres choisies. On veut démontrer que le nombre de combinaisons est $C^2_n=\dfrac{n(n-1)}{2}$

Cela fonctionne pour $n=3$ comme on vient de le voir mais aussi pour $n=2$ (je te laisse vérifier)

Si c'est vrai pour un nombre de lettres de l'alphabet $n$ quelconque alors que se passe t'il pour $n+1$ ? Autrement dit que se passe t-il avec une lettre supplémentaire dans l'alphabet ?

On garde les combinaisons avec $n$ lettres dans l'alphabet, elles sont au nombre de $\dfrac{n(n-1)}{2}$ par hypothèse et on rajoute les combinaisons avec la nouvelle lettre $a_{n+1}$ c'est à dire $\{a_1,a_{n+1}\}$, $\{a_2,a_{n+1}\}$...$\{a_n,a_{n+1}\}$ soit $n$ nouvelles combinaisons. Au final il y a $C_{n+1}^2=\dfrac{n(n-1)}{2}+n$=$\dfrac{n^2-n}{2}+\dfrac{2n}{2}$=$\dfrac{n^2+n}{2}$=$\dfrac{n(n+1)}{2}$ combinaisons.

La propriété que l'on voulait démontrer est démontrée, elle est vraie pour $n=2$ et si elle est vraie pour $n$, elle est aussi vraie pour $n+1$ donc par récurrence, elle est vraie pour $n=3$, puis $n=4$, puis $n=5$...

2ème induction sur $p$ : généraliser l'exemple cette fois pour un choix de $p$ lettres dans l'alphabet constitué de $n$ lettres en supposant avoir suffisamment de lettres. On veut démontrer que le nombre de combinaisons est $C^p_n=\dfrac{n(n-1)(n-2)...(n-p+1)}{p(p-1)(p-2)...1}$

Cela fonctionne pour $p=2$ comme on vient de le voir précédemment

Si c'est vrai pour un nombre de lettres choisies $p$ alors que se passe-t'il pour $p+1$ ? Autrement dit que se passe t-il avec une lettre supplémentaire dans les combinaisons ?

On complète les combinaisons avec $p$ lettres choisies, elles sont au nombre de $C_n^p$, par une $(p+1)$^ème lettre. Or pour chaque combinaison, il ne reste plus que $n-p$ lettres disponibles puisque $p$ lettres ont déjà été choisies ce qui donne $C_n^p (n-p)$ possibilités. Mais attention, en faisant cela, on compte plusieurs fois les mêmes combinaisons.

Par exemple pour $n=3$ et $p+1=3$
On choisit d'abord $2$ lettres $(a_1,a_2)$ puis une troisième $a_3$ ce qui donne $(a_1,a_2,a_3)$
Mais on peut aussi choisir d'abord les $2$ lettres $(a_1,a_3)$ puis une troisième $a_2$ ce qui donne $(a_1,a_3,a_2)$
Ou même d'abord les $2$ lettres $(a_2,a_3)$ puis une troisième $a_1$ ce qui donne $(a_2,a_3,a_1)$
Or nous, on voulait que ce soit la même chose.

Donc il faut diviser par $p+1$ pour avoir au final $C^{p+1}_n=C_n^p \dfrac{n-p}{p+1}=\dfrac{n(n-1)(n-2)...(n-p+1)(n-p)}{(p+1)p(p-1)(p-2)...1}$ combinaisons

Comme précédemment, la propriété que l'on voulait démontrer est démontrée

PS : je te déconseille le site où tu as initialement posé ton message, selon moi, il n'est pas adapté aux non professionnels

Bonjour
Les réponses qui t'ont été données ici ne te conviennent-elles pas?