Chap A : entiers, r ecurrences, formules sommatoires

1 Montrer qu’il s’agit d’un sch´ema de Bernoulli 2 Repr´esenter la situation par un arbre pond´er´e 3 On note X la variable al´eatoire ´egale au nombre d’as tir´es Donner la loi de probabilit´e de X Exercice 11 La variable al´eatoire X suit la loi binomiale de param`etres n= 100 et p= 0,15 1

Classification M1-MASS

Loi binomiale D´eﬁnition Soient Y 1,··· ,Y n n va ind´ependantes suivant une loi de Bernoulli de param`etre π, alors on dit que la somme de ces variables suit une loi binomiale de param`etre n,π Y = Y 1 +···+Y n ∼ B(n,π) E(Y) = nπ var(Y) = nπ(1−π) ObjectifOn fait n exp´eriences succ`es/´echec , on veut mod´eliser le

Chap A : entiers, r ecurrences, formules sommatoires

Lien avec les exp eriences de Bernoulli vues en premi ere Le point de vue choisi en premi ere : on y a d e ni ›n k ” comme le nombre de chemins de l’arbre donnant ksucc es pour nr ep etitions Il a et e d emontr e en raisonnant sur les chemins les relations : ∀n≥2, ∀p∈B1;n−1G, ›n p ”=›n−1 p ”+›n−1 p−1 ”

Planche d’exercices 55 - joffrempsi1

qu’il n’a pas pu joindre au cours de la premi ere s erie d’appels On note Y le nombre de personnes jointes au cours de la seconde s erie d’appels i) Soit i ∈B0;nG D eterminer pour k ∈N, P(Y =kSX =i) ii) Prouver que Z =X +Y suit une loi binomiale dont on d eterminera les param etres iii) D eterminer l’esp erance et la variance

Probabilités, statistique et applications

de premi ere importance en sciences appliqu ees Il y est aussi question de la r egression curviligne La abilit e, qui intervient dans la plupart des disciplines du g enie, et particu-li erement en g enie m ecanique, fait l’objet du chapitre 8 Les notions pr esent ees g en eralisent les notions de base de abilit e vues au chapitre 2

glm(Y/N ++Xk,family=binomial,weights=N)

rappel e dans le plan de cours, la triche est interdite Dans les feuilles qui suivent, il y a 42 questions, question 1 (pr eliminaire) sur la r egression binomiale (total de 3 points) questions 2-20 sur la gravit e d’accidents de la route (total de 20 points) questions 21-34 sur le provisionnement pour sinistres a payer (total de 15 points)

Ann´ee universitaire 2002-2003 UNIVERSITE D’ORL´ EANS

Ann´ee universitaire 2002-2003 UNIVERSITE D’ORL´ EANS´ Olivier GARET MA6 06 : Mesure et Probabilit´es

Ann´ee universitaire 2006-2007 UNIVERSITE D’ORL´ EANS

Ann´ee universitaire 2006-2007 UNIVERSITE D’ORL´ EANS´ Olivier GARET Int´egration, Fourier et Probabilit´es

[PDF] Exercices d 'algorithmique en seconde Probabilités #8211 statistiques

[PDF] simulations, algorithmes en probabilités et statistique(s) au - Apmep

[PDF] Probabilités, simulation et algorithmique (pour TI)

[PDF] Algorithmes et programmation en Pascal TD corrigés - Limuniv-mrsfr

[PDF] Notes de cours / Algo et Python

[PDF] Algorithmique et Programmation Projet : algorithme de - DI ENS

[PDF] Score ASIA

[PDF] Un algorithme de simulation pour résoudre un problème de probabilité

[PDF] Algorithmique en classe de première avec AlgoBox - Xm1 Math

[PDF] Algorithme U prend la valeur [expression de la suite - Maths en ligne

[PDF] Rappels sur les suites - Algorithme - Lycée d 'Adultes

[PDF] Algorithme U prend la valeur [expression de la suite - Maths en ligne

[PDF] Algorithmique et Suites numériques Utiliser un algorithme avec les

[PDF] Les tableaux - Luc Brun

[PDF] Les tableaux 1 Exercice 1 - Lipn

MPSI 1Semaine 2, du 2 au 6 octobre 2017Chap. A

2: entiers, recurrences, formules sommatoiresToute l'arithmetique est la consequence de l'acte de compter.

J. Stillwell, les mathematiques et leur histoire.

I L'ensembleNet le raisonnement par recurrence :

1) Un peu de theorie surN:

On presente ici les proprietes fondamentales de l'ensemble des entiers naturels. Quand on re- garde les entiers ≪dans leur ensemble≫(i.e. plut^ot qu'isolement), fondamentale est la notion de

successeur: un enfant sait vraiment compter quand il sait compter≪jusqu'a l'inni≫ce qui veut

dire plut^ot qu'il sait donner le successeur de n'importe quel nombre. Les mathematiciens aiment comprendre les relations entre des proprietes,deduire. Il est re- marquable quetoutesles proprietes des nombres entiers se deduisent de celles de l'application successeur≫, qui a un entiernassocie celui qu'on va appelern+1. Cela a conduit a donner la denitiondeNdonnee au a), par une liste de proprietes ouaxiomes. Cette denition n'est pas a savoir par coeur. Elle entra^ne les proprietes donnees du b) au d), qui,elles,sont a bien conna^tre, m^eme si leur demonstration a partir des axiomes a) n'est pas exigible.

a) Axiomes de Peano pourN(H.P, non exigible)Il existe un ensembleessentiellement uniquenoteN, muni d'une applications?N→N

avec les proprietes : (i)sestinjective, ce qui signie que?(x;y)?N2,x≠y?s(x)≠s(y). (ii) il existe dansNun element note 0 qui n'est le successeur d'aucun element deN.

(iii) pour tout sous-ensembleAdeN, siAcontient 0 et est stable pars, alorsA=N.Notation :On note 1=s(0), et pour toutn?N, on notes(n)=n+1.

Remarque 1 :Suivant qu'on considere par exemple,les entiers ecrits en base dix, a l'aide des chires 0;1;2;:::;9 oules entiers ecrits en base deux, a l'aide seulement des chires 0;1, on obtient desensembles dierentspuisque formes avec des objets dierents. Cependant ce qui signie l'expressionessentiellement uniquedans l'encadre ci-dessus, est qu'il existe une (unique) bijection deNbase deuxdansNbase dixcompatible avec l'application successeur Remarque 2 :Par denition, un nombre entier naturel est un element de l'ensembleN. On ne denit pas ici, la notion de nombre entierisolement. b) Consequence a conna^tre : principe de recurrence : Thm. (H)On considere unpredicatP(n)dependant d'une variablen?Nqui verie les deux proprietes suivantes : ?Initialisation :P(0)est vraie, ?Heredite : pour toutn?N, l'implication[P(n)?P(n+1)]est vraie. (C)Alors la proprieteP(n)est vraie pour toutn?N

Demonstration :

c) Notion de suitedenie par recurrence : (i)Def.Une suiteud'elements d'un ensembleA(p.ex.A=R) est une applicationu?N→A. (ii)Vous avez l'habitude, au lycee, dedenirdes suites par recurrence, en disant p.ex.u0=2, et pour toutn?N,un+1=2u2n+un. (iii) Le fait que les donnees du (ii) denissent bienune unique applicationu?N→Rest une consequence de l'axiome de recurrence du a) (iii). L'idee est qu'on determineupar ses restriction successivesu?⟦0;n⟧pour tous lesn?N. d) Retour sur les prop. fondamentales deN: (i) Def. de loi+(par recurrence!) Soitn?N, on denit l'application addnN→N,m↦addn(m)par recurrence comme suit : ?addn(0)=n, ? ?m?N, addn(m+1)=addn(m)+1. 1 MPSI 1Semaine 2, du 2 au 6 octobre 2017Notation : add n(m)=m+n.

Deux proprietes tres importantesa retenir, m^eme si elles sont tres intuitives!(P1) Toute partie non vide deNadmet un plus petit element.

(P2) Toute partie non vide deNmajoree admet un plus grand element.La dem. en est admise, mais bien s^ur, elles se prouvent par recurrence.

(iii) Def. loi×: Soitn?N, on denit l'application multn?N→N,m↦multn(m)par recurrence comme suit : ?multn(0)=0, ? ?m?N, multn(m+1)=multn(m)+n.

Notation : mult

n(m)=m×n=m:n. Les def. du (i) et (iii) ne sont pas exigibles a ce stade, elles serviront cependant en info. Les prop. de l'ordre donnees au (ii) doivent ^etre sues. (iv) On admettra dans la suite toutes les prop. bien connues de+et×dansN: elles se montreraient par recurrence!

Penser que s'il est facile de

≪voir sur un dessin≫que2×3=3×2, c'est moins immediat avec des nombres a 4 chires par exemple, merci la recurrence! e) Une nouvelle fonction importante deNdansN: la factorielle a) Def. (i) :n!=1×2×???×n(ii) Plus formellement : par recurrence. (iii) Conna^tre 0!,1!, 2!,3!,4!,5!. b) En anticipant sur le denombrement (pas de dem. formelle) :n! est le nombre depermutations denelements distincts i.e. defacons de les ordonner. Exemple pourn=3.

2) Pratique du raisonnement par recurrence :

a)Consigne de redaction:#" !On doitenoncer clairement le predicatP(n)que l'on veut demontrer. Si on veut montrer que pour toutn?N≥n0;P(n)est vraie, on montre que : ?Initialisation :P(n0)est vraie, ?Hypothese de recurrence (H.R) : soitn?N≥n0tel queP(n)est vraie.

Montrons queP(n+1)est vraie.

On conclut a la n : la recurrence est etablie.

Remarque :Ce raisonnement≪recurrence a partir d'un certain rang≫est valide car c'est l'application du 1) b) a la propriete b) Exercice : comparer 2 netn! pour toutn?N. c) Pratique de la recurrence ≪forte≫: (i)Dans l'H.R., au lieu de supposer qu'on aP(n)vraie pour un certainn, on suppose qu'on a, pour (ii) Exple : montrer que tout entier dierent de 1 admet un diviseur premier. (iii)N.B. {La validite de la rec. forte se deduit du principe de rec. usuel applique a la propriete (iv)Remarque :Alternative possible au (ii) a la preuve par rec. forte : utiliser le fait qu'une partie non vide deNadmet un plus petit element. d) Erreurs usuelles :oubli de l'initialisation, formulation de l'H.R. avec un?nou erreur du type exercice pl. e) Exemples de suites denies par rec. : (i) Suites arithmetiques : def. par rec. et ecriture expliciteun=u0+na. (ii) Suites geometriques : def. par rec. et ecriture expliciteun=anu0. f) Cas des recurrences doubles sur l'exemple de la suite de Fibonacci : On noteF0=0,F1=1 et?n?N; Fn+2=Fn+1+Fn. La suite(Fn)est appeleesuite de Fibonacci. 2 MPSI 1Semaine 2, du 2 au 6 octobre 2017Une formule ≪tombee du ciel≫(pour l'instant) : montrer que?n?N,Fn=1⎷5 ('n- n)ou '=1+⎷5 2 et =1-⎷5 2

3) Pratique de la recurrence sur l'exemple de la formule du bin^ome de Pascal-

Newton

a) Developpement de(a+b)npournpetit : arbre de developpement. Lien avec les experiences de Bernoulli vues en premiere.

Le point de vue choisi en premiere :on y adeni?n

k?comme le nombre de chemins de l'arbre donnantksucces pournrepetitions. Il a ete demontre en raisonnant sur les chemins les relations : ? ?n≥2,?p?⟦1;n-1⟧,?n p?=?n-1 p?+?n-1 p-1? ? ?n≥1,?k?⟦0;n⟧;?n k?=?n n-k?. b)Changement de point de vue ici : Def. plus mathematique, plus numerique, des binomiaux : par recurrence (double) enpartant de la relation du a)

Denition -On denit le coe. binomial?n

p?pour toutn?Net toutp?⟦0;n⟧par | Initialisation :?n?N?n 0?=?n n?=1, | Relation de recurrence :?n≥2,?p?⟦1;n-1⟧,?n p?=?n-1 p?+?n-1 p-1? c) Prop. (les coecients binomiaux ?n p?sont bien les coecients du bin^ome(a+b)n). ?(a;b)?R2;?n?N;(a+b)n=?n

0?an+?n

1?an-1b+⋯+?n

k?an-kbk+⋯+?n n?bn: Preuve par recurrencede la formule du bin^ome, imparfaite car il reste des petits points....

4) Ecriture explicite pour les coe. binomiaux avec des factorielles :

a) Prop.?n p?=n!p!(n-p)!=n(n-1):::(n-p+1)p!. b) Preuve par recurrence (frustrante car c'est une verication, mais a bien ma^triser au ni- veau de la redaction) :formulation correcte deP(n)avec le?k?⟦0;n⟧, reduction au m^eme denominateur.... c) Commenttrouve-t-onla formule : en faisant du denombrement cf. 2eme semestre. !Lorsqu'on veut montrer quelque chose sur les binomiaux : on peut donc penser : ?A la formule du triangle de Pascal (formule de recurrence), ?A les voir comme coecients d'un bin^ome(a+b)nou(1+x)n. ?A la formule explicite?n p?=n!p!(n-p)!=n(n-1):::(n-p+1)p!. ?Nous reviendrons plus tard sur l'aspect denombrement :≪pparmin≫. Appendice au I : pour ceux qui se poseraient des questions... nonexigible

A propos des proprietes de l'ordre dansN

Dans le cours, on a deniNa partir des axiomes de Peano. Il y a d'autres facons de denirN, notamment a partir des deux proprietes de l'ordre dansNqu'on a citees. On ne donnera pas ici les axiomes dans ce cas car il faudrait deja preciser ce qu'est unerelation d'ordreen general... nous en reparlerons. Ici, nous voulons montrer comment d'un c^ote on peut demontrer les proprietes de l'ordre a

partir de l'axiome de recurrence, et comment, dans l'autre sens, on pourrait s'en servir pour deduire

l'axiome de recurrence. On note encoreP1la propriete :≪toute partie non vide deNadmet un plus petit element≫. ?Comment on montre P1a partir de l'axiome de recurrence : SoitAune partie deNqui n'a pas de plus petit element. Montrons par recurrence (forte) que Aest l'ensemble vide. Precisement, on considere le predicatP(n)?n??A. 3

MPSI 1Semaine 2, du 2 au 6 octobre 2017?Comme 0 est le plus petit element deN, 0??A, sinon 0 serait le plus petit element deA. Donc

P(0)est vrai.

def. le plus petit element deA,contradictiondoncn+1??AetP(n+1)est vrai. La rec. est etablie.?Comment on montre que P1entra^ne l'axiome de recurrence : On suppose donc qu'on sait que toute partie non vide deNadmet un plus petit element. Soit

A?N, tel queA?0 et?n?A,n+1. Montrons queA=N.

Par l'absurdesiA≠N, alorsAc≠∅et doncAcadmet un plus petit elementm?N. Comme

0?A,m≠0 et doncm-1?Net commemest le plus petit element deAc,m-1 n'est pas dans

A cdoncm-1?A. Mais alors(m-1)+1?Apar hypothese surAdoncm?A,contradiction. Ce qui precede n'interessera que ceux qui ont l'^ame ≪theoricienne≫. En revanche, il faut avoir compris l'exemple du cours ou l'on peut utiliser aussi bien une recurrence ou l'existence d'un minimum pour montrer une propriete (l'existence d'un diviseur premier) Exercice amusant... qu'on peut resoudre en cherchant un minimum...

Soitnun entier naturel non nul.

On se donne dans le plan 2npoints, notesF1;:::;FnetP1;:::;Pn,trois par trois non alignes. Chaque pointF1;:::;Fnrepresente une ferme et chaque pointP1;:::;Pnun puit. On veut fabriquer des chemins en ligne droite reliant chaque ferme a un puit dierent. Est-il possible de le faire de sorte qu'aucun des chemins ne croise un autre (les fermiers ont tous mauvais caractere)?

II Formules sommatoires : symbole

1) Notation

a) (i) Def intuitive :n i=0a i=a0+⋯+an. (ii) Def. plus rigoureuse de n i=0a i? b) Sens de la variablei:n i=0a i=n j=0a j=? i?⟦0;n⟧a i.

Notion de variable muette.

c) En info. : comment calculer une somme a l'aide d'une bouclefor:

Pour calculer

100
i=1i, on peut proceder comme suit, ce qui suit les dieses#est un commentaire, qui n'est pas lu par la machine. S=0 # on cree une variable S a laquelle on affecte (symbole =) la valeur 0 for i in range(101): # i va prendre successivement les valeurs 0,1,..., 100 S=S+i # a chaque tour de boucle on ajoute i a la valeur precedente de S print(S) d) Trois regles de calculs (distrib. , regroupement, changement d'indice) e) Application :redaction de la preuve de la formule du bin^ome avec des∑ f) Reformulation ≪polynomiale≫de la formule du bin^ome : (1+x)n=n k=0?n k?xk: Application : valeur de la somme de tous les binomiaux d'une m^eme ligne du triangle de Pascal : n k=0?n k?= 4 MPSI 1Semaine 2, du 2 au 6 octobre 20172) Exemples de formules sommatoires : les ∑comme alternative aux recurrences a) L'astuce du petit Gauss pourSn=1+2+⋯+n: idee regroupmt de termes, redac.∑. b) Generalisation aux suite arithmetiques :a savoir absolument : Somme des termes :(Premier terme+dernier terme)×nombre de termes?2

Ecriture de la preuve avec les

c) Somme des termes d'une suite geometrique. :a savoir absolument : (Premier terme-successeur du dernier)?(1-la raison)

Preuve : telescopage a voir sans

∑et avec∑!

3) Principe general des sommes telescopiques :

a) L'essentiel :

Formule :

q k=p(uk+1-uk)=uq+1-up. b) Exemple d'application : (i) Exo. ≪frustant≫:verierquen k=1k2=n(n+1)(2n+1)6 (ii) Methode pour ≪decouvrir la formule≫. En notantuk=k2pour toutk?N, on cherche(vk)telle quevk+1-vk=uk, ou a peu pres! Ici, on essaievk=k3(analogie avec la derivation...) (iii) Fin de l'exercice : factorisation du resultat. (iv) Exercice a faire : donner de m^eme une formule pour n k=1k3. c) Application des sommes telescopique a une identite remarquable importante :

(i) Prop.?(a;b)?R2;?n?N?,an-bn=(a-b)(an-1+an-2b+⋯+an-kbk-1+???+abn-2+bn-1).Preuve facile en allant de ...

(ii) Interpretation de cette formule poura≠0, en passant en variablex=b?a.

4) Variante multiplicative des

a) Def den i=1a i: par recurrence. b) Exemple de calcul : n i=1(ai)= n i=1(aibi)=

III T.D. Cours : manipulations de

?et de sommes doubles

0) Presentation des sommes doubles :

On considere une famille(ai;j)de nombres reels indexee par des indices(i;j)?⟦1;n⟧×⟦1;p⟧.

On peut visualiser cette famille par un tableau, l'indiceirepresentant par convention l'indice ligne et l'indicejl'indice colonne.a 1;1a

1;2⋯a

1;j⋯a

1;pa 2;1a

2;2⋯a

2;j⋯a

2;p?⋯?

a i;1a i;2⋯a i;j⋯a i;p?⋯? a n;1⋯a n;ja n;pGr^ace a la commutativite (et l'associativite!) de l'addition dansR, on peut faire la somme de MPSI 1Semaine 2, du 2 au 6 octobre 20171) Sommation ligne par ligne ou colonne par colonne : a) Si on somme ligne par ligne : On noteila somme des elements dans la lignei. Ainsi1=p j=1a

1;j,2=p

j=1a

2;jet d'une

maniere generale : $%La somme des elements de la ligneiest : i=p j=1a i;j: Il faut bien noter que dans cette formule les variablesietjjouent un r^ole tres dierent : la variableiest externe au symbole∑alors que lejest lecompteurqui sert a sommer, variable interne au symbole Ainsi, si on choisit de d'abord faire la somme des elements lignes par lignes, on peut calculerS comme :S=n i=1 i=n i=1?p j=1a i;j?(2)b) De m^eme si on somme colonne par colonne :La somme1des elements de la colonne 1 vaut1=n i=1a i;1et d'une maniere generale :

La somme des elements de la colonnejest :j=n

i=1a i;j: De m^eme, en faisant la somme des elements colonne par colonne :S=p j=1?n i=1a i;j?:(3)c) Exercice d'application :Calculer la sommeS0=? (i;j)?⟦1;n⟧2(i+j).

2) Un exemple de sommation en diagonale :

N.B.On garde les notations du 1), mais on considere maintenant quep=n, autrement dit un tableau carre dont les entrees sont les(ai;j)(i;j)?⟦1;n⟧2.

Considerons le tableau forme par lesindices(i;j)?⟦1;n⟧×⟦1;n⟧, a distinguer dutableau des

valeursdonne au 1). On peut le voir comme un sous-ensemble deN2represente dans un repere

(peut-^etre australien) ou l'axe des \abscisses" est vertical vers le bas et l'axe des ordonnes horizontal

vers la droite :(1;1)(1;2)(1;3)⋯(1;j)⋯(1;n)(2;1)(2;2)(2;3)⋯(2;j)⋯(2;n)(3;1)(3;2)(3;3)⋯(3;j)⋯(3;n)?⋯?

(i;1)(i;2)⋯(i;j)⋯(i;n)?⋯? (n;1)⋯(n;j)(n;n)a) On note k={(i;j)?⟦1;n⟧2;i-j=k}. A quoi correspond l'ensemble des indices dans 0, 1, -1 sur le tableau ci-dessus? Decrire d'une maniere generale ce que represente k. b) On note encoreS=? (i;j)?⟦1;n⟧2a i;j. On trouve aussi l'abus de notation courant suivant :S= i;j. 6 MPSI 1Semaine 2, du 2 au 6 octobre 2017Justier qu'on peut exprimerSsous la forme suivante : S=N k=-N?? (i;j)?ka i;j?;(?) en precisant la valeur de l'entierN. N.B. : L'ensemble des indices⟦1;n⟧2etant xe, on notera plus simplement l'egalite(?)sous la forme :S=N k=-N?? (i;j);i-j=ka i;j?(4). c)Exercice d'application :Calculer de deux manieres dierentes :S1=? (i;j)?⟦1;n⟧2?i-j?.

3) Un exemple de sommation avec d'autres decoupage de⟦1;n⟧2

Exercice :Calculer de plusieurs manieres dierentesS2=? jsinon.

4) Produits de sommes

Rappel :Dans une ecrituren

i=1, on a dit que l'indiceiest muet, interne au∑. On peut donc l'utiliser dans plusieurs ∑et ecrire par exemple :n i=1a i+n i=1b iavec le m^eme indicei. Mais il convient d'^etre prudent pour les produits de la forme(n i=1a i)(n i=1b i). En eet, par exemple sin=2 et qu'on developpe ce produit(a1+a2)(b1+b2)on aura quatre termes a

[PDF] Chap A : entiers, r ecurrences, formules sommatoires