Pascals Iterationsformel ist ein (sehr) großartiger Klassiker der EKG-Wettbewerbe, sei es für EDHEC/EM Lyon-Fächer, aber auch für Pariser Fächer. Obwohl es sich weiterhin um ein Randkonzept des Programms handelt, ist es sehr schnell und relativ einfach zu erlernen. Dieser Artikel lädt Sie ein, diese Pascal-Iterationsformel zu analysieren, um Punkte in Ihrem zukünftigen DS, CB oder sogar Wettbewerb zu sichern!
Pascals Iterationsformel
Definition
Soient (n, p in mathbb{N}) tels que (n geq p), (displaystyle sum_{k=p}^{n} {{k} choose {p} } = {{n+1} choose {p+1}}).
Bemerkungen:
- Unter Verwendung der Vervollständigung des Pascalschen Dreiecks durch Nullterme können wir es auch schreiben: (displaystyle sum_{k=0}^{n} {{k} choose {p}} = {{n+1} choose {p+1}}) mit (n, p geq 0 ).
- Zur Erinnerung: Wir wissen, dass (displaystyle {{n} choose {k}} = 0), wenn (k > n).
- Unter Verwendung der Symmetrie der Binomialkoeffizienten erhalten wir die Summe einer absteigenden Diagonale, (displaystyle sum_{k=p}^{n} {{k} choose {kp}} = {{n+1} choose {p+1}}) für (n geq p ).
- Zur Erinnerung: Wir wissen, dass (displaystyle {{n} choose {k}} = {{n} choose {nk}}) mit (n, k in mathbb{N}) und (n geq k).
Erläuterungen
Die Iterationsformel von Pascal, auch Gutterformel (oder Hockeyschlägerformel) genannt, gibt das Ergebnis einer endlichen Summe aufeinanderfolgender Terme einer Spalte des Pascal-Dreiecks, beginnend beim ersten Term ungleich Null, als Binomialkoeffizienten an rechts und unterhalb des letzten Termes.
Grafische Erklärung mit Pascals Dreieck
Die roten Kästchen werden von der Formel für (n)=5, (p)=2 verwendet; in Blau, Fall einer absteigenden Diagonale für die gleichen Werte.
Hinweis: Dank dieses Pascal-Dreiecks verstehen wir die Logik hinter dem Titel „Hockeyschläger-Formel“. Tatsächlich bilden die roten Kästchen, die Elemente der Summe sind, und das rote Kästchen 20, das das Ergebnis der Summe darstellt, eine Art Kreuz.
Beweise der Pascalschen Iterationsformel
Die folgenden ersten Demonstrationen basieren auf einer weiteren Eigenschaft von Pascal, die im Programm enthalten ist: (displaystyle {{n} choose {k}} = {{n-1} choose {k-1}} + {{n – 1} choose {k}}). Wir nennen es „Pascalsche Relation“. Grafisch sehen wir in der obigen Tabelle, dass die Summe zweier aufeinanderfolgender Zahlen in derselben Zeile gleich der Zahl ist, die sich unter der zweiten hinzugefügten Zahl befindet.
Teleskopvorführung
begin{align*} displaystyle sum_{k=p}^{n} {{k} choose {p}} &= sum_{k=p}^{n} left( {{k+1 } choose {p+1}} – {{k} choose {p+1}} right) text{ nach der Beziehung von Pascal} \ &= displaystyle {{p+1} choose {n+1}} – {{p+1} choose {p}} text{ par télescopage} \ &= displaystyle {{p+1} choose {n+1}}. end{align*}
Hinweis: Diese Demonstration der Pascalschen Iterationsformel ist die kürzeste, einfachste und eleganteste der drei. Ich kann es nur wärmstens empfehlen!
Beweis durch Induktion
Montrons que (displaystyle sum_{k=p}^{n} {{k} choose {p}} = {{n+1} choose {p+1}}) mit (n, p in mathbb{N}) und (n geq p).
Initialisierung : Für (n)=(p) erhalten wir 1=1
Vererbung : Sei ein bestimmtes ( n ), das zu ( gehört[![p, +infty[![).
On a : begin{align*} displaystyle sum_{k=p}^{n} {{k} choose {p}} &= {{n+1} choose {p+1}} text{ par hypothèse de récurrence.} \ displaystyle sum_{k=p}^{n+1} {{k} choose {p}} &= sum_{k=p}^{n} {{k} choose {p}} + {{n+1} choose {p}} \ &= {{n+1} choose {p+1}} + {{n+1} choose {p}} \ &= {{n+2} choose {p+1}}. end{align*}
Conclusion : la proposition est initialisée et héréditaire, donc par principe de récurrence, on a démontré la formule d’itération de Pascal.
Remarque : cette démonstration (comme la première) est rigoureuse. Cependant, comme toute récurrence, elle nécessite de connaître au préalable le résultat à démontrer. Ici, la formule d’itération de Pascal. Cela ne devrait pas poser trop de problèmes : la formule étant hors programme, il est quasiment certain que dans des sujets, on te demande « Montrer que… ».
Démonstration par itération de la relation de Pascal
begin{align*} text{On a } displaystyle {{n+1} choose {p+1}} &= {{n} choose {p}} + {{n} choose {p+1}} text{ d’après la relation de Pascal.} \ & = displaystyle {{n} choose {p}} + {{n-1} choose {p}} + {{n-1} choose {p+1}} \ & = displaystyle {{n} choose {p}} + {{n-1} choose {p}} + dots + {{n-k} choose {p}} + {{n-k} choose {p+1}} end{align*}
On pose (k)= (n) – (p) :
On a (displaystyle {{n+1} choose {p+1}} = {{n} choose {p}} + {{n-1} choose {p}} + cdots + {{p} choose {p}} + {{p} choose {p+1}}) ce qui donne bien la formule voulue.
Remarque : cette démonstration peut être utile à comprendre. Cependant, je ne conseille pas de l’apprendre et de l’utiliser, car les « … » sont souvent mal vus par des correcteurs très rigoureux. Privilégie la démonstration 1 ou 2.
Remarque générale : on peut également trouver des démonstrations de la formule d’itération de Pascal qui reposent sur la formule des séries géométriques ou encore sur le dénombrement, mais mieux vaut tout de même privilégier les démonstrations n° 1 et n° 2, bien plus classiques et plus connues des correcteurs. De plus, elles ne sont pas évidentes à comprendre et pourraient causer des erreurs d’étourderie.
Utilisation de la formule d’itération de Pascal
Exemples pratiques
La formule d’itération de Pascal est particulièrement utile pour retrouver les formules des sommes des premières puissances.
Si on développe notre formule, on obtient : [ displaystyle sum_{k=p}^{n} {k(k-1)cdots(k-p+1)} = frac{(n+1)(n)cdots(n-p+1)}{(p+1)}. ]
Für (p)=1 erhalten wir die Summe der ersten n natürlichen ganzen Zahlen: [ displaystyle sum_{k=1}^{n} k = frac{n(n+1)}{2}. ]
Für (p)=2 finden wir [ displaystyle sum_{k=2}^{n} k(k-1) = frac{n(n-1)(n+1)}{3}, ] was es uns ermöglicht, anschließend die Summe der ersten n Quadrate zu erhalten, die wert ist[ displaystyle sum_{k=1}^{n} k^2 = frac{n(n+1)(2n+1)}{6}. ]
Und für (p)=3, (p)=4…
Eines ist sicher: Wenn Sie in einem Fach die Iterationsformel von Pascal demonstrieren müssen, müssen Sie sie in den folgenden Fragen verwenden. Also bleiben Sie dran!
Anwendungen aus der Praxis
Die Iterationsformel von Pascal wird in verschiedenen Bereichen angewendet, um kombinatorische Berechnungen zu vereinfachen und Algorithmen zu optimieren:
- In der kombinatorischen Analyse zur Bestimmung der Summe von Binomialkoeffizienten und zur Erleichterung der Zählung von Teilmengen.
- In der Informatik zur Optimierung von Algorithmen und zur Vereinfachung von Komplexitätsausdrücken.
- In der Wahrscheinlichkeitsrechnung und Statistik zur Berechnung der Erwartungen und Varianzen kombinatorischer Zufallsvariablen.
- In der Graphentheorie zum Zählen von Pfaden und Zyklen.
- In der Genetik zur Analyse von Merkmalskombinationen.
- In der Wirtschaftswissenschaft und Betriebsforschung zur Modellierung und Optimierung von Entscheidungen und Systemen.
Summe der Umkehrungen der Terme einer Spalte des Pascalschen Dreiecks
Gießen Sie ( displaystyle n geq p geq 2 ),
[ displaystyle sum_{k=p}^{n} frac{1}{displaystyle {k choose p}} = frac{p}{p-1} left(1 – frac{1}{displaystyle {n choose p-1}}right) ]
ALSO, [ displaystyle sum_{k=p}^{infty} frac{1}{displaystyle {k choose p}} = frac{p}{p-1} ] Wir kommen zum vorherigen Ergebnis, weil [ displaystyle sum_{k=p}^{infty} frac{1}{displaystyle {k choose p}} = displaystyle sum_{k=p}^{n} frac{1}{displaystyle {k choose p}} + displaystyle sum_{k=n+1}^{infty} frac{1}{displaystyle {k choose p}} ]
und durch Teleskopieren von [ displaystyle frac{1}{displaystyle {k choose p}} = frac{p}{p-1} left( frac{1}{displaystyle {k-1 choose p-1}} – frac{1}{displaystyle {k choose p-1}} right) ] was aus der Beziehung kommt: [ displaystyle (p-1) {k-1 choose p-1} {k choose p-1} = p {k-2 choose p-1} {k choose p} ]
Schließlich können wir die Summe wie folgt schreiben: [ displaystyle sum_{k=p}^{infty} frac{1}{k(k-1)cdots (k-p+1)} = frac{1}{(p-1)!(p-1)} ]
Thema, das den Beweis der Pascal-Iteration aufruft
EDHEC 2016-Problem
Abschluss
Jetzt beherrschen Sie die Iterationsformel von Pascal, sind in der Lage, diesen Zusammenhang zu demonstrieren und verstehen seine vielfältigen Anwendungsmöglichkeiten! Obwohl dieses Konzept möglicherweise nicht auf dem Programm steht, ist es für Sie von Nutzen, es zu verstehen, wenn Sie auf komplexe kombinatorische Probleme stoßen. Wir hoffen, dass dieser Artikel von Major-prépa Ihnen Klarheit verschafft und Ihr Verständnis von kombinatorischen Werkzeugen bereichert hat.
Hier finden Sie das Mega-Verzeichnis, das alle Wettbewerbsaufzeichnungen und die Antworten enthält. Sie können auch auf alle unsere anderen Mathe-Ressourcen zugreifen!
Related News :