Kombinatorischer Beweis der Identität 3n=∑nk=0(nk)2k3n=∑k=0n(nk)2k3^n=\sum_{k=0}^n \binom nk 2^k

Question

Kombinatorischer Beweis der Identität 3n=∑nk=0(nk)2k3n=∑k=0n(nk)2k3^n=\sum_{k=0}^n \binom nk 2^k

Summe
Mathematik
Kombinatorik
Kombinatorische Beweise
Binomialkoeffizienten

Corp. und Ltd.

Verwenden Sie ein kombinatorisches Argument, um Folgendes zu beweisen: $3^n =$ $\sum_{k=0}^n{n \choose k}2^k.$

Ich habe den mathematischen Beweis dafür gesehen, indem ich die Identität von Pascal verwendet habe; und ich versuche, einen kombinatorischen Beweis / eine Analogie zu finden, um eine Situation in der realen Welt nachzuahmen.

Was LHS betrifft, habe ich mir diese Analogie ausgedacht:

Angenommen, Ihre Aufgabe besteht darin, kostenlose Süßigkeiten zu verteilen.

Am ersten Tag gibst du drei Kindern Süßigkeiten. Am nächsten Tag bringt jeder von ihnen zwei ihrer Freunde mit. Am Tag $n$ , gibst du aus $3^n$ Süßigkeiten.

Kann jemand eine gute Analogie für die RHS liefern, so dass LHS = RHS offensichtlich ist?

Antworten (1)

Kombinatorischer Beweis der Identität 3n=∑nk=0(nk)2k3n=∑k=0n(nk)2k3^n=\sum_{k=0}^n \binom nk 2^k

Brian M. Scott · Answer 1

TIPP: Sie werden es schwer haben, es mit der von Ihnen gewählten Geschichte zum Laufen zu bringen. Versuchen Sie es stattdessen. Du hast $n$ Bonbons, alle in verschiedenen Geschmacksrichtungen, und Sie möchten wissen, auf wie viele verschiedene Arten Sie sie an drei Kinder, Vanessa, Sunny und Melissa, verteilen können. Die Antwort ist eindeutig $3^n$ . Nehmen wir nun an, Sie entscheiden sich für eine Aufteilung $k$ des $n$ Bonbons zwischen Vanessa und Sunny und Melissa den Rest geben; Auf wie viele verschiedene Arten kann man das tun?

So $2^k$ würde die Anzahl der möglichen Funktionen von k an Vanessa und Sunny darstellen, während der Rest automatisch an Melissa geht?

Kombinatorischer Beweis der Identität 3n=∑nk=0(nk)2k3n=∑k=0n(nk)2k3^n=\sum_{k=0}^n \binom nk 2^k

Corp. und Ltd.

Antworten (1)

Brian M. Scott

Corp. und Ltd.

Brian M. Scott

Kombinatorischer Beweis für die Identität ∑nk=0(nk)(−2)k=(−1)n∑k=0n(nk)(−2)k=(−1)n\sum_{k=0}^n \binom{n}{k}\left(-2\right)^k = (-1)^n

Lösungsverifikation: Zeigen Sie, dass ∑ni=0(n+an−i)(i+a+1i)=2n(n+aa)+2n−1(n+aa+1)∑i=0n(n+an−). i)(i+a+1i)=2n(n+aa)+2n−1(n+aa+1)\sum_{i=0}^{n}{\binom{n+a}{ni}\ binom{i+a+1}{i}}=2^{n}\binom{n+a}{a}+2^{n-1}\binom{n+a}{a+1} für n ≥1n≥1n\geq 1

Kombinatorischer Beweis von ∑k=0n(nk)3k=4n∑k=0n(nk)3k=4n\sum\limits_{k=0}^n {n \choose k}3^k=4^n

Kombinatorische Interpretation für die Identität ∑i(mi)(nj−i)=(m+nj)∑i(mi)(nj−i)=(m+nj)\sum\limits_i\binom{m}{i}\ binom{n}{ji}=\binom{m+n}{j}?

Zeigen Sie, dass für r,n∈Nr,n∈Nr,n\in\mathbb{N} mit r≥nr≥nr\geq n, ∑n−1i=0(−1)i(ni)(r+n−). i−1r)=(r−1n−1)∑i=0n−1(−1)i(ni)(r+n−i−1r)=(r−1n−1)\sum_{i=0} ^{n-1} (-1)^i \binom{n}{i} \binom{r+ni-1}{r} = \binom{r-1}{n-1}

Vereinfachen des Produkts mehrerer Binomialentwicklungen

Binomial-/Kombinatorik-Summationsbeweisfrage

Summe des Produkts der Binomialkoeffizienten: ∑nk=0(−1)k(nk)(n+kk)=(−1)n∑k=0n(−1)k(nk)(n+kk)=(− 1)n\sum_{k=0}^{n}(-1)^k\binom{n}{k}\binom{n + k}{k} = (-1)^n

Kombinatorischer Beweis bezüglich fallender Fakultäten und Summen fallender Fakultäten

Kombinatorischer Beweis für Reihen von Stirlingzahlen und Binomialkoeffizienten