summenformel beweisen

27.10.2007, 11:20

marci_

Auf diesen Beitrag antworten »

summenformel beweisen

hallo!

aufgabenstellung: zeigen sie, dass die folgende summenformel für alle zahlen $\begin{eqnarray*} n \in \mathbb N_0 \end{eqnarray*}$ gilt:

$\begin{eqnarray*} \sum_{k=0}^n~ \begin{pmatrix} n \\ k \end{pmatrix} =2^n \end{eqnarray*}$

hinweis: sie können dabei den binomischen lehrsatz verwenden.

=>

$\begin{eqnarray*} (a+b)^n=\sum_{k=0}^n~ \begin{pmatrix} n \\ k \end{pmatrix}a^{n-k}b^k \end{eqnarray*}$

dann setze ich a=b=1

und erhalte dann:

$\begin{eqnarray*} (1+1)^n=\sum_{k=0}^n~ \begin{pmatrix} n \\ k \end{pmatrix}=2^n \end{eqnarray*}$

reicht dieser schritt schon als beweis, oder muss ich da noch mit der vollständigen induktion ran?
unsere tutorin meinte, man könne es in einer zeile schreiben...

27.10.2007, 12:22

therisen

Auf diesen Beitrag antworten »

Das genügt vollkommen.

27.10.2007, 20:22

marci_

Auf diesen Beitrag antworten »

angenommen ich würde dies mit vollständiger induktion beweisen wollen,

dann steh ich am ende meines induktionsschrittes vorm lösen dieser gleichung:

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

wie kann ich das jetzt genau auflösen?
mir fehlt gerade der ansatz...

27.10.2007, 23:03

klarsoweit

Auf diesen Beitrag antworten »

Ich glaube, da hast du irgendwo einen Fehler gemacht.

27.10.2007, 23:16

marci_

Auf diesen Beitrag antworten »

also: angenommen ich wollte dies mit vollständiger induktion beweisen:

$\begin{eqnarray*} \sum_{k=0}^n~ \begin{pmatrix} n \\ k \end{pmatrix} =2^n \end{eqnarray*}$

es stimmt für k=0

indukstionsschritt:

$\begin{eqnarray*} \sum_{k=0}^{n+1}~ \begin{pmatrix} n \\ k \end{pmatrix}=2^{n+1} \end{eqnarray*}$

$\begin{eqnarray*} \sum_{k=0}^{n}~ \begin{pmatrix} n \\ k \end{pmatrix}+ \begin{pmatrix} n+1 \\ k \end{pmatrix}=2^{n+1} \end{eqnarray*}$

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

wo liegt hier jetzt mein fehler?

27.10.2007, 23:19

pseudo-nym

Auf diesen Beitrag antworten »

Du musst schon jedes n um eins erhöhen

$\begin{eqnarray*} \sum_{k=0}^{n+1}~ \begin{pmatrix} n+1 \\ k \end{pmatrix}=2^{n+1} \end{eqnarray*}$

Anzeige

27.10.2007, 23:20

therisen

Auf diesen Beitrag antworten »

Zitat:

Original von marci_
$\begin{eqnarray*} \sum_{k=0}^{n}~ \begin{pmatrix} n \\ k \end{pmatrix}+ \begin{pmatrix} n+1 \\ k \end{pmatrix}=2^{n+1} \end{eqnarray*}$

Außerdem darf bei dem rechten Summanden kein k mehr vorkommen.

27.10.2007, 23:52

marci_

Auf diesen Beitrag antworten »

hm, irgendwie verstehe ich das nicht!

ist dann diese aufgabe auch falsch?:

$\begin{eqnarray*} \sum_{k=0}^n~ \begin{pmatrix} m+k \\ k \end{pmatrix} =\begin{pmatrix} m+n+1 \\ n \end{pmatrix} \end{eqnarray*}$

für k=0 stimmt die aussage

induktionsschritt:

$\begin{eqnarray*} \sum_{k=0}^{n+1}~ \begin{pmatrix} m+k \\ k \end{pmatrix}= \begin{pmatrix} m+(n+1)+1 \\ (n+1) \end{pmatrix} \end{eqnarray*}$

$\begin{eqnarray*} \sum_{k=0}^{n}~ \begin{pmatrix} m+k \\ k \end{pmatrix}+\begin{pmatrix} m+(n+1) \\ (n+1) \end{pmatrix} = \begin{pmatrix} m+(n+1)+1 \\ (n+1) \end{pmatrix} \end{eqnarray*}$

$\begin{eqnarray*} \begin{pmatrix} m+n+1 \\ n \end{pmatrix} +\begin{pmatrix} m+n+1 \\ n+1 \end{pmatrix}= \begin{pmatrix} m+n+1+1 \\ n+1 \end{pmatrix} \end{eqnarray*}$

$\begin{eqnarray*} \begin{pmatrix} m+n+1+1 \\ n+1 \end{pmatrix} = \begin{pmatrix} m+n+1+1 \\ n+1 \end{pmatrix} \end{eqnarray*}$

28.10.2007, 00:00

therisen

Auf diesen Beitrag antworten »

Zitat:

Original von marci_
ist dann diese aufgabe auch falsch?:

Nein, das ist richtig.

28.10.2007, 00:28

marci_

Auf diesen Beitrag antworten »

liegt mein fehler darin, dass ich nicht für k sondern für n, (n+1) eingesetzt habe?

also:

$\begin{eqnarray*} \sum_{k=0}^n~\begin{pmatrix} n \\ k \end{pmatrix} =2^n \end{eqnarray*}$

...

induktionsschritt:

$\begin{eqnarray*} \sum_{k=0}^{m+1}~\begin{pmatrix} n \\ k \end{pmatrix} =2^{m+1} \end{eqnarray*}$

$\begin{eqnarray*} \sum_{k=0}^{m}~\begin{pmatrix} n \\ k \end{pmatrix} + \begin{pmatrix} n \\ m+1 \end{pmatrix} =2^{m+1} \end{eqnarray*}$

$\begin{eqnarray*} 2^m + \begin{pmatrix} n \\ m+1 \end{pmatrix} =2^{m+1} \end{eqnarray*}$

stimmt das bis hier?
wie würde es jetzt weiter gehen?

28.10.2007, 00:51

therisen

Auf diesen Beitrag antworten »

RE: summenformel beweisen
Nein, der Induktionsschritt wäre zu zeigen, dass $\begin{eqnarray*} \sum_{k=0}^{n+1}~ \begin{pmatrix} n+1 \\ k \end{pmatrix} =2^{n+1} \end{eqnarray*}$ gilt.

28.10.2007, 00:58

marci_

Auf diesen Beitrag antworten »

warum wird hier schon im binomialkoeffizienten das (n+1) eingesetzt?

in der anderen aufgabe war das doch auch nicht so!

28.10.2007, 01:02

therisen

Auf diesen Beitrag antworten »

Dann mach die Augen auf!

$\begin{eqnarray*} A(n):=\sum_{k=0}^n~ \begin{pmatrix} m+k \\ k \end{pmatrix} \end{eqnarray*}$

$\begin{eqnarray*} \Rightarrow A(n+1)=\sum_{k=0}^{n+1}~ \begin{pmatrix} m+k \\ k \end{pmatrix} \end{eqnarray*}$

28.10.2007, 01:19

marci_

Auf diesen Beitrag antworten »

sorry, aber ich seh das immer noch nicht...
die aussage lautet doch:

$\begin{eqnarray*} \sum_{k=0}^{n+1}~ \begin{pmatrix} n \\ k\end{pmatrix} =2^n \end{eqnarray*}$

28.10.2007, 01:22

therisen

Auf diesen Beitrag antworten »

Zitat:

Original von marci_
die aussage lautet doch:

$\begin{eqnarray*} \sum_{k=1}^{n+1}~ \begin{pmatrix} n \\ k\end{pmatrix} =2^n \end{eqnarray*}$

Nein. Die Indexverschiebung ist falsch.

28.10.2007, 01:24

marci_

Auf diesen Beitrag antworten »

sorry, habs geändert( habs vergessen vom formeleditor zu ändern)...

aber ich versteh nicht ganz den zusammenhang zwischen deiner aussage und der aufgabenstellung...

28.10.2007, 01:32

therisen

Auf diesen Beitrag antworten »

RE: summenformel beweisen
Nimm dir einen Stift und schreibe

$\begin{eqnarray*} \sum_{k=0}^n~ \begin{pmatrix} n \\ k \end{pmatrix} =2^n \end{eqnarray*}$

auf. Jetzt ersetzt du jedes n durch ein n+1. Was steht dann da?

28.10.2007, 01:59

marci_

Auf diesen Beitrag antworten »

es steht dann da:

$\begin{eqnarray*} \sum_{k=0}^{n+1}~ \begin{pmatrix} n+1 \\ k \end{pmatrix} =2^{n+1} \end{eqnarray*}$

jetzt verstehe ich aber nicht, warum in der aufgabe von zuvor nur auf der rechten seite m+1 eingesetzt wird:

$\begin{eqnarray*} \sum_{k=0}^{n+1}~ \begin{pmatrix} m+k \\ k \end{pmatrix}= \begin{pmatrix} m+(n+1)+1 \\ (n+1) \end{pmatrix} \end{eqnarray*}$

28.10.2007, 09:10

klarsoweit

Auf diesen Beitrag antworten »

Zitat:

Original von marci_
$\begin{eqnarray*} \sum_{k=0}^n~ \begin{pmatrix} m+k \\ k \end{pmatrix} =\begin{pmatrix} m+n+1 \\ n \end{pmatrix} \end{eqnarray*}$

Suchspiel: wo sind in dieser Formel die n's versteckt? Ersetze jedes gefundene n durch n+1. Die m's werden nicht verändert.

28.10.2007, 13:26

marci_

Auf diesen Beitrag antworten »

ai, ich weiß, was ich immer falsch gemacht habe, in jeder bisher behandelten induktion stand im binomialkoeffizienten kein n...und ich habs nicht kapiert!
vielen dank für die geduld!

also:

$\begin{eqnarray*} \sum_{k=0}^{n+1}~\begin{pmatrix} n+1 \\ k \end{pmatrix} =2^{n+1} \end{eqnarray*}$

$\begin{eqnarray*} \sum_{k=0}^{n}~\begin{pmatrix} n+1 \\ k \end{pmatrix} +\begin{pmatrix} n+2 \\ k \end{pmatrix} =2^{n+1} \end{eqnarray*}$

muss ich jetzt das k durch das n ausdrücken?
n=k ?

28.10.2007, 13:49

klarsoweit

Auf diesen Beitrag antworten »

Zitat:

Original von marci_
$\begin{eqnarray*} \sum_{k=0}^{n}~\begin{pmatrix} n+1 \\ k \end{pmatrix} +\begin{pmatrix} n+2 \\ k \end{pmatrix} =2^{n+1} \end{eqnarray*}$

muss ich jetzt das k durch das n ausdrücken?
n=k ?

Unfug. Sowohl, was die Gleichung angeht als auch die Frage. Wie lautet denn der letzte Summand von $\begin{eqnarray*} \sum_{k=0}^{n+1}~\binom{n+1}{k} \end{eqnarray*}$ ?

28.10.2007, 14:20

marci_

Auf diesen Beitrag antworten »

also bis hier stimmts doch noch?

$\begin{eqnarray*} \sum_{k=0}^{n+1}~\begin{pmatrix} n+1 \\ k \end{pmatrix} =2^{n+1} \end{eqnarray*}$

ich verstehs grad nicht mehr...wie kann ich das hier außeinaderziehen:
$\begin{eqnarray*} \sum_{k=0}^{n+1}~\begin{pmatrix} n+1 \\ k \end{pmatrix} \end{eqnarray*}$

lautet der letzte summand: $\begin{eqnarray*} \begin{pmatrix} n+1 \\ n+1 \end{pmatrix} \end{eqnarray*}$

28.10.2007, 14:52

klarsoweit

Auf diesen Beitrag antworten »

Zitat:

Original von marci_
also bis hier stimmts doch noch?

$\begin{eqnarray*} \sum_{k=0}^{n+1}~\begin{pmatrix} n+1 \\ k \end{pmatrix} =2^{n+1} \end{eqnarray*}$

Ja. Wobei das die im Induktionsschritt zu zeigende Aussage ist. Üblicherweise nimmt man die linke Seite her und formt diese unter Verwendung der Induktionsannahme solange um, bis die rechte Seite rauskommt.

Zitat:

Original von marci_
lautet der letzte summand: $\begin{eqnarray*} \begin{pmatrix} n+1 \\ n+1 \end{pmatrix} \end{eqnarray*}$

Ja. Man könnte dazu auch 1 sagen. Augenzwinkern

Augenzwinkern

28.10.2007, 15:24

marci_

Auf diesen Beitrag antworten »

also wenn ich dann das hier habe:

$\begin{eqnarray*} \sum_{k=0}^{n+1}~\begin{pmatrix} n+1 \\ k \end{pmatrix} =2^{n+1} \end{eqnarray*}$

$\begin{eqnarray*} \sum_{k=0}^{n}~\begin{pmatrix} n+1 \\ k \end{pmatrix} +1=2^{n+1} \end{eqnarray*}$

und woran sehe ich nun, dass die linke seite gleich der rechten seite ist?

28.10.2007, 15:33

therisen

Auf diesen Beitrag antworten »

RE: summenformel beweisen
Zeige $\begin{eqnarray*} \sum_{k=0}^{n+1}{n+1\choose k}=2\sum_{k=0}^{n}{n\choose k} \end{eqnarray*}$ . Das genügt.

28.10.2007, 15:35

klarsoweit

Auf diesen Beitrag antworten »

Tja, da mußt du noch fleißig umformen. Unter anderem mußt du auch die Beziehung
$\begin{eqnarray*} \binom{n+1}{k} = \binom n k + \binom{n}{k-1} \end{eqnarray*}$
verwenden.

Schreibe dazu vorher noch $\begin{eqnarray*} \sum_{k=0}^n~\binom{n+1}{k} = 1 + \sum_{k=1}^n~\binom{n+1}{k} \end{eqnarray*}$

01.11.2007, 22:09

Pumbaa

Auf diesen Beitrag antworten »

hallo.
Ich hab mich auch an der Aufgabe versucht, finde und finde aber meinen Fehler nicht.

und zwar:
$\begin{eqnarray*} \sum_{k=0}^{n+1}~\binom{n+1}{k}\\=\binom{n+1}{n+1}+\binom{n+1}{0}+\sum_{k=1}^{n}~\binom{n+1}{k}\\= 1+1+ \sum_{k=1}^{n}~\binom{n}{k} + \sum_{k=1}^{n}~\binom{n}{k-1}\\= 2 + \sum_{k=0}^{n}~\binom{n}{k} - \binom{n}{0} +\sum_{k=0}^{n-1}~\binom{n}{k}\\=1+2^n+ \sum_{k=0}^{n}~\binom{n}{k}-\binom{n}{n-1}\\=1+2^{n+1} -n \end{eqnarray*}$

Wir ihr seht, hab ich nach der Parametertransformation ein -n statt des gewünschten -1 erzeugt...

und ich finde den wurm nicht.

jochen

02.11.2007, 09:20

klarsoweit

Auf diesen Beitrag antworten »

Zitat:

Original von Pumbaa
$\begin{eqnarray*} =1+2^n+ \sum_{k=0}^{n}~\binom{n}{k}-\binom{n}{n-1} \end{eqnarray*}$

Wie bist du da auf $\begin{eqnarray*} \binom{n}{n-1} \end{eqnarray*}$ gekommen?

Tipp: mache Umformungen schön langsam Schritt für Schritt und nicht 2 Schritte in einem. Augenzwinkern

Augenzwinkern

02.11.2007, 09:31

Pumbaa

Auf diesen Beitrag antworten »

Auwei, danke.
Aufm Papier sinds schon mehr Schritte gewesen. Aber hab wohl doch gedusselt, und nicht das "nte Element" in die Summe gestopft, sondern das "n-1-te" nen zweites mal dazugetan. Und die Grenzen aber doch richtig geändert smile

smile

Dankee! Nun ists klar

1

Verwandte Themen

Die Beliebtesten »

Die Größten »

Die Neuesten »