Beweis: Summe 2^(n-k)*(n+k über k) = 4^n

21.04.2012, 12:32

Shizorano

Beweis: Summe 2^(n-k)*(n+k über k) = 4^n

Meine Frage:
Hallo zusammen,

meine Aufagbe ist es $\begin{eqnarray*} \sum\limits_{k=0}^n 2^{n-k}\begin{pmatrix} n+k \\ k \end{pmatrix} = 4^n \end{eqnarray*}$ via vollständiger Induktion zu beweisen!

Meine Ideen:
Also der Induktionsanfang mit n=0 stimmt ja.
Dann hab ich wie die vollständige Induktion verlangt für n n+1 ingesetzt:
$\begin{eqnarray*} \sum\limits_{k=0}^{n+1} 2^{(n+1)-k}\begin{pmatrix} (n+1)+k \\ k \end{pmatrix}= \sum\limits_{k=1}^{n+2} 2^{n-k}\begin{pmatrix} n+k \\ k \end{pmatrix} <br /> = 4^n - 1 + 2^{n-(n+1)}\begin{pmatrix} n+(n+1) \\ (n+1) \end{pmatrix} + 2^{n-(n+2)}\begin{pmatrix} n+(n+2) \\ (n+2) \end{pmatrix} <br /> = 4^n - 1 + 2^{-1}\begin{pmatrix} 2n+1 \\ n+1 \end{pmatrix} + 2^{-2}\begin{pmatrix} 2n+2 \\ n+2 \end{pmatrix} <br /> \end{eqnarray*}$

Um die einzelnen Schritte nach dem einsetzen von n+1 kurz zu erläutern:
1. Eine Indexverschiebung, damit wieder aus n+1 in der Summenformel n wird.
2. Dann habe ich n+2 und n+1 aus der Summe rausgeholt und nach Induktionsvorraussetzung den Rest durch $\begin{eqnarray*} 4^n -1 \end{eqnarray*}$ ersetzt.

Naja... dann komm ich nicht weiter! Habe schon an Binomische Hilfssätze gedacht, aber irgendwie kriege ich die nicht an-/eingesetzt.

Danke schonmal für die Hilfe
MFG
Shizorano

22.04.2012, 13:30

Shizorano

Auf diesen Beitrag antworten »

RE: Beweis: Summe 2^(n-k)*(n+k über k) = 4^n
Weiß denn wirklich keiner Rat?!
Oder ist der Thread einfach nur zu weit nach hinten gerutscht?!

23.04.2012, 10:13

klarsoweit

Auf diesen Beitrag antworten »

RE: Beweis: Summe 2^(n-k)*(n+k über k) = 4^n

Zitat:

Original von Shizorano
Dann hab ich wie die vollständige Induktion verlangt für n n+1 ingesetzt:
$\begin{eqnarray*} \sum\limits_{k=0}^{n+1} 2^{(n+1)-k}\begin{pmatrix} (n+1)+k \\ k \end{pmatrix}= \sum\limits_{k=1}^{n+2} 2^{n-k}\begin{pmatrix} n+k \\ k \end{pmatrix} \end{eqnarray*}$

Hier ist deine Indexverschiebung in die Hose gegangen. Wenn du die Grenzen des Laufindex k um 1 erhöhst, mußt du jedes k in der Summe durch "k-1" ersetzen.

23.04.2012, 11:49

Freund Nachtigall

Auf diesen Beitrag antworten »

RE: Beweis: Summe 2^(n-k)*(n+k über k) = 4^n
Wieso geht man überhaupt den Weg über n + 2?

Ich hätte die Summe von k = 0 bis n + 1 aufgespalten in Summe von k = 0 bis n + letztes Glied.

$\begin{eqnarray*} \sum\limits_{k=0}^{n+1} 2^{(n+1)-k}\begin{pmatrix} (n+1)+k \\ k \end{pmatrix}= \sum\limits_{k=0}^{n} 2^{n-k}\begin{pmatrix} n+k \\ k \end{pmatrix} + 2^{(n+1)-(k-1)} \begin{pmatrix} (n+1)+(k-1) \\ (k-1) \end{pmatrix} \end{eqnarray*}$

Ist dieser Weg falsch? Wenn ja, wieso? Ich finde Beispiele die Kombinatorik und vollständige Induktion miteinander verknüpfen irgendwie ziemlich schwer.

23.04.2012, 11:55

klarsoweit

Auf diesen Beitrag antworten »

RE: Beweis: Summe 2^(n-k)*(n+k über k) = 4^n

Zitat:

Original von Freund Nachtigall
Wieso geht man überhaupt den Weg über n + 2?

Das mußt du Shizorano fragen. Der Weg scheint jedenfalls nicht erfolgversprechend.

Zitat:

Original von Freund Nachtigall
Ich hätte die Summe von k = 0 bis n + 1 aufgespalten in Summe von k = 0 bis n + letztes Glied.

Dann müßte die Umformung so lauten:

$\begin{eqnarray*} \sum\limits_{k=0}^{n+1} 2^{(n+1)-k}\begin{pmatrix} (n+1)+k \\ k \end{pmatrix} = \sum\limits_{k=0}^{n} 2^{n+1-k}\begin{pmatrix} n+1+k \\ k \end{pmatrix} + 2^{(n+1)-(n+1)} \begin{pmatrix} (n+1)+(n+1) \\ (n+1) \end{pmatrix} \end{eqnarray*}$

23.04.2012, 12:53

Freund Nachtigall

Auf diesen Beitrag antworten »

RE: Beweis: Summe 2^(n-k)*(n+k über k) = 4^n
Danke vielmals!

Abgesehen davon, dass ich vergessen habe die k's durch n's zu ersetzen (danke dafür) ist mir nicht ganz klar wieso du auf:

$\begin{eqnarray*} \sum\limits_{k=0}^{n} 2^{n+1-k}\begin{pmatrix} n+1+k \\ k \end{pmatrix} \end{eqnarray*}$

kommst.

Der Rest (davor und dahinter) ist mir klar (Wie gesagt, ich hab vergessen die k's durch n's zu ersetzen.)

$\begin{eqnarray*} \sum\limits_{i=0}^{n+1} ... = \sum \limits_{i=0}^(n) + letztes Glied \end{eqnarray*}$

Wieso werden bei dir also schon die n's durch n+1 ersetzt?

Irgendwie steh ich jetzt grade gewaltig am Schlauch und verheddere mich. Wahrscheinlich ghörts eh so... ich sollt man Pause machen.

EDIT: Komplettzitat entfernt (klarsoweit)

23.04.2012, 13:04

klarsoweit

Auf diesen Beitrag antworten »

RE: Beweis: Summe 2^(n-k)*(n+k über k) = 4^n

Zitat:

Original von Freund Nachtigall
$\begin{eqnarray*} \sum\limits_{i=0}^{n+1} ... = \sum \limits_{i=0}^(n) + letztes Glied \end{eqnarray*}$

Wieso werden bei dir also schon die n's durch n+1 ersetzt?

Die Frage ist doch eher umgekehrt: warum werden bei dir durch das Rausziehen des letzten Summanden aus allen "n+1" ein n gemacht?

Wenn ich aus $\begin{eqnarray*} \sum\limits_{k=0}^{n+1} 2^{(n+1)-k} \binom{(n+1)+k}{k} \end{eqnarray*}$ den letzten Summanden rausziehe, ändert sich doch nicht die Darstellung des Summenterms.

23.04.2012, 13:07

Freund Nachtigall

Auf diesen Beitrag antworten »

RE: Beweis: Summe 2^(n-k)*(n+k über k) = 4^n

Zitat:

Original von klarsoweit

Zitat:

Original von Freund Nachtigall
$\begin{eqnarray*} \sum\limits_{i=0}^{n+1} ... = \sum \limits_{i=0}^(n) + letztes Glied \end{eqnarray*}$

Wieso werden bei dir also schon die n's durch n+1 ersetzt?

Stimmt natürlich und macht jetzt wieder absolut Sinn... all maths and no play make me a dull boy unglücklich

Vielen lieben Dank auf jeden Fall! smile

23.04.2012, 13:16

Freund Nachtigall

Auf diesen Beitrag antworten »

RE: Beweis: Summe 2^(n-k)*(n+k über k) = 4^n
Nein, Moment, macht grade doch keinen Sinn traurig

Ich nehm alle Glieder bis n (!) und addiere dann das letzte Glied mit n+1 dazu.

Wenn ich es so nehme kann ich ja nichts mehr einsetzen.

Irgendwie muss ich ja die rechte Seite des Induktionsanfang einsetzen können, aber das geht hier nirgends, wenn ich überall n+1 einsetze unglücklich

So geh ich doch sonst bei ner vollständigen Induktion auch vor.

Induktionsanfang beweisen, damit stimmt die Voraussetzung.
Behauptung aufstellen: n -> n+1

Summe von n+1 = Summe von n + letztes Glied.

Summe von n = mit Anfang bewiesen, ergo rechte Seite einsetzen.

Bei uns sollte das dann so aussehen:

Summe von n+1 = 4^n + letztes Glied.

Aber genau das 4^n krieg ich da nirgends rein, wenn überall nur mehr n+1 sind unglücklich

23.04.2012, 13:35

klarsoweit

Auf diesen Beitrag antworten »

RE: Beweis: Summe 2^(n-k)*(n+k über k) = 4^n

Zitat:

Original von Freund Nachtigall
Wenn ich es so nehme kann ich ja nichts mehr einsetzen.

Irgendwie muss ich ja die rechte Seite des Induktionsanfang einsetzen können, aber das geht hier nirgends, wenn ich überall n+1 einsetze unglücklich

Das macht den Beweis auch etwas anspruchsvoll. Augenzwinkern

Zitat:

Original von Freund Nachtigall
Summe von n+1 = Summe von n + letztes Glied.

Summe von n = mit Anfang bewiesen, ergo rechte Seite einsetzen.

Da bist du etwas im Irrtum. Für n lautet die Aussage:

$\begin{eqnarray*} \sum\limits_{k=0}^n 2^{n-k} \binom{n+k}{k} = 4^n \end{eqnarray*}$

Und für n+1: $\begin{eqnarray*} \sum\limits_{k=0}^{n+1} 2^{n+1-k} \binom{n+1+k}{k} = 4^{n+1} \end{eqnarray*}$

Und wenn du da den letzten Summanden rausziehst, steht eben nicht die Summe $\begin{eqnarray*} \sum\limits_{k=0}^n 2^{n-k} \binom{n+k}{k} \end{eqnarray*}$ da. Mach dir das mal an den Beispielen n=1 und n=2 klar.

23.04.2012, 13:57

HAL 9000

Auf diesen Beitrag antworten »

@Freund Nachtigall

Du kannst es drehen und wenden wie du willst, ob mit oder ohne Indexverschiebung: Mit der Abtrennung des letzten Summanden allein ist es nicht getan - schließlich taucht explizit $\begin{eqnarray*} n \end{eqnarray*}$ in jedem Summanden auf, was die unmittelbare Anwendung der Induktionsvoraussetzung verhindert.

Also muss man ran an die Zerlegung dieses Summanden, und da bietet sich (wie so oft) die "Pascal-Dreieck-Rekursion" $\begin{eqnarray*} \binom{m+1}{k} = \binom{m}{k-1}+\binom{m}{k} \end{eqnarray*}$ an, gültig für alle $\begin{eqnarray*} k\geq 1 \end{eqnarray*}$ . Im Induktionsschritt $\begin{eqnarray*} n\to n+1 \end{eqnarray*}$ wendet man dies für $\begin{eqnarray*} m=n+k \end{eqnarray*}$ an:

$\begin{eqnarray*} \sum\limits_{k=0}^{n+1} 2^{n+1-k} \binom{n+1+k}{k} = 2^{n+1} + \sum\limits_{k=1}^{n+1} 2^{n+1-k} \binom{n+k}{k-1} + \sum\limits_{k=1}^{n+1} 2^{n+1-k} \binom{n+k}{k} = \ldots \end{eqnarray*}$

Das ist noch nicht alles - Indexverschiebung in der ersten Teilsumme und ein wenig Nachdenken, auch über die "Summenränder", ist schon noch nötig. Augenzwinkern

23.04.2012, 14:27

Freund Nachtigall

Auf diesen Beitrag antworten »

Ohje, ich glaub man merkt, dass ich kein Mathematiker bin. Ich steig mal aus für heute, mal sehen ob es morgen klarer wird.

Danke für eure Geduld!

25.04.2012, 10:04

Tanzender Barde

Auf diesen Beitrag antworten »

Guten Tag!

Nachdem ich das Beispiel hier entdeckt habe und meine Algebra-Prüfung für Informatiker bald ansteht hab ich mich des Beispiels angenommen und seitdem träume ich schlecht traurig

Zwar glaube und hoffe ich nicht, dass wir ein solches Beispiel bekommen, doch einerseits liegt es im Bereich des Möglichen, andererseits hat mich der Ehrgeiz gepackt.

Crosspostings sind sicher nicht erwünscht, es sei aber gesagt, dass ich dieses Beispiel zuerst im informatik-forum(.at) gepostet habe. Jetzt würde ich gerne wissen ob meine Ansätze (wobei ich auch diese nur mit der Hilfe von Kollegen soweit gebracht habe) überhaupt korrekt sind, oder ob ich irgendeine wichtige Regel missachtet oder zu kompliziert gedacht habe etc. (es gibt nämlich auch noch andere Ansätze mit dem binomischen Lehrsatz...)

Induktionsschritt:

$\begin{eqnarray*} \sum\limits_{k=0}^{n+1} 2^{(n+1)-k}\begin{pmatrix} (n+1)+k \\ k \end{pmatrix} = \sum\limits_{k=0}^{n} 2^{n+1-k}\begin{pmatrix} n+1+k \\ k \end{pmatrix} + 2^{(n+1)-(n+1)} \begin{pmatrix} (n+1)+(n+1) \\ (n+1) \end{pmatrix} \end{eqnarray*}$

$\begin{eqnarray*} \sum\limits_{k=0}^{n+1} 2^{(n+1)-k}\begin{pmatrix} (n+1)+k \\ k \end{pmatrix} = \sum\limits_{k=0}^{n} 2 * 2^{n-k}\frac{(n+1+k)!}{k!(n+1+k-k)!} + 1 *\begin{pmatrix}(2n+2) \\ n+1\end{pmatrix} \end{eqnarray*}$
$\begin{eqnarray*} \sum\limits_{k=0}^{n+1} 2^{(n+1)-k}\begin{pmatrix} (n+1)+k \\ k \end{pmatrix} = \sum\limits_{k=0}^{n} 2 * 2^{n-k}\frac{(n+1+k)!}{k!n!(n+1)} + \begin{pmatrix}(2n+2) \\ n+1\end{pmatrix} \end{eqnarray*}$
$\begin{eqnarray*} \sum\limits_{k=0}^{n+1} 2^{(n+1)-k}\begin{pmatrix} (n+1)+k \\ k \end{pmatrix} = \sum\limits_{k=0}^{n} 2 * 2^{n-k}\frac{(n+k)! (n+1+k)}{k!n!} * \frac{1}{(n+1)} + \begin{pmatrix}(2n+2) \\ n+1\end{pmatrix} \end{eqnarray*}$
$\begin{eqnarray*} \sum\limits_{k=0}^{n+1} 2^{(n+1)-k}\begin{pmatrix} (n+1)+k \\ k \end{pmatrix} = \sum\limits_{k=0}^{n} 2 * 2^{n-k}\frac{(n+k)!}{k!n!} * \frac{n+1+k}{(n+1)} + \begin{pmatrix}(2n+2) \\ n+1\end{pmatrix} \end{eqnarray*}$

So, jetzt kommt's $\begin{eqnarray*} \frac{(n+k)!}{k!n!} = \begin{pmatrix}n+k \\k\end{pmatrix} \end{eqnarray*}$

$\begin{eqnarray*} \sum\limits_{k=0}^{n+1} 2^{(n+1)-k}\begin{pmatrix} (n+1)+k \\ k \end{pmatrix} = \sum\limits_{k=0}^{n} 2 * 2^{n-k}\begin{pmatrix}n+k \\k\end{pmatrix} * \frac{n+1+k}{(n+1)} + \begin{pmatrix}(2n+2) \\ n+1\end{pmatrix} \end{eqnarray*}$

Missachte ich hier irgendeine Regel oder geht das so?

Wenn nicht, dann könnt ich jetzt nämlich 4n einsetzen und käme auf:

$\begin{eqnarray*} \sum\limits_{k=0}^{n+1} 2^{(n+1)-k}\begin{pmatrix} (n+1)+k \\ k \end{pmatrix} = 2* 4^n * \frac{n+1+k}{(n+1)} + \begin{pmatrix}(2n+2) \\ n+1\end{pmatrix} \end{eqnarray*}$

Liebe Grüße
Tanzender Barde

25.04.2012, 10:37

HAL 9000

Auf diesen Beitrag antworten »

Und es stört dich nicht, dass du den Faktor $\begin{eqnarray*} \frac{n+1+k}{(n+1)} \end{eqnarray*}$ gar nicht aus der Summe herausziehen kannst, weil er nämlich vom Summenindex $\begin{eqnarray*} k \end{eqnarray*}$ abhängt? unglücklich

25.04.2012, 11:10

Tanzender Barde

Auf diesen Beitrag antworten »

Zitat:

Original von HAL 9000
Und es stört dich nicht, dass du den Faktor $\begin{eqnarray*} \frac{n+1+k}{(n+1)} \end{eqnarray*}$ gar nicht aus der Summe herausziehen kannst, weil er nämlich vom Summenindex $\begin{eqnarray*} k \end{eqnarray*}$ abhängt? unglücklich

Nein?! Für mich sah das wie ein stinknormales Produkt aus. *seufz* Mathematik und ich werden wohl nie wirkliche Freunde werden fürchte ich.

26.04.2012, 14:56

HAL 9000

Auf diesen Beitrag antworten »

Du formst doch statt des richtigen

$\begin{eqnarray*} \sum_{k=1}^n k^2 = \frac{n(n+1)(2n+1)}{6} \end{eqnarray*}$

auch nicht um

$\begin{eqnarray*} \sum_{k=1}^n k^2 = \sum_{k=1}^n k\cdot k \stackrel{???}{=} k\cdot\sum_{k=1}^n k = k\cdot \frac{n(n+1)}{2} \end{eqnarray*}$ ,

oder etwa doch? Im Prinzip ist letzteres aber genau das, was du da gemacht hast. Überhaupt stellt sich ja dann die Frage, was dieses $\begin{eqnarray*} k \end{eqnarray*}$ überhaupt sein soll, denn außerhalb des Summenrahmens hat dieses Symbol hier nicht die geringste Bedeutung - es schwebt also frei in der Luft, völlig losgelöst... geschockt

26.04.2012, 15:23

klarsoweit

Auf diesen Beitrag antworten »

@HAL9000: ich glaube, Tanzender Barde hat seinen Fehler durchaus eingesehen.

26.04.2012, 16:14

HAL 9000

Auf diesen Beitrag antworten »

Ein verwundertes "Nein?!" ist für mich allemal Grund, die Sache zu verdeutlichen. Und ich habe da mehr Resignation als Einsicht gesehen.

26.04.2012, 16:55

Tanzender Barde

Auf diesen Beitrag antworten »

Zitat:

Original von HAL 9000
Ein verwundertes "Nein?!" ist für mich allemal Grund, die Sache zu verdeutlichen. Und ich habe da mehr Resignation als Einsicht gesehen.

Du hast beides gesehen Augenzwinkern

Ich schaff das Beispiel nicht und wenn sowas zur Klausur kommt lass ich es aus und probier gegen Ende mein Glück.

Was soll ich denn auch anderes machen? Mir liegen Teilgebiete der Mathematik einigermaßen, ich finde vieles sehr interessant, aber leider war das nicht immer so. Den Stoff auf der Uni fand und finde ich eigentlich sehr interessant, aber von Heut auf Morgen wird man nicht zum Mathe-Genius, leider.

Bisher hat auch niemand sonst den ich kenne das Beispiel lösen können. Es ist um ne Hausecke schwerer als es bisher zu unseren Klausuren kam (Wie gesagt, kein Mathematiker) und ich hab meinen Ergeiz mittlerweile zum Schweigen gebracht Augenzwinkern

Liebe Grüße
Tanzender Barde

26.04.2012, 17:29

Valdas Ivanauskas

Auf diesen Beitrag antworten »

Also so fürchterlich schwierig ist die Geschichte eigentlich nicht.
Genaugenommen geht das sogar ziemlich geradeaus durch und HAL 9000 hat den Fahrplan samt Ansatz ja schon dargelegt.

Also: Nich am Weinen fangen sondern einfach mal versuchen!

26.04.2012, 17:41

Tanzender Barde

Auf diesen Beitrag antworten »

Zitat:

Original von Valdas Ivanauskas
Also so fürchterlich schwierig ist die Geschichte eigentlich nicht.
Genaugenommen geht das sogar ziemlich geradeaus durch und HAL 9000 hat den Fahrplan samt Ansatz ja schon dargelegt.

Also: Nich am Weinen fangen sondern einfach mal versuchen!

Hab's mehr als einmal probiert, so schnell geb ich nicht auf. Da es aber noch reichlich andere Stoffgebiete zur Klausur gibt hab ich einfach nicht die Zeit mich allzulange damit aufzuhalten Augenzwinkern

Hab das Beispiel hier entdeckt und fand es spannend. Meinen Fehler hab ich eingesehen, auf ne Lösung komm ich dennoch nicht.

26.04.2012, 18:37

HAL 9000

Auf diesen Beitrag antworten »

Das ist bedauerlich, denn wie Valdas Ivanauskas schon sagte, habe ich doch einen möglichen Fahrplan für den Induktionsschritt $\begin{eqnarray*} n\to n+1 \end{eqnarray*}$ oben dargelegt:

Zitat:

Original von HAL 9000
Indexverschiebung in der ersten Teilsumme und ein wenig Nachdenken, auch über die "Summenränder", ist schon noch nötig.

Es folgen (zu viele) nächste Schritte, beginnend mit der Indexverschiebung $\begin{eqnarray*} j=k-1 \end{eqnarray*}$ in der ersten Teilsumme, zugleich Veränderungen in der zweiten Teilsumme (Hinzunahme des Gliedes k=0, Wegnahme von k=n+1):

Zitat:

Original von HAL 9000
$\begin{eqnarray*} \sum\limits_{k=0}^{n+1} 2^{n+1-k} \binom{n+1+k}{k} = {\color{red}2^{n+1}} + \sum\limits_{k=1}^{n+1} 2^{n+1-k} \binom{n+k}{k-1} + \sum\limits_{k=1}^{n+1} 2^{n+1-k} \binom{n+k}{k} = \ldots \end{eqnarray*}$

$\begin{eqnarray*} \ldots = \sum\limits_{k=1}^{n+1} 2^{n+1-k} \binom{n+k}{k-1} + \sum\limits_{{\color{red}k=0}}^{{\color{red}n}} 2^{n+1-k} \binom{n+k}{k} + {\color{red}\binom{2n+1}{n+1}} = \sum\limits_{j=0}^{n} 2^{n-j} \binom{n+1+j}{j} + 2\cdot {\color{blue}\sum\limits_{k=0}^{n} 2^{n-k} \binom{n+k}{k}} + \binom{2n+1}{n+1} \end{eqnarray*}$

Nun sollte erkennbar sein, dass man die Induktionsvoraussetzung einsetzen kann. Zugleich ergänzen wir mal noch die erste Summe (nach Umbenennung von j wieder in k) um das Glied für k=n+1:

$\begin{eqnarray*} \definecolor{dgreen}{rgb}{0,0.4,0} {\color{dgreen} \sum\limits_{k=0}^{n+1} 2^{n+1-k} \binom{n+1+k}{k}} = \frac{1}{2} {\color{dgreen} \sum\limits_{k=0}^{n+1} 2^{n+1-k} \binom{n+1+k}{k}} + 2\cdot 4^n + \binom{2n+1}{n+1} - \frac{1}{2}\binom{2n+2}{n+1} \end{eqnarray*}$

Die grünen Anteile auf die linke Seite gebracht, das ganze mit 2 multipliziert, steht schließlich noch da

$\begin{eqnarray*} \sum\limits_{k=0}^{n+1} 2^{n+1-k} \binom{n+1+k}{k} = 4^{n+1} + 2\binom{2n+1}{n+1} - \binom{2n+2}{n+1} \end{eqnarray*}$ .

Was ist jetzt wohl noch zu tun? smile

Neue Frage »

Antworten »

Beweis: Summe 2^(n-k)*(n+k über k) = 4^n

Verwandte Themen