| | Semaine 2 - Récurrence | |
| | Auteur | Message |
---|
kexuan Grand chef
Nombre de messages : 236 Age : 34 Localisation : roissy en brie, connaissez pas ? bah maintenant ouai ^^ Section : MPSI 2 -> MP* Loisirs : Foutchbaule Date d'inscription : 25/07/2007
| Sujet: Semaine 2 - Récurrence Lun 14 Juil 2008, 23:11 | |
| Exercice 2.1 (petit théorème de Fermat)Soit $p$ premier. a) Montrer que $p$ divise $p \choose k$ pour $k \in \{1, ... ,p-1\}$. b) En déduire que pour tout $n \in \mathbb{N}^*$ et pour tous entiers $a_1,...,a_n$ on a $$(a_1 + ... + a_n)^p \equiv a_1^p + ... + a_n^p \quad [p]$$ c) Démontrer le petit théorème de Fermat. | |
| | | julien Gros Méchant
Nombre de messages : 796 Age : 35 Localisation : At home Section : ex MPSI V, ex MP*2 Date d'inscription : 10/07/2006
| Sujet: Re: Semaine 2 - Récurrence Mar 15 Juil 2008, 01:28 | |
| Exercice 2.2 (inégalité arithmético-géométrique)Soit $n \in \mathbb{N}^*$. On veut montrer que pour tous $a_1,...,a_n$ réels strictement positifs on a l'inégalité
$$\displaystyle{\frac{a_1+....+a_n}{n} \geq \rootn{a_1 \cdots a_n\right}}$$
(a) Montrer que le résultat est vrai lorsque $n$ est de la forme $n=2^k$, $k\in \mathbb{N}$ par récurrence. (b) Conclure dans le cas général.
Dernière édition par julien le Ven 18 Juil 2008, 22:19, édité 3 fois | |
| | | julien Gros Méchant
Nombre de messages : 796 Age : 35 Localisation : At home Section : ex MPSI V, ex MP*2 Date d'inscription : 10/07/2006
| Sujet: Re: Semaine 2 - Récurrence Mar 15 Juil 2008, 20:45 | |
| Exercice 2.3 (formule de Taylor avec reste intégrale)Soit $f$ un fonction de $\mathbb{R}$ dans lui-même infiniment dérivable. Monter que pour tout $n\in\mathbb{N}$, pour tous $a,b$ réels on a $$f(b) = \sum_{k=0}^n \frac{f^{(k)}(a)}{k!}(b-a)^k + \int_a^b \frac{(b-t)^n}{n!}f^{(n+1)}(t)dt$$
Dernière édition par julien le Ven 18 Juil 2008, 22:20, édité 3 fois | |
| | | louisclem Skwateur
Nombre de messages : 11 Section : Date d'inscription : 20/06/2008
| Sujet: Re: Semaine 2 - Récurrence Jeu 17 Juil 2008, 00:35 | |
| Bon apparement il n'y a pas beaucoup de nouveaux qui sont intéressés, alors moi je poste pour l'exo 2.1 : j'y arrive assez bien, j'ai (je pense) les bonnes idées, mais j'ai du mal à le démontrer proprement et rigoureusement, c'est assez intuitif (questions a et b), enfin je vous mets ce que j'ai trouvé, dites moi ce que vous en pensez : - Spoiler:
a. $p \choose k = \frac{p!}{k!(p-k)!}$ Cette fraction est un nombre entier. Or $p$ divise évidement $p!$ sans diviser ni $k!$ car $0 \lt k \lt p$ ni $(p-k)!$ car $0 \lt p-k \lt p$, et $p$ étant premier, il ne divise aucune factorielle d'un nombre strictement inférieur à lui même. Ainsi, $p$ divise le numérateur et pas le dénominateur, donc $p$ divise l'entier $p \choose k$
b. En développant $(a_1 + a_2 + ... +a_n)^p$, on verra apparaître des termes $a^p$ et les autres termes auront un coefficient en $p \choose k$ avec $k \neq 0$ et $k \neq p$ (il s'agit des cas où le coefficient vaut 1, c'est à dire ceux en $a^p$), or tous ces termes sont divisibles par $p$. Bref, modulo $p$, on retrouve l'égalité cherchée.
c. En décomposant $a$ comme $a = 1+1+1...$, avec $1^p = 1$, on en déduit immédiatement : $a^p \equiv a [p]$, il s'agit du petit théorême de Fermat.
| |
| | | julien Gros Méchant
Nombre de messages : 796 Age : 35 Localisation : At home Section : ex MPSI V, ex MP*2 Date d'inscription : 10/07/2006
| Sujet: Re: Semaine 2 - Récurrence Jeu 17 Juil 2008, 00:40 | |
| - Spoiler:
Pour la a) on peut voir que $p \choose k = \frac{p}{k} {{p-1} \choose {k - 1}}$ ...
Pour démontrer la b) de manière rigoureuse, regarde quelle est la notion clef de la semaine . Sinon c'est très bien ! | |
| | | Poupoute God P'tit joueur
Nombre de messages : 35 Age : 33 Section : Ts mais futur MPSI Loisirs : JV, Ciné, Lecture (moderement). Date d'inscription : 03/07/2008
| Sujet: Re: Semaine 2 - Récurrence Jeu 17 Juil 2008, 12:31 | |
| Bonjour a tous !
On a aussi $p\choose k = \frac{p*(p-1)!}{k!*(p-k)!} = p*\frac{(p-1)!}{k!*(p-k)!}$ et la pour la a c'est terminé puisque l'on a écrit $p\choose k$ comme étant égal a $K*p$ avec $K = \frac{(p-1)!}{k!*(p-k)!} $ Non ?? | |
| | | Gandhorn Gros Vilain
Nombre de messages : 592 Age : 36 Localisation : Périgueux Section : MPSI V --> ψ*1 --> X 08 Loisirs : Faire fondre mon tapis de souris... Date d'inscription : 07/09/2006
| Sujet: Re: Semaine 2 - Récurrence Jeu 17 Juil 2008, 12:56 | |
| reste a montrer que ton K est un entier je pense | |
| | | Poupoute God P'tit joueur
Nombre de messages : 35 Age : 33 Section : Ts mais futur MPSI Loisirs : JV, Ciné, Lecture (moderement). Date d'inscription : 03/07/2008
| Sujet: Re: Semaine 2 - Récurrence Jeu 17 Juil 2008, 13:19 | |
| - Gandhorn a écrit:
- reste a montrer que ton K est un entier je pense
Haaa, je me disais aussi que j'avais oublié un truc, pfff j'ai vraiment une capacité d'oubli très importante, en tout cas de mes cours de spé. Edit Si $k \in \{1, ... ,p-1\}$ ne peut on pas affirmer que $p\choose k$ est un entier ?? En fait, ça m'arrangerait bien ( hihi ) parce qu'après vu que pour tout entiers a et b, a divise b s'écrit b= ak avec k appartenant a Z je n'aurais pas a demontrer que le K est entier ^^. | |
| | | Emeric Philiboy
Nombre de messages : 688 Age : 33 Localisation : 10 km de Valence Section : MPSI5 -> MP*2 -> (5/2) MP*2 -> ENS Lyon Loisirs : Maths, PC, MSN, Karting, Glande, Sport ... Date d'inscription : 22/08/2007
| Sujet: Re: Semaine 2 - Récurrence Jeu 17 Juil 2008, 14:52 | |
| - Poupoute God a écrit:
Edit Si $k \in \{1, ... ,p-1\}$ ne peut on pas affirmer que $p\choose k$ est un entier ?? Ca oui ( Preuve ? ) . Le reste j'ai pas lu | |
| | | Poupoute God P'tit joueur
Nombre de messages : 35 Age : 33 Section : Ts mais futur MPSI Loisirs : JV, Ciné, Lecture (moderement). Date d'inscription : 03/07/2008
| Sujet: Re: Semaine 2 - Récurrence Jeu 17 Juil 2008, 16:57 | |
| Après petites recherches, la demonstration peut se faire par reccurence en applicant la formule de Pascal, mais elle est un peu spéciale ( dite d'induction ) parce qu'il faut partir du cas ou k = 1, pour prouver que pour le cas ou k = 2 la propriété est vraie également et ainsi de suite. Enfin je pense que la c'est assez spécial et peut être pas dans la logique de l'exercice de rechercher ( peut-être ) un surplus de difficulté. Cependant, durant mes investigation laborieuses ( je déconne bien sur ), j'ai trouvé ce pdf, issu d'un DS qui prouve par le calcul que tout coefficient binomial est un entier voici le lien, regardez question 7. ( si ça peut amuser quelques personnes de le rechercher, étant en vacances et voyant ma totale impuissance mathématique devant ce DS, je vous le laisse ) http://people.math.jussieu.fr/~merel/mt282-98-partiel.pdf | |
| | | kexuan Grand chef
Nombre de messages : 236 Age : 34 Localisation : roissy en brie, connaissez pas ? bah maintenant ouai ^^ Section : MPSI 2 -> MP* Loisirs : Foutchbaule Date d'inscription : 25/07/2007
| Sujet: Re: Semaine 2 - Récurrence Ven 18 Juil 2008, 01:29 | |
| - Poupoute God a écrit:
- Bonjour a tous !
On a aussi $p\choose k = \frac{p*(p-1)!}{k!*(p-k)!} = p*\frac{(p-1)!}{k!*(p-k)!}$ et la pour la a c'est terminé puisque l'on a écrit $p\choose k$ comme étant égal a $K*p$ avec $K = \frac{(p-1)!}{k!*(p-k)!} $ Non ?? je ne sais pas si celui-là est entier, mais y a quelquechose de plus simple à faire à partir de là. suffit d'appliquer l'astuce taupinale numéro une (c'est the World Master qui l'appelle ainsi) qui dit que 1-1=0 ! donc on écrit : (p-k)!=(p-1-(k-1))! puis on obtient alors : $p\choose k = \frac{p*(p-1)!}{k!*(p-k)!} = p*\frac{(p-1)!}{k!*(p-1-(k-1))!}$ ce qui nous donne une égalité à connaître (encore une !) : $k p\choose k = p{p-1}\choose {k-1}$ et pi on finit avec un argument de primalité (p et k premiers entre eux) Mais j'pense que ça marche ton truc, mais c'est vrai que c'est pas évident... | |
| | | Poupoute God P'tit joueur
Nombre de messages : 35 Age : 33 Section : Ts mais futur MPSI Loisirs : JV, Ciné, Lecture (moderement). Date d'inscription : 03/07/2008
| Sujet: Re: Semaine 2 - Récurrence Ven 18 Juil 2008, 01:48 | |
| - kexuan a écrit:
- Poupoute God a écrit:
- Bonjour a tous !
On a aussi $p\choose k = \frac{p*(p-1)!}{k!*(p-k)!} = p*\frac{(p-1)!}{k!*(p-k)!}$ et la pour la a c'est terminé puisque l'on a écrit $p\choose k$ comme étant égal a $K*p$ avec $K = \frac{(p-1)!}{k!*(p-k)!} $ Non ?? je ne sais pas si celui-là est entier, mais y a quelquechose de plus simple à faire à partir de là. suffit d'appliquer l'astuce taupinale numéro une (c'est the World Master qui l'appelle ainsi) qui dit que 1-1=0 ! donc on écrit : (p-k)!=(p-1-(k-1))! puis on obtient alors : $p\choose k = \frac{p*(p-1)!}{k!*(p-k)!} = p*\frac{(p-1)!}{k!*(p-1-(k-1))!}$ ce qui nous donne une égalité à connaître (encore une !) : $k p\choose k = p{p-1}\choose {k-1}$ et pi on finit avec un argument de primalité (p et k premiers entre eux)
Mais j'pense que ça marche ton truc, mais c'est vrai que c'est pas évident... Ok je vois comment ça marche, merci a toi grand chef. | |
| | | Emeric Philiboy
Nombre de messages : 688 Age : 33 Localisation : 10 km de Valence Section : MPSI5 -> MP*2 -> (5/2) MP*2 -> ENS Lyon Loisirs : Maths, PC, MSN, Karting, Glande, Sport ... Date d'inscription : 22/08/2007
| Sujet: Re: Semaine 2 - Récurrence Ven 18 Juil 2008, 01:58 | |
| Et encore une victoire de ..... cui cuissss | |
| | | kexuan Grand chef
Nombre de messages : 236 Age : 34 Localisation : roissy en brie, connaissez pas ? bah maintenant ouai ^^ Section : MPSI 2 -> MP* Loisirs : Foutchbaule Date d'inscription : 25/07/2007
| Sujet: Re: Semaine 2 - Récurrence Ven 18 Juil 2008, 11:32 | |
| - Poupoute God a écrit:
- Après petites recherches, la demonstration peut se faire par reccurence en applicant la formule de Pascal, mais elle est un peu spéciale ( dite d'induction ) parce qu'il faut partir du cas ou k = 1, pour prouver que pour le cas ou k = 2 la propriété est vraie également et ainsi de suite.
Enfin je pense que la c'est assez spécial et peut être pas dans la logique de l'exercice de rechercher ( peut-être ) un surplus de difficulté.
Cependant, durant mes investigation laborieuses ( je déconne bien sur ), j'ai trouvé ce pdf, issu d'un DS qui prouve par le calcul que tout coefficient binomial est un entier voici le lien, regardez question 7. ( si ça peut amuser quelques personnes de le rechercher, étant en vacances et voyant ma totale impuissance mathématique devant ce DS, je vous le laisse )http://people.math.jussieu.fr/~merel/mt282-98-partiel.pdf bah en fait maintenant qu'on a l'égalité : $k p\choose k = p{p-1}\choose {k-1}$ et toujours avec le même argument de primalité, k divise ${p-1}\choose {k-1}$ et ton grand K est bien entier (tu l'aurais appelé q ça aurait été marrant ) EDIT : lol j'ai pas vu ton spoiler julien ! tout était dans le spoiler... | |
| | | julien Gros Méchant
Nombre de messages : 796 Age : 35 Localisation : At home Section : ex MPSI V, ex MP*2 Date d'inscription : 10/07/2006
| Sujet: Re: Semaine 2 - Récurrence Ven 18 Juil 2008, 17:00 | |
| C'est marrant, vous avez disserté sur 8 messages pour avoir la même chose que mon petit spoiler | |
| | | kexuan Grand chef
Nombre de messages : 236 Age : 34 Localisation : roissy en brie, connaissez pas ? bah maintenant ouai ^^ Section : MPSI 2 -> MP* Loisirs : Foutchbaule Date d'inscription : 25/07/2007
| | | | louisclem Skwateur
Nombre de messages : 11 Section : Date d'inscription : 20/06/2008
| Sujet: Re: Semaine 2 - Récurrence Mar 19 Aoû 2008, 13:39 | |
| Bonjour, Je suis rentré hier d'un mois de vacances. Et moi, quand je suis sur la plage, que je me baigne, ou que je dors, je fais des maths. Je suis soulagé de voir que personne n'a posté pour l'exercice 2.2, alors je propose la solution que j'ai trouvé pour la question a. Je pense qu'elle est un peu compliquée, il doit y avoir plus simple, surtout que je n'arrive pas à faire la question suivante, alors je poste ça pour l'instant en espérant avoir quelques avis et un peu d'aide... - Spoiler:
On veut montrer par récurrence sur $k \in \mathbb{N}$, avec $n = 2^k$ et des réels strictement positifs $a_1,...a_n$ que : $\frac{a_1+....+a_n}{n} \geq \rootn{a_1 \cdots a_n\right}}$ Initialisation : $k = 0$$\forall a \in \mathbb{R}_{+}^{*}, a \geq a$ Ca va, pas trop dur à suivre ? Initialisation : $k = 1$Je ne suis pas sure que mon initialisation précédente suffise, alors je mets celle-ci aussi car elle est facile et donne pleins de conditions équivalentes intéressantes. Pour $a$ et $b$ réels strictement positifs, on a : $(a-b)^2 \geq 0$ ce qui équivaut successivement, sans trop détailler, à : $a^2 + b^2 \geq 2ab \Leftrightarrow a^2 + b^2 + 2ab \geq 4ab \Leftrightarrow (a+b)^2 \geq 4ab \Leftrightarrow a+b \geq 2\sqrt{ab} \Leftrightarrow \frac{a+b}{2} \geq \sqrt{ab}$ La dernière inégalité est celle que l'on cherche à généraliser. RécurrenceSupposons que pour tout $k \in \mathbb{N}$ l'égalité soit vraie. On a donc, pour tout suites de réels strictement positifs $a_n$ et $b_n$ : $\frac{a_1 +...+a_n}{2^k} \geq \root{2^k}{a_1...a_n}$ et $\frac{b_1 +...+b_n}{2^k} \geq \root{2^k}{b_1...b_n}$ Essayons de "regrouper" ces inégalités pour démontrer ces inégalités pour $n = 2^{k+1}$. En additionnant membre à membre, puis en divisant par 2, il vient : $\frac{a_1+b_1+...+a_n+b_n}{2^{k+1}} \geq \frac{\root{2^k}{a_1...a_n} + \root{2^k}{b_1...b_n}}{2}$ A gauche, c'est bon. Si on montre que le membre de droite est supérieur à $\root{2^{k+1}}{a_1 b_1 ... a_n b_n}}$, alors par transitivité de la relation d'ordre, l'égalité sera démontrée pour $n = 2^{k+1}$. Comparons donc ces deux membres. La condition $\frac{\root{2^k}{a_1...a_n} + \root{2^k}{b_1...b_n}}{2} \geq \root{2^{k+1}}{a_1 b_1 ... a_n b_n}}$ équivaut, en élevant au carré de chaque côté, à: $\frac{\root{2^{k-1}}{a_1...a_n} + \root{2^{k-1}}{b_1...b_n} + 2 \root{2^k}{a_1 b_1 ... a_n b_n}}{4} \geq \root{2^{k}}{a_1 b_1 ... a_n b_n}}$ Puis en multipliant par 4 et en arrangeant, cela équivaut à : $\root{2^{k-1}}{a_1...a_n} + \root{2^{k-1}}{b_1...b_n} \geq 2 \root{2^{k}}{a_1 b_1 ... a_n b_n}}$ Qui se regroupe et se factorise simplement pour obtenir la condition équivalente : $(\root{2^k}{a_1 ... a_n} - \root{2^k}{b_1 ... b_n})^2 \geq 0$ Qui est évidement toujours vraie. L'inégalité est donc démontrée pour $n = 2^{k+1}$ et donc, par récurrence, pour tout entier $k$.
Voilà c'était pas facile quand même, et long à tapper, mais quand on connaît bien le cas $a+b \geq 2 \sqrt{ab}$ ($n = 2$), on peut arriver à le démontrer pour $n = 4$ et généraliser. | |
| | | julien Gros Méchant
Nombre de messages : 796 Age : 35 Localisation : At home Section : ex MPSI V, ex MP*2 Date d'inscription : 10/07/2006
| Sujet: Re: Semaine 2 - Récurrence Mar 19 Aoû 2008, 18:58 | |
| Je te félicite pour la rédaction. Tu aurais juste pu aller un peu plus vite en utilisant directement l'inégalité du cas n = 2 pour l'hérédité, ce qui t'aurais permis d'éviter quelques lourdeurs d'écriture. Très bien quand même, j'attends la suite de l'exo maintenant Tu veux des indications ? | |
| | | B2Moo Skwateur
Nombre de messages : 10 Age : 34 Localisation : Epinay/Orge (91) Section : futur MPSI Loisirs : informatique (programmation), jeux vidéo (fps), roller (skate park) Date d'inscription : 10/06/2008
| Sujet: Re: Semaine 2 - Récurrence Mer 20 Aoû 2008, 01:26 | |
| Pour le 2.2 (b) Je crois que j'ai trouvé, mais ça me semble bizarre, les calculs s'arrangent trop facilement, donc je commence à douter .... mais je vois pas d'erreurs donc .... je vous laisse trouver (gros pavé, attention) - Spoiler:
Puisque l'on sait que l'égalité est vraie pour les valeurs de n de la forme $2^k, k \in \mathbb{N}$, et qu'on peut trouver de telle valeurs aussi grandes que l'on veut, il suffit de montrer que si la propriétés est vraie au rang n, elle l'est forcément au rang n-1 (s'il est positif), en fixant la valeur de $a_n$
Pour une valeur N $\in \mathbb{N}^*$ fixée. Initialisation: On pose $n_0 = 2^{E[log_2(N)] + 1$ ainsi $n_0$ est de la forme $2^k, k \in \mathbb{N}$ et N < $n_0$. On a donc: $\frac{\sum_{k=1}^{n_0} a_k }{n_0} \geq \root{n_0}{\prod_{k=1}^{n_0} a_k}$
Hérédité: On remarque que $\frac{\sum_{k=1}^n a_k }{n} = \frac{\sum_{k=1}^{n-1} a_k }{n - 1}$ <=> $\frac{a_n}n + \frac{\sum_{k=1}^{n - 1} a_k }{n} = \frac{\sum_{k=1}^{n-1} a_k }{n - 1}$ <=> (on retire $a_n$ de la somme) $\frac{a_n}n = \frac{\sum_{k=1}^{n-1} a_k }{n - 1} - \frac{\sum_{k=1}^{n - 1} a_k }{n} = \sum_{k=1}^{n - 1} a_k \frac{1}{n-1} - \frac{1}{n}$ <=> $\frac{a_n}n = \frac{n - (n - 1)}{(n-1)n}\sum_{k=1}^{n - 1} a_k = \frac{1}{(n-1)n}\sum_{k=1}^{n - 1} a_k $ <=> $a_n = \frac{\sum_{k=1}^{n - 1} a_k }{n-1}$ (simplification par n > 0)
Supposons donc $\frac{\sum_{k=1}^{n - 1} a_k }{n-1} \geq \rootn{\prod_{k=1}^n a_k} $ en prenant $a_n = \frac{\sum_{k=1}^{n - 1} a_k }{n-1}$
On a ainsi: $\frac{\sum_{k=1}^{n-1} a_k }{n - 1} \geq \rootn{\prod_{k=1}^n a_k} $ Ce qu'on peut aussi écrire: $a_n \geq \rootn{\prod_{k=1}^n a_k} $ Donc: $(a_n)^n \geq \prod_{k=1}^n a_k $ Puis en simplifiant par $a_n$ ( > 0): $(a_n)^{n-1} \geq \prod_{k=1}^{n-1} a_k $ Soit finalement: $a_n \geq \root{n-1}{\prod_{k=1}^{n-1} a_k}$ Ce qui est bien:
$\frac{\sum_{k=1}^{n - 1} a_k }{n-1} \geq \root{n-1}{\prod_{k=1}^{n-1} a_k}$ (qui est l'inégalité au rang n-1)
Pour n > 1, on a donc: $\frac{\sum_{k=1}^{n} a_k }{n} \geq \root{n}{\prod_{k=1}^{n} a_k}$ =>$\frac{\sum_{k=1}^{n - 1} a_k }{n-1} \geq \root{n-1}{\prod_{k=1}^{n-1} a_k}$
Conclusion Par récurrence, on en déduit que pour tout n, tel que $1 \leq n \leq n_0$, $\frac{\sum_{k=1}^{n} a_k }{n} \geq \root{n}{\prod_{k=1}^{n} a_k}$ Or $1 \leq N \leq n_0$ donc $\frac{\sum_{k=1}^{N} a_k }{N} \geq \root{N}{\prod_{k=1}^{N} a_k}$
J'ai noté ça sans utiliser les points, je trouve ça plus clair, j'espère que vous m'en voudrez pas | |
| | | Contenu sponsorisé
| Sujet: Re: Semaine 2 - Récurrence | |
| |
| | | | Semaine 2 - Récurrence | |
|
Sujets similaires | |
|
| Permission de ce forum: | Vous ne pouvez pas répondre aux sujets dans ce forum
| |
| |
| |