Induktionsaufgabe falscher Ansatz? Alternierende Summe von Binomialkoeffizienten.

Question

ⁿ∑_k=0   (-1)^k * ( n über k)   =  0

IS:         

ⁿ⁺¹∑_k=0   (-1)^k * ( n+1 über k)   =  0

=  ⁿ∑_k=0   (-1)^k * ( n+1 über k)    +   (-1)ⁿ⁺¹ * (n+1   über  n+1)  =  0

= ⁿ∑_k=0   (-1)^k * ( n über k   +   n  über k-1)     +    (-1)ⁿ⁺¹ * 1  =  0

= ⁿ∑_k=0   (-1)^k * ( n über k)    +     ⁿ∑_k=0   (-1)^k * (n  über k-1)   +  (-1)ⁿ⁺¹ * 1= 0

=  0  + ⁿ∑_k=0   (-1)^k * (n  über k-1)   +   (-1)ⁿ⁺¹

=  ⁿ∑_k=1   (-1)^k * (n  über k-1)   +  (-1)ⁿ⁺¹

 

wie geht  es nun weiter ?

Comments

Betrachte mal: https://www.mathelounge.de/60643/binomialkoeffizienten-beweise-summe-von-n-tief-k-1-k-gibt-0

Die Antwort dort ist kein Induktionsbeweis. Wenn du ihn verstehst, vielleicht eine Möglichkeit deinen Induktionsbeweis anders anzugehen.

---

Vom Duplikat:

Titel: Vollständige Induktion. Zeige: Die alternierende Summe von Binomialkoeffizienten gibt Null.

Stichworte: binomialkoeffizient,alternierend,summe,induktion,vollständige-induktion

Aufgabe:

habe Probleme mit einem Beweis. Hier hat mir meine Lehrerin eine Aufgabe gestellt, in der ich folgende Gleichung mit der vollständigen Induktion beweisen soll. Ich komme beim Induktionsschritt nicht mehr weiter.

..

---

Vgl. https://www.mathelounge.de/665002/vollstandiger-induktion-alternierende-binomialkoeffizienten

Answer 1

Hier nochmal dein Induktionsschritt in formal korrigierter Form (am Anfang jeder Zeile müssen Äquivalenzzeichen stehen und jede Zeile muss eine Gleichung sein, auf deren rechter Seite die 0 steht.)

ⁿ⁺¹∑_k=0   (-1)^k * ( n+1 über k)   =  0

<=>  ⁿ∑_k=0   (-1)^k * ( n+1 über k)    +   (-1)ⁿ⁺¹ * (n+1   über  n+1)  =  0

<=> ⁿ∑_k=0   (-1)^k * ( n über k   +   n  über k-1)     +    (-1)ⁿ⁺¹ * 1  =  0

<=> ⁿ∑_k=0   (-1)^k * ( n über k)    +     ⁿ∑_k=0   (-1)^k * (n  über k-1)   +  (-1)ⁿ⁺¹ * 1 = 0

<=>  0  + ⁿ∑_k=0   (-1)^k * (n  über k-1)   +   (-1)ⁿ⁺¹ = 0

<=>  ⁿ∑_k=1   (-1)^k * (n  über k-1)   +  (-1)ⁿ⁺¹ = 0

--> ab hier mein Vorschlag für das weitere Vorgehen:

Zunächst Indextransformation:

<=>  ^n-1∑_k=0   (-1)^k+1 * (n  über k)   +  (-1)ⁿ⁺¹ = 0

Nun die Summe bis k = n gehen lassen und dafür das n-te Element wieder subtrahieren: 

<=>  ⁿ∑_k=0   (-1)^k+1 * (n  über k)   - (-1)ⁿ⁺¹ * (n über n) +  (-1)ⁿ⁺¹ = 0

Es ist (n über n) = 1, also:

<=>  ⁿ∑_k=0   (-1)^k+1 * (n  über k)   - (-1)ⁿ⁺¹ +  (-1)ⁿ⁺¹ = 0

Die beiden letzten Summanden heben sich auf:

<=>  ⁿ∑_k=0   (-1)^k+1 * (n  über k) = 0

Es ist (-1) ^k+1= (-1)*(-1)^k , also:

<=>  ⁿ∑_k=0   (-1) (-1)^k * (n  über k) = 0

Den Faktor (-1) vor die Summe ziehen:

<=> - ⁿ∑_k=0   (-1)^k * (n  über k) = 0

Die Summe hat gemäß Induktionsvoraussetzung den Wert 0, also:

<=> - 0 = 0

Das ist eine immer wahre Aussage.

Comments

darf ich fragen wie man von 

<=>  0  + ⁿ∑_k=0   (-1)^k * (n  über k-1)   +   (-1)ⁿ⁺¹ = 0

 auf 

<=>  ⁿ∑_k=1   (-1)^k * (n  über k-1)   +  (-1)ⁿ⁺¹ = 0 

kommt?

das wär sehr lieb . Danke

---

@JaMMa: Man lässt links einfach den Summanden 0 weg.

Ist das das, was du wissen wolltest?

Die erste 0 links kommt aus der Induktionsvoraussetzung.

Answer 2

Du hast das ja schon recht weit. Es muss übrigens = statt <=> heißen.

Das mit dem p-1 ist auch nicht so ganz echt, denn für p=0 gäbe das ja eine -1 in dem

Binomialkoeffizienten.  Also wäre besser der 0-te Summand vorher rausgenommen worden.

Außerdem ist m+1 über m+1 gleich 1

Dann wäre es so:

$$= \sum \limits_{p=0}^{m}((-1)^p \begin{pmatrix} m+1\\p \end{pmatrix})+(-1)^{m+1}*1$$

$$= ((-1)^0 \begin{pmatrix} m+1\\0 \end{pmatrix})+\sum \limits_{p=1}^{m}((-1)^p \begin{pmatrix} m+1\\p \end{pmatrix})+(-1)^{m+1}*1$$

Der 1. Binomialkoeffizient ist auch 1 und (-1)^0 auch. Und das mit der Formel war eine gute Idee.

$$=1+\sum \limits_{p=1}^{m}((-1)^p (\begin{pmatrix} m\\p \end{pmatrix}+ \begin{pmatrix} m\\p-1 \end{pmatrix}))+(-1)^{m+1}*1$$

Und jetzt zwei Summen, wie du es hattest

$$=1+\sum \limits_{p=1}^{m}((-1)^p \begin{pmatrix} m\\p-1 \end{pmatrix})+\sum \limits_{p=1}^{m}((-1)^p \begin{pmatrix} m\\p \end{pmatrix})+(-1)^{m+1}*1$$

Jetzt kannst du die erste 1 als 0-ten Summanden in die 2. Summe stecken und den letzten Summenden als (m+1)-ten in die erste

$$=\sum \limits_{p=1}^{m+1}((-1)^p \begin{pmatrix} m\\p-1 \end{pmatrix})+\sum \limits_{p=0}^{m}((-1)^p \begin{pmatrix} m\\p \end{pmatrix})$$

Jetzt bei der ersten den Index verschieben und du hast

$$=\sum \limits_{p=0}^{m}((-1)^{p+1} \begin{pmatrix} m\\p \end{pmatrix})+\sum \limits_{p=0}^{m}((-1)^p \begin{pmatrix} m\\p \end{pmatrix})$$

Aus der 1. Summe den Faktor (-1) rausziehen gibt

$$=(-1)*\sum \limits_{p=0}^{m}((-1)^{p} \begin{pmatrix} m\\p \end{pmatrix})+\sum \limits_{p=0}^{m}((-1)^p \begin{pmatrix} m\\p \end{pmatrix})$$

und zweimal die Induktionsannahme einsetzen

= (-1)*0 + 0 = 0    Bingo!