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

Question

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

Summe
Mathematik
Kombinatorik
Kombinatorische Beweise
Binomialkoeffizienten

Terrasse

Ich weiß, wie man diese Identität algebraisch beweist, aber das ist die dumm langweilige Art, Probleme zu lösen. Mir fällt dafür kein kombinatorischer Beweis ein, wie bei der Verwendung von Zählausschüssen oder ähnlichem. Es ist schwer, mit dem Negativen umzugehen $2$ ...

\sum_{k = 0}^{N} (\binom{N}{k}) {(- 2)}^{k} = (- 1)^{N}

$\displaystyle\sum_{k=0}^n \binom{n}{k}\left(-2\right)^k = (-1)^n$

Jede Hilfe ist willkommen, danke!

hmakholm hat Monica übrig gelassen

(1 - 2)^{n}

$(1-2)^n$ . Binomialsatz.

Lerner

@HenningMakholm, die Fragen fragen nach einem kombinatorischen Beweis. Der algebraische Beweis ist trivial.

Terrasse

@HenningMakholm Wow, das ist viel einfacher als das, was ich mir vorgestellt hatte, als ich es algebraisch bewies. Ich hasse Induktion (ich denke, es nimmt den Spaß daran, Dinge zu beweisen) und ich habe es durch Induktion gemacht ...

Antworten (1)

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

@HenningMakholm, die Fragen fragen nach einem kombinatorischen Beweis. Der algebraische Beweis ist trivial.
@HenningMakholm Wow, das ist viel einfacher als das, was ich mir vorgestellt hatte, als ich es algebraisch bewies. Ich hasse Induktion (ich denke, es nimmt den Spaß daran, Dinge zu beweisen) und ich habe es durch Induktion gemacht ...

Brian M. Scott · Answer 1

Der natürlichste kombinatorische Beweis beginnt mit der Multiplikation der gewünschten Identität mit $(-1)^n$ es zu machen

\sum_{k = 0}^{N} (\binom{N}{k}) 2^{k} (- 1)^{N - k} = 1 .

$\sum_{k=0}^n\binom{n}k2^k(-1)^{n-k}=1\;.$

Natürlich ergibt sich dies unmittelbar aus dem Binomialsatz, aber wenn Sie etwas expliziteres Kombinatorisches wollen, können Sie es ersetzen $k$ von $n-k$ zu bekommen

\sum_{k = 0}^{N} (\binom{N}{k}) (- 1)^{k} 2^{N - k} = 1 .

$\sum_{k=0}^n\binom{n}k(-1)^k2^{n-k}=1\;.$

Angenommen, wir wollen die Teilmengen von zählen $[n]=\{1,\ldots,n\}$ die kein Element von enthalten $[n]$ . Natürlich ist die einzige solche Teilmenge $\varnothing$ , so sollte der Wert sein $1$ . Andererseits, wenn z $k\in[n]$ wir lassen $\mathscr{A}_k$ sei die Familie der Teilmengen von $[n]$ enthält $k$ , dann für alle nicht leeren $F\subseteq[n]$ wir haben

| ⋂_{k \in F} A_{k} | = 2^{N - k},

$\left|\bigcap_{k\in F}\mathscr{A}_k\right|=2^{n-k}\;,$

und da sind $\binom{n}k$ solch $F\subseteq[n]$ , das Ergebnis folgt also aus dem Inklusions-Exklusions-Prinzip .

Vielen Dank für eine sehr coole Herangehensweise an das Problem! Vielleicht ist der algebraische Weg doch einfacher - ich habe es durch Induktion gemacht, was ich als Beweistechnik für äußerst langweilig / uninteressant halte, ich habe nicht erkannt, dass es möglich ist, einfach zu erweitern $(1-2)^n$ wie Henning Makholm betonte.

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

Terrasse

hmakholm hat Monica übrig gelassen

Lerner

Terrasse

Antworten (1)

Brian M. Scott

Terrasse

Brian M. Scott

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

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