Vollständige Induktion mit n über k

28.10.2004, 12:59

UnwissenderPartII

Vollständige Induktion mit n über k

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

Beweis per v.I.
$\begin{eqnarray*} \sum_{k=1}^n~\begin{pmatrix} n \\ k \\ \end{pmatrix}=<br /> \sum_{k=1}^n~\begin{pmatrix} n \\ k \\ \end{pmatrix}+ \begin{pmatrix} n+1 \\ k \end{pmatrix}=<br /> 2^{n}+\frac{(n+1)!}{k!(n+1-k)!} \end{eqnarray*}$

Beim Summenzeichen muss natürlich n+1 stehen...allerdings hänge ich an der Stelle ein bisschen feste, ist mein Ansatz soweit richtig? Ich glaub einfach mir fehlen nur die Rechenregeln für Fakultäten, wenn ihr mir da ein bisschen weiter helfen könntet.

BIG THANKS!
(sorry, habe doppelt gepostet und ein Fehler gemacht, den ich ja als unregistrierter User nich korrigierenkann...werd mich mal anmelden....:-)

28.10.2004, 16:17

defatigation

Auf diesen Beitrag antworten »

kann keiner helfen..... traurig

28.10.2004, 16:49

Gast

Auf diesen Beitrag antworten »

RE: Vollständige Induktion mit n über k
Guck Dir mal die Binomische Formel an:

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

Wie sieht's aus mit $\begin{eqnarray*} a=b=1 \end{eqnarray*}$ ?

28.10.2004, 16:58

Leopold

Auf diesen Beitrag antworten »

Falls du die binomische Formel nicht verwenden darfst, dann beachte:

Du mußt auch beim Binomialkoeffizienten von $\begin{eqnarray*} n \end{eqnarray*}$ auf $\begin{eqnarray*} n+1 \end{eqnarray*}$ umschalten.
Verwende die folgende Regel vom Pascalschen Dreieck:

$\begin{eqnarray*} {{n+1} \choose k }= {{n} \choose {k-1}} + {n \choose k} \, , \ \ 1 \leq k \leq n \end{eqnarray*}$

Ziehe zuvor die Glieder für $\begin{eqnarray*} k=0 \end{eqnarray*}$ und $\begin{eqnarray*} k=n+1 \end{eqnarray*}$ aus der Summe heraus.

28.10.2004, 21:11

Mathespezialschüler

Auf diesen Beitrag antworten »

Zitat:

Original von UnwissenderPartII
Sei
$\begin{eqnarray*} \sum_{k=1}^n~\begin{pmatrix} n \\ k \\ \end{pmatrix}= 2^{n} \end{eqnarray*}$

Diese Formel kannst du gar nicht beweisen, denn sie ist falsch! Vielmehr gilt

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

Bei deiner Formel wird der Indukionsanfang sicher nicht funktionieren.
Einen Tipp, wie der Beweis funktioniert, hat Leopold ja schon gegeben. Augenzwinkern

28.10.2004, 23:29

defatigation

Auf diesen Beitrag antworten »

Yo,mein Schreibfehler, hast natürlich recht!@Mathespezialschüler

Könntest du das ein bisschen genauer sagen, oder nen Beispiel geben: "Ziehe zuvor die Glieder für k=0 und k=n+1 aus der Summe heraus."

Stecke immer noch bei
.... $\begin{eqnarray*} =2^{n}+\begin{pmatrix} n \\ k-1 \end{pmatrix}+\begin{pmatrix} n \\ k \end{pmatrix} \end{eqnarray*}$
fest. Die Summe der Binominalkoeffizienten muss ja 2 ergeben, damit $\begin{eqnarray*} 2^{n}+2= 2^{n+1} \end{eqnarray*}$ . Aber wenn ich die Koeffizienten in $\begin{eqnarray*} \frac{n!}{k!(n-k)!} \end{eqnarray*}$ -Form Ausdrücke, komme ich auch nich wirklich weiter, hätte nämlich dann
$\begin{eqnarray*} \frac{n!}{(k-1)!(n-k+1!)}+\frac{n!}{k!(n-k)!} \end{eqnarray*}$

Und da is dann irgendwie schluss für mich traurig

28.10.2004, 23:33

Mathespezialschüler

Auf diesen Beitrag antworten »

Also $\begin{eqnarray*} 2^n+2=2^{n+1} \end{eqnarray*}$ stimmt ganz sicher nicht!

Und außerdem hast du die Formel von Anfang an schon falsch aufgeschrieben für n+1. Es müsste nämlich heißen:

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

und da kommst du nicht ganz so einfach weiter. Dazu musst du dann die von Leopold angegebene Formel benutzen!

28.10.2004, 23:39

defatigation

Auf diesen Beitrag antworten »

Ach...ich glaub ich bin bisschen heute durchn Wind.....natürlich stimmt der &%$§ mit 2^n + 2 =2 ^n+1 nich....tja ja...wenn man nich mal + von * unterscheiden kann...ich glaub ich geh zurück in die 1. Klasse....oder erstmal ins Bett;-) NACHT!

30.10.2004, 13:43

defatigation

Auf diesen Beitrag antworten »

ach...komm einfach nich weiter, habe jetzt leopolds ratschlag befolgt, bringt mich aber irgendwie nich weiter...

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

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

30.10.2004, 14:01

Mathespezialschüler

Auf diesen Beitrag antworten »

1. Bitte unterlasse solche PNs, mit denen du jmd. dazu aufforderst, nochmal in das Thema zu gucken oder Ähnliches!
2. Beachte erstmal Leopolds Bemerkung:

Zitat:

Original von Leopold
Ziehe zuvor die Glieder für $\begin{eqnarray*} k=0 \end{eqnarray*}$ und $\begin{eqnarray*} k=n+1 \end{eqnarray*}$ aus der Summe heraus.

Danach sollst du die Formel für alle Summanden der Summe anwenden!

30.10.2004, 14:09

Leopold

Auf diesen Beitrag antworten »

Und noch ein Tip!
Du scheinst Schwierigkeiten mit dem Verständnis des Summenzeichens zu haben. Vielleicht hilft es dir, wenn du das einfach einmal wegläßt und mit Pünktchen arbeitest:

$\begin{eqnarray*} {{n+1} \choose 0} + {{n+1} \choose 1} + {{n+1} \choose 2} + {{n+1} \choose 3} + \dots + {{n+1} \choose {n-1}} + {{n+1} \choose n} + {{n+1} \choose {n+1}} \end{eqnarray*}$

Den Wert des ersten und letzten Summanden kannst du direkt angeben. Und für die anderen mußt du die von mir angegebene Formel verwenden. Ich zeige es einmal am Beispiel des dritten Summanden:

$\begin{eqnarray*} {{n+1} \choose 2} = {n \choose 1} + {n \choose 2} \end{eqnarray*}$

Und jetzt habe ich dir die Aufgabe schon fast gelöst.
Den Rest solltest du jetzt wirklich selber probieren.

Neue Frage »

Antworten »

Vollständige Induktion mit n über k

Verwandte Themen