Vollständige: Zeigen Summe der Binomialkoeffizienten ist 2^n. Alternierende Summe ist 0.

Question

Ich komme leider bei folgender Induktion nicht weiter. Ich bin mir so unsicher wie eine solche Induktion erfolgt. Vor allem verstehe ich einfach diese Indexverschiebung nicht. Ich habe echt schon viel recherchiert und nachgelesen aber ich verstehe es trotzdem nicht.

Folgendes Beispiel:

ICH HABE FOLGENDES:

Induktionsanfang:

n = 0

Σ (von k=0 bis 0) (⁰₀) = 2⁰= 1       und das STIMMT auf beiden Seiten.

Induktionsbehauptung:

∃n∈ℕ, n≥0 : ∑_kⁿ₌₀  (n über k) = 2ⁿ

Induktionsschritt: n → n+1

zz. ∑ⁿ⁺¹_k=0 (ⁿ⁺¹_k) = 2ⁿ⁺¹

2ⁿ⁺¹ = 2*2ⁿ = 2 * ∑ⁿ_k=0(ⁿ_k) = ∑ⁿ_k=0(ⁿ_k)*2 

und weiter weiß ich leider nicht mehr kann mir wer dabei helfen?

-----

Aus Duplikat:

 1)

$$ { 2 }^{ n }=(\begin{matrix} n \\ 0 \end{matrix})+(\begin{matrix} n \\ 1 \end{matrix})+(\begin{matrix} n \\ 2 \end{matrix})+...+(\begin{matrix} n \\ n-1 \end{matrix})+(\begin{matrix} n \\ n \end{matrix}), $$

2)
$$ 0=(\begin{matrix} n \\ 0 \end{matrix})-(\begin{matrix} n \\ 1 \end{matrix})+(\begin{matrix} n \\ 2 \end{matrix})-...+{ (-1) }^{ n-1 }(\begin{matrix} n \\ n-1 \end{matrix})+{ (-1) }^{ n }(\begin{matrix} n \\ n \end{matrix}). $$

Answer 1

normalerweise bespricht oder behandelt man vor diesem Beweis die Rekursionsformel für den Binomialkoeffizienten:

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

Dies ist auch mein Hinweis an dich für den IS.

Gruß

Comments

Ach du meine Güte ich kenn mich da nicht aus.

Aber der Induktionsanfang passt noch oder?

Ich dachte ich darf die Rekursionsformel nur bei k >0 anwenden.

Muss ich sozusagen für den Induktionsschritt die rechte Formel verwenden?

Ich bin echt am verzweifeln. Ich kenne mich gar nicht mehr aus.

Kannst du mir bitte helfen?

---

Der Induktionsanfang passt.

Anscheinend kennst du ja die Rekursionsformel, dann sollte doch klar sein warum:

$$ \sum_{k=0}^{n+1} \binom{n+1}{k} = \sum_{k=0}^n \binom{n}{k} + \sum_{k=1}^{n+1} \binom{n}{k-1} = ... $$

ab da kannst du bestimmt selber weiter machen oder?

---

So das hab ich gefunden. Aber ich verstehe nicht wirklich warum ich am Anfang z.B. n+1 über 0 herausheben muss. Liegt das daran, dass ich dann mit k=1 starten darf?

Nächste Frage: Wie komme ich von der dritten auf die vierte Zeile? Der Einser auf der l.S. kommt ja weg, muss ich deshalb n-1 machen? und das (-1) bei n über (k-1) wird einfach unter der Summe vom k abgezogen?

Ich erkenne auch nicht wie man auf die 2 letzten Zeilen kommt.

Ich bin echt megaverzweifelt. Mir gehen da anscheinend so viele Verknüpfungen ab.

Könntest du so lieb sein und mir das erklären?

---

Schade, dachte du willst dich selber dran probieren. Je nachdem wie man den Binomialkoeffizient definiert hat macht man diese Heraushebung  nach dem 1. Gleichheitszeichen genau aus dem Grund den du genannt hast.

Bei der 4.  und 5. Zeile wurde einfach verwendet, dass \( \binom{n}{n} = \binom{n}{0} = 1 \), die 1 also in die jeweilige Summe eingegliedert wurde. Außerdem wurde bei der rechten Summe ein Indexshift verwendet, damit die Summe nicht bei \(k=1\) sonder bei \(k=0\) anfängt und aus \(\binom{n}{k-1}\) zu \(\binom{n}{k} \) wird. Natürlich geht die Summe dann nicht mehr bis \( k = n \) sondern nun bis \(k=n-1\).

Du musst dich vertrauter machen mit den Themen:

Binomialkoeffizient, Summenzeichen und Indexshift

Das sind keine Grundlagen aus der Schulzeit also keine Sorge ;).

---

okay vielen dank für deine Geduld.

Das mit der 1 warum die in Zeile 4 auf einmal wegfällt verstehe ich trotzdem nicht. Ich weiß schon, dass über 0 diese 1 ist aber warum kann ich die wirklich ganz weglassen?

also ich weiß auch warum  man auf die letzten 2 Zeilen kommt aber ich sehe nicht, dass unsere erste LANGE Lösung wirklich dem 2^{n+1} entspricht.

Oder kann man das gar nicht wirklich sehen? So als Probe?

Den Shift verstehe ich jetzt, aber wie gesagt der 1er ist für mich noch mystisch und eben wie ich sehen kann, dass der lange errechnete Ausdruck äquivalent zu 2^{n+1} ist.

---

Ich seh grade, dass es ein Fehler in der Lösung gibt, die 1 verschwindet nicht in der 4. Zeile sie wird mit in die Summe integriert, aber dafür müsste in der 4. Zeile in der linken Summe \(k=0\) dafür dann stehen und nicht \(k=1\).

$$ 1+ \sum_{k=1}^n \binom{n}{k} = \binom{n}{0} + \sum_{k=1}^n \binom{n}{k} = \sum_{k=0}^n \binom{n}{k} $$

Das am Ende \(2^{n+1} \) rauskommt müsste man eigentlich sofort sehen, wenn man jeden einzelnen Schritt verstanden hat, deswegen verstehe ich deine Frage nicht.

---

ich meinte die 4. Zeile ist ja abgeschlossen oder?

und dann nehme ich von der Angabe die rechte Seite zur Hand und bearbeite diese oder? dann brauche ich nur für die eine n+1 einsetzen (schnell gesagt) und dass ist dasselbe wie eben 2^n und die Anfangssumme gemeinsam.

Sehe ich nun das Endergebnis mit 2^{n+1} und die Vierte Zeile dann müssen diese ja gleich sein und das kann ich i.wie nicht sehen.

Aber vl.  bin ich einfach nur zu blöd dafür.

---

Ich versteh leider überhaupt nicht was du meinst.

Die Gleichung wird solange umgeformt bis man bei \(2^{n+1} \) ankommt, man hört nicht einfach bei der 4. Zeile auf und rechnet \(2^{n+1} \) so lange rückwärts bis man darauf kommt (aber ja da überall zwischen den Schritten Gleichheitszeichen stehen, ist die 4. Zeile gleich \(2^{n+1} \), aber da man das nicht sofort sieht gibt es ja noch n Haufen Zwischenschritte oder?)

Welchen Schritt verstehst du nicht?

---

4. auf 5. und 5. auf 6. .

Wo kommt auf einmal das 2^n her und wo ist die rechte Seite der Addition aus der 3. Zeile?

Ich dachte er rechnete mit dem Ergebnis der Angabe weiter, aber er hat die 4. Zeile auf die 5. umgeformt? sry da weiß ich nicht wie das geht. Ich glaube da steht mir heute was im Kopf dagegen.

Wenn du noch Geduld hast würde ich mich sehr darüber freuen, dass zu erfahren.

Vielen lieben Dank

---

Hier wurde einfach die Induktionsvoraussetzung verwendet nach der ja gilt, dass \( \sum \limits_{k=0}^n \binom{n}{k} = 2^n\). Bei der rechten Summe wird das +1 als \( \binom{n}{n} \) in die Summe integiert (weswegen sie dann auch bis n läuft und nicht mehr nur bis n-1). Das habe ich weiter oben schon geschrieben gehabt.

---

ajjaaaaaaaaa verstehe mich hat dann nur verwirrt, dass eben immer noch der linke Summand dasteht mimt unterer Grenze k = 1 .

D.h. mein linker Summand wird laut innduktionsvoraussetzung zu 2^n und der rechte wird nur umgeformt, damit die obere Grenze wieder n wird.und dann sieht man, dass auch der rechte summand zu 2^n umgeformt werden kann. Und dann folgt aus 2^n und 2^n usw.........

Stimmt das so?

Du bist ein Engel

---

Ja das stimmt so weit :). Haha danke.