La démonstration par récurrence
n(n +1). 2 pour tout entier n )). La démonstration par récurrence se fait en trois étapes : • Initialisation : on vérifie que la propriété est vraie
Récurrence ; Sommes produits
27?/09?/2011 1 Démonstration par récurrence ... récurrence n'est pas très compliqué si on se force à bien en respecter la structure la rigueur est donc.
Entraînement sur les récurrences
donc la propriété est vraie au rang n + 1 ce qu'on voulait. Corrigé 2. Nous allons démontrer cette inégalité par récurrence sur n. Initialisation : pour n = 1
Raisonnement par récurrence
Correction (1.28 question 2). Montrons par récurrence sur n la propriété. Pn : ?x > 0
Chapitre 3: La démonstration par récurrence
2 · 1 expression que l'on appelle n factorielle (?n ? IN *). Page 7. CHAPITRE 3. DEMONSTRATION PAR RECURRENCE. 39. 2MSPM – JtJ
Combinatoire énumérative
1 × 2 × 3 ×···× (n ? 1) × n. On lit "n factorielle". Proposition 3. Le nombre de manières d'ordonner n éléments est n!. Démonstration. Nous avons n
Calcul Algébrique
Table des matières. 1 Cours. 2. 1.1 Sommes et produits . des nombres de 1 à n est n!. Démonstration : On montre le théorème par récurrence sur n.
Sommes produits
https://www.normalesup.org/~glafon/carnot10/recurrence.pdf
Le raisonnement par récurrence
Preuve : notons A l'ensemble des naturels n tels que P(n) soit vraie. La propriété 1 nous dit que 0 appartient. `a A ; la propriété 2 nous dit que si n
Chapitre 1. Raisonnement par récurrence
+. P n 1 à démontrer. 2) Si on veut prouver que la propriété est vraie pour ? n 0 on commence l'initialisation à ( ).
Z ] í X Z ] } v v u v µ v
1 Raisonnement par récurrence 7 ô î W ] X ^ µ } } v W v À ] ~ [ r r ] µ v v í
Quel est le principe de la démonstration par récurrence ?
Eh bien il s’agit exactement du principe de la démonstration par récurrence. Essayons de le comprendre en reformulant cet exemple des dominos en termes mathématiques. La démonstration par récurrence sert à démontrer des propriétés qui portent sur les entiers naturels, c’est-à-dire des propriétés de la forme : “Pour tout n ? N, blablabla” .
Qui a inventé la récurrence ?
Le terme récurrence est apparu au début du 20è siècle. On parle alors de formules de récurrence et de raisonnement par récurrence pour parler du rai- sonnement par induction introduit par Blaise Pascal.
Comment utiliser le principe de récurrence ?
On est amené à utiliser le principe de récurrence suivant : Cette propriété est en apparence plus forte que la récurrence simple, puis que l'on a une hypothèse supplémentaire à notre disposition, mais lui est en fait équivalente, puisque cela revient à démontrer [ P ( n) et P ( n +1)] par récurrence simple.
Comment calculer la récurrence linéaire ?
n) vérie la relation de récurrence linéaire d'ordre 2 suivante : a 0= 0; a 1= 1; 8n2N; a n+2 a n+1 2 a n 2 = 0: Le polynôme caractéristique étant ˜ f, on a déjà calculé sa racines, qui sont 1= 1 et 2= 1 2 .
Combinatoire énumérative
Igor Kortchemski
-Introduction- La Combinatoire est un sous-art des mathématiques qui consiste à compter et à étudierdes structures finies. De nombreux problèmes difficiles sont formulés de manière très simple
(mais la résolution nécessite des outils avancés). Le but de ce cours est de présenter quelques
réflexes et idées de bases pouvant être utiles dans la résolution d"exercices de combinatoire
de type olympiades. On parlera de coefficients binomiaux, double-comptage, injections, surjections, bijections. 1Coef ficientsbinomiaux
1.1Définitions
On rappelle qu"un ensembleEest une collection d"éléments dont l"ordre n"a pas d"impor- tance (ainsi, les ensemblesf2,3getf3,2gsont les mêmes ensembles) et comptés sans multipli- cité (par exemple, 2,2=2). On notex2Asixappartient à l"ensembleA. SiAetBsont deux ensemble, on écritABet on dit queAest inclus dansBsi chaque élément deAappartient à B. L"ensemble vide, qui ne contient aucun élément, est noté;. On note Card(A)(on prononce " cardinal deA») le nombre d"éléments deA. On dit queAest infini si Card(A) =1, fini sinon.Définition 1.Pour des entiers 06k6n, on noten
k(et on prononce "kparmin») le nombrede manières de choisir un sous-ensemble àkéléments d"un ensemble ànéléments différents.
Pourk > n, on posen
k=0. Il est clair que dans la définition précédente, n kne dépend pas de l"ensemble ànéléments différents considéré.Exemple 2.On a4
2=6, car les sous-ensembles à 2 éléments def1,2,3,4gsontf1,2g,f1,3g,
f1,4g,f2,3g,f3,4get il y en a 6 Pour un entiern>1, rappelons la notationn!=123 (n-1)n. On lit "n factorielle". Proposition 3.Le nombre de manières d"ordonnernéléments estn!.Démonstration.Nous avonsnpossibilités pour choisir le premier élément,n-1 possibilités
pour le deuxième, et ainsi de suite jusqu"au dernier élément pour lequel nous avons une seule
possibilité. Le résultat en découle.1Proposition 4.Pour des entiers 06k6n, on a :
n k =n!(n-k)!k!. Démonstration.Utilisons le principe dedouble-comptage, très important en combinatoire. Ilconsiste à établir une égalité en comptant de deux manières différentes une certaines quan-
tité. Ici, comptons le nombre de suites àkéléments qu"on peut créer en utilisant lesnéléments
d"un ensemble ànéléments différents. D"une part, comme pour la proposition précédente, nous avonsnchoix pour le premierterme de la suite;n-1 choix pour le deuxième, et ainsi de suite jusqu"auk-ième élément pour
lequel nous avonsn-k+1 choix. Finalement, il y a en toutn(n-1)(n-k+1) =n!(n-k)!suites àkéléments.
D"autre part, pour créer une suite àkéléments, on peut commencer par choisir leskélé-
ments qui vont constituer la suite (n kpossibilités), puis les ordonner (k! manières possibles de les ordonner). Il y a donc en toutk!n ksuites àkéléments.1.2Propriétés combinatoiresExercice 1Pour des entiers 06k6n, on a :
n k =n n-k Solution de l"exercice 1Première méthode :On utilise la formulen k=n!(n-k)!k!et le résultat en découle immédiatement.Deuxième méthode :On remarque que choisirkéléments parminrevient à sélectionner les
n-kéléments qu"on ne choisira pas. L"exercice précédent, bien que facile, est assez représentatif des exercices ayant pour butde prouver des relations d"égalité entre coefficients binomiaux. Très souvent, il y a toujours
(au moins) deux approches possibles : remplacer les coefficients binomiaux par leur formuleet ramener le problème à un exercice de manipulation de relations algébriques, ou bien inter-
préter de manière combinatoire les deux termes de part et d"autre de l"égalité et prouver qu"ils
sont égaux. La deuxième approche est bien sûr bien plus élégante et fournit très souvent des
preuves courtes, mais requiert davantage d"ingéniosité. Proposition 5.(formule de Pascal) Soientnet 06k6ndes entiers (avec(k,n)6= (0,0)).Alors :
n k =n-1 k +n-1 k-1 2 Démonstration.Pr emièreméthode : On utilise la formule : n-1 k +n-1 k-1 =(n-1)!k!(n-1-k)!+(n-1)!(k-1)!(n-k)! (n-1)!(k-1)!(n-1-k)! 1k +1n-k (n-1)!(k-1)!(n-1-k)! nk(n-k) n!k!(n-k)! f1,2,...,nget dénombrons ses sous-ensembles àkéléments. On distingue les ensembles qui contiennent l"élémentnet les ensembles qui ne le contiennent pas. Il y an-1 kensembles qui ne contiennent pasn(on choisitkéléments dansf1,2,...,nget il y en an-1 k-1qui contiennent n. Au total on a doncn-1 k+n-1 k-1manières de choisir noskéléments parmi nosnentiers,d"où le résultat.La formule de Pascal nous permet ensuite de construire le triangle de Pascal, que vous
connaissez peut-être déjà. La case située dans lak-ième colonne de lan-ième ligne contient le
coefficient binomialn-1 k-1. D"après la formule de Pascal, on obtient donc chaque case comme la somme des deux cases qui sont au-dessus. 111121
1331
14641
15101051
1615201561
172135352171
de(x+y)n: Proposition 6(Formule du binôme de Newton).Soientx,ydes nombres réels etn>1 un entier. Alors : nX k=0 n k x kyn-k= (x+y)n. Notation.Avant de démontrer cette formule, un petit rappel de notation : 3 Lorsqu"on veut faire une grosse somme de termes qui peuvent s"exprimer selon un entier, souvent noték(ouimais cela n"a pas d"importance), qui varie entre deux valeurs, on utilise le symboleP. Par exemple : n X k=01=1+1+...+1=n+1 n X k=0k=0+1+2+...+n=n(n+1)2 n X k=0 n k =n 0 +n 1 +...+n n-1 +n n Pour un produit on utilise de la même manière le symboleQ. Par exemple :
n Y k=1k=n!Démonstration.
Pr emièreméthode : par récurrence surn(s"entraîner à le faire). Seconde méthode :lorsqu"on développe(x+y)(x+y)(x+y), pour trouver le coefficient devantxkyn-k, parmi lesntermes(x+y), il faut en choisirkpour lesquels on garde lexet qui vont donner un termexk, et lesn-kautres termes pour lesquels on sélectionney(et quisont fixés par le choix deskpremiers) vont donner le termeyn-k. Le résultat s"ensuit.Exercice 2Pour tout entiern>1, on a
n X k=0 n k =2n.Exercice 3Pour 06k6n, on a :
k n k =nn-1 k-1 Exercice 4Quel est le cardinal moyen d"un sous-ensemble def1,2,...,ng?Exercice 5Prouver que pour 06m6n:
n X k=0 n k k m =n m 2 n-m. Exercice 6Combien y a-t-il de chemins surZ2issus de(0,0), faisant des pas+(1,0)ou+(0,1), et finissant en(m,n), oùm,n>0? Exercice 7De combien de manières peut-on placer 5 pièces identiques dans 3 poches diffé- rentes? 4 Solution de l"exercice 2Première méthode :Si on n"a pas d"idée comment commencer de ma-nière astucieuse, on peut essayer de procéder par récurrence surn. Pourn=1, le résultat est
clair. Supposons le résultat acquis au rangnet montrons-le au rangn+1 en écrivant, avec la formule de Pascal : n+1X k=0 n+1 k =1+n+1X k=1 n k +n k-1 nX k=1 n k +nX k=0 n k =2n+2n(par hypothèse de récurrence) =2n+1, Seconde méthode :Démontrons ce résultat de manière combinatoire en comptant le nombre Nde sous-ensembles def1,2,...,ng. D"une part, pour un entier 06k6n, il y an ksous- ensembles àkéléments. En sommant le tout, on voit queN=Pn k=0 n k. Mais, pour construire un sous-ensemble def1,2,...,ng, on a le choix de choisir 1 ou non,2 ou non, et ainsi de suite jusqu"àn. On a doncnchoix à faire entre deux possibilités et ces
choix sont indépendants (le choix de prendrekou non n"influence pas le choix de prendrek0 ou non sik6=k0), d"oùN=2n, ce qui permet de conclure. En particulier, la solution précédente montre qu"il existe 2 nsous-ensembles d"un ensembleànéléments.
Troisième méthode :On utilise la formule du binôme de Newton avecx=y=1. Solution de l"exercice 3Première méthode :On utilise la formule exprimantn k(on vous laisse le faire). Seconde méthode :Démontrons ce résultat de manière combinatoire en comptant de deux manières différentes le nombre de sous-ensembles def1,2,...,ngde cardinalkayant un élé- ment distingué (qu"on appellera chef). D"une part, il suffit de choisir un sous-ensemble de cardinalk(n kchoix), puis de choisir un chef (kchoix indépendants). On obtient donc en toutkn kpossibilités. D"autre part, on peut d"abord choisir un chef (nchoix) puis compléter lesk-1 éléments à choisir dansf1,2,...,ngprivé du chef (donc un ensemble àn-1 éléments). Il y a alorsnn-1 k-1éléments.
Solution de l"exercice 4
Première méthode (d"après une idée d"élèves) :On regroupe un ensemble avec son complémen-
taire. SiAf1,2,...,ng, on noteAcl"ensemble des entiers def1,2,...,ngqui ne sont pas dansA. NotonsNce cardinal moyen. Alors :
N=12 nXAf1,2,...,ngCard(A) =12
nXAf1,2,...,ngCardA+Card(Ac)2
12 nXAf1,2,...,ngn2
=12 nn2 2n=n2Autre méthodes :Il faut évaluer la somme
S n=12 nn X k=0kn k 5 Si on ne sait pas commencer, il faut étudier les premiers cas :n=1,2,.... On trouve toujours S n=n=2. Essayer donc de démontrer cela. Seconde méthode :Si on n"a pas d"idée, on peut procéder par récurrence surn.Troisième méthode, plus avancée. On utilise le résultat de la proposition6 . Considérons le
polynômePn(x) =Pn k=0 n kxk. D"après la formule du binôme de Newton,Pn(x) = (1+x)n. Dérivons cette égalité par rapport àx: nX k=0kn k x k-1=n(1+x)n-1.Évaluons alors cette quantité enx=1 :
nX k=0kn k =n2n-1.Le résultat en découle.
Solution de l"exercice 5On remarque d"abord que seuls lesktels quek>mcontribuent de manière non nulle. On va procéder à un double comptage en comptant le nombreNde sous-ensemblesA,Bdef1,2,...,ngtels queABet Card(A) =m. En effet, d"une part, pour construireA,Bon peut d"abord choisirAde cardinalm(n mchoix), puis rajouter un sous- ensemble quelconque de l"ensemblef1,2,...,ngprivé des éléments deA, qui an-méléments (et donc 2 n-mchoix indépendants). En ainsi,N=nquotesdbs_dbs24.pdfusesText_30[PDF] bar en kg
[PDF] kg/cm2 en bar
[PDF] 10 psi en bar
[PDF] convertir pascal en bar
[PDF] convertir mpa en bar
[PDF] 1 mega pa en bar
[PDF] 1 bar en hectopascal
[PDF] 1 mégapascal
[PDF] tableau de conversion cm3
[PDF] tableau de conversion m3 en l
[PDF] 1l en cm3
[PDF] conversion cm en cm3
[PDF] catu am-18/1
[PDF] exemple fiche e6 contexte international