Inklusion-Exklusion-Formel für ungerade n beweisen

Question

Aufgabe:

Es gilt zu beweisen, dass für alle geraden n gilt:

$$ \sum\limits_{k=0}^{n}(-1)^k \binom{n}{k} = 0 $$

Ansatz:

Wir haben bereits bewiesen, dass dies für ungerade n gilt.

Wir wissen, dass auch gilt: (1)

$$ \binom{n}{k} = \binom{n-1}{k} + \binom{n-1}{k-1}$$

Meine Lösung wäre nun folgendes gewesen:

Wenn (1) gilt, dann gilt auch:

$$ \sum\limits_{k=0}^{n}(-1)^k \binom{n}{k} =  \sum\limits_{k=0}^{n}(-1)^k \binom{n-1}{k} + \sum\limits_{k=0}^{n}(-1)^k \binom{n-1}{k-1} $$

Wir wissen, dass die Annahme für ungerade n gilt.

Also gilt:

$$  \sum\limits_{k=0}^{n}(-1)^k \binom{n-1}{k} = 0 $$

Somit müsste für die Annahme (geltend für gerade n) dies zutreffen:

$$ \sum\limits_{k=0}^{n}(-1)^k \binom{n-1}{k-1} = 0$$

Dies trifft auch zu, da auch hier n-1 ein ungerades n darstellt.

Durch k-1 ist unser erster Binomialkoeffzient ist zwar (n -1 "über" -1), da dies aber 0 ist, macht das letztlich keinen Unterschied.

Macht dieser Lösungsweg irgendwie Sinn oder ist das völlig falsch?

Wenn es falsch ist, was wäre denn der richtige Ansatz, ohne die Lösung vorwegzunehmen?

(so wie ich es verstanden habe, sollen wir für den Beweis die rekursive Formel des Binomialkoeffzienten benutzen; siehe oben)

Answer 1

Aloha :)

Wenn du in den binomischen Lehrsatz:$$(a+b)^n=\sum\limits_{k=0}^n\binom{n}{k}a^k\,b^{n-k}$$für \(a=(-1)\) und für \(b=1\) einsetzt, bist du fertig:$$\sum\limits_{k=0}^n(-1)^k\binom{n}{k}=\sum\limits_{k=0}^n\binom{n}{k}(-1)^k\cdot1^{n-k}=((-1)+1)^n=0^n=0$$

Du kannst deinen Beweis aber auch weiterführen. Alledings musst du auf die Indexgrenzen achten, in deiner letzten Summe wäre im \((k=0)\)-Term \(\binom{n-1}{-1}\) enthalten, was aber nicht definiert ist. Daher musst du diesen Fall vorher aus der Summe ziehen:$$\sum\limits_{k=0}^n(-1)^k\binom{n}{k}=(-1)^0\binom{n}{0}+\sum\limits_{k=1}^n(-1)^k\binom{n}{k}$$$$\phantom{\sum\limits_{k=0}^n(-1)^n\binom{n}{k}}=1+\sum\limits_{k=1}^n(-1)^k\binom{n-1}{k}+\sum\limits_{k=1}^n(-1)^k\binom{n-1}{k-1}$$Jetzt machst du eine Indexverschiebung:$$\phantom{\sum\limits_{k=0}^n(-1)^n\binom{n}{k}}=1+\sum\limits_{k=1}^{n}(-1)^{k}\binom{n-1}{k}+\sum\limits_{k=0}^{n-1}(-1)^{k+1}\binom{n-1}{(k+1)-1}$$$$\phantom{\sum\limits_{k=0}^n(-1)^n\binom{n}{k}}=1+\sum\limits_{k=1}^{n}(-1)^{k}\binom{n-1}{k}-\sum\limits_{k=0}^{n-1}(-1)^{k}\binom{n-1}{k}$$Da \(\binom{n-1}{n}=0\) ist, kannst du die Obergrenze der ersten Summe von \(n\) auf \((n-1)\) setzen. In der zweiten Summe spaltest du den Summand für \(k=0\) ab:$$\phantom{\sum\limits_{k=0}^n(-1)^n\binom{n}{k}}=1+\sum\limits_{k=1}^{n-1}(-1)^{k}\binom{n-1}{k}-\left(\sum\limits_{k=1}^{n-1}(-1)^{k}\binom{n-1}{k}+(-1)^0\binom{n-1}{0}\right)$$Die beiden Summen sind nun gleich und heben sich gegenseitig weg, übrig bleibt:$$\phantom{\sum\limits_{k=0}^n(-1)^n\binom{n}{k}}=1-(-1)^0\binom{n-1}{0}=1-1=0$$

Comments

Ah ja, so macht das Sinn. Vielen Dank für die Antwort!

---

Tschakabumba, du erklärst super:

Kannst du mir bei deiser Frage helfen?

(a) Bestimmen Sie begründet die Anzahl der Permutationen von [6] mit höchstens drei Fixpunkten.

(b) Bestimmen Sie begründet die Anzahl der 9-Derangements von 9], so dass sich jede gerade Zahl an einer geraden Position befindet.

Answer 2

Ja, das macht Sinn.

Cleverer finde ich allerdings, 0^n in der Form (-1+1)^n mit dem binomischen Satz darzustellen.

Comments

So geht das natürlich um einiges einfacher :) Danke für die Antwort!