Vollständige Induktion < Induktion < eindimensional < reell < Analysis < Hochschule < Mathe < Vorhilfe
|
| Aufgabe | Man zeige mittels vollständiger Induktion:
[mm] \summe_{k=0}^{n}\vektor{n \\ k} [/mm] = [mm] 2^{n} [/mm] |
Hallo, hab ein kleines Problem mit obiger Aufgabe.
Gut zuerst mal der Induktionsstart mit $n=1$:
[mm] $\vektor{1 \\ 0} [/mm] + [mm] \vektor{1 \\ 1} [/mm] = [mm] 2^{1}$
[/mm]
$1 = 1$
Stimmt, nun der Induktionsschluss $n+1$:
[mm] \summe_{k=0}^{n+1}\vektor{n+1 \\ k} [/mm] = [mm] 2^{n+1}
[/mm]
[mm] \summe_{k=0}^{n}\vektor{n+1 \\ k} [/mm] + [mm] \vektor{n+1 \\ n+1} [/mm] = [mm] 2^{n+1}
[/mm]
Bei der Zeile bin ich mir schon nicht mehr sicher.
Kann man das so machen?
Lg
|
|
| |
|
| Status: |
(Antwort) fertig  | | Datum: | 20:50 So 12.06.2011 | | Autor: | snikch |
> Man zeige mittels vollständiger Induktion:
>
> [mm]\summe_{k=0}^{n}\vektor{n \\ k}[/mm] = [mm]2^{n}[/mm]
>
> Hallo, hab ein kleines Problem mit obiger Aufgabe.
>
> Gut zuerst mal der Induktionsstart mit [mm]n=1[/mm]:
> [mm]\vektor{1 \\ 0} + \vektor{1 \\ 1} = 2^{1}[/mm]
> [mm]1 = 1[/mm]
>
> Stimmt, nun der Induktionsschluss [mm]n+1[/mm]:
>
> [mm]\summe_{k=0}^{n+1}\vektor{n+1 \\ k}[/mm] = [mm]2^{n+1}[/mm]
>
> [mm]\summe_{k=0}^{n}\vektor{n+1 \\ k}[/mm] + [mm]\vektor{n+1 \\ n+1}[/mm] =
> [mm]2^{n+1}[/mm]
>
> Bei der Zeile bin ich mir schon nicht mehr sicher.
> Kann man das so machen?
>
> Lg
Hi
der letzte Schritt stimmt nicht.
Betrachte stattdessen [mm] 2^{n+1}=2^n [/mm] + [mm] 2^n
[/mm]
Benutze nun die Induktionsvoraussetzung und versuche aus den Summen die 1 herauszuziehen. Dann kann eine bekannte(?) Identität verwendet werden.
|
|
|
| |
|
Danke
$ [mm] \summe_{k=0}^{n+1}\vektor{n+1 \\ k} [/mm] = [mm] 2^{n+1} [/mm] $
Wenn ich die 1 Herausziehe bekomm ich doch folgendes oder:
$ [mm] \summe_{k=0}^{n}\vektor{n \\ k} [/mm] + [mm] \vektor{n+1 \\ n+1} [/mm] $
Und das ist wiederum [mm] 2^{n} [/mm] + 1 = [mm] 2^{n+1} [/mm] und das stimmt nicht.
Wie hebe ich die 1 richtig aus der Summe heraus?
|
|
|
| |
|
| Status: |
(Antwort) fertig | | Datum: | 00:18 Mo 13.06.2011 | | Autor: | barsch |
Hi,
es ist [mm]{{n+1 \choose k}}={{n \choose k-1}}+{{n \choose k}}[/mm]. Das kannst du benutzen. Dann beachten, dass [mm]{{n \choose k}}=0 \ \ \text{für} \ \ k>n[/mm] und eine geeignete Indexverschiebung vornehmen. Das bringt dich an den Tipp von snikch: [mm](2^n+2^n)=2^{n+1}[/mm].
Viel Erfolg.
Gruß
barsch
|
|
|
| |
|
> Hi,
>
> es ist [mm]{{n+1 \choose k}}={{n \choose k-1}}+{{n \choose k}}[/mm].
Hmm. Das versteh ich nicht, du meinst doch [mm] \summe_{k=0}^{n+1} \vektor{n+1 \\ k} [/mm] oder? Ist das dasselbe wie [mm] \summe_{k=0}^{n} \vektor{n \\ k-1} [/mm] + [mm] \summe_{k=0}^{n} \vektor{n \\ k} [/mm] ?
[mm] \summe_{k=0}^{n} \vektor{n \\ k} [/mm] entspricht [mm] $2^{n}$
[/mm]
Wie bring ich [mm] \summe_{k=0}^{n} \vektor{n \\ k-1} [/mm] auf eine andere Form?
Wie wende ich hier eine Indexverschiebung an?
Etwa so?:
[mm] \summe_{k=1}^{n} \vektor{n \\ k} [/mm] + [mm] \vektor{n \\ 0}
[/mm]
[mm] \vektor{n \\ 0} [/mm] wäre ja 1
Mein Rechenweg kommt mir doch sehr suspekt vor...
Danke, der Erfolg hat sich leider noch nicht eingestellt *g*
Lg
|
|
|
| |
|
Hallo,
Es sind schon viele richtige Schritte dabei.
> > es ist [mm]{{n+1 \choose k}}={{n \choose k-1}}+{{n \choose k}}[/mm].
>
> Hmm. Das versteh ich nicht, du meinst doch
> [mm]\summe_{k=0}^{n+1} \vektor{n+1 \\
k}[/mm] oder?
Natürlich meint er, dass du es so anwenden sollst (also in der Summe), aber die Identität oben gilt doch auch ohne Summen!
Ist das dasselbe
> wie [mm]\summe_{k=0}^{n} \vektor{n \\
k-1}[/mm] + [mm]\summe_{k=0}^{n} \vektor{n \\
k}[/mm]
> ?
Nicht ganz:
[mm] $\sum_{k=0}^{n+1}\vektor{n+1\\k} \quad=\quad \sum_{k=0}^{n+1}\vektor{n\\ k-1} [/mm] + [mm] \sum_{k=0}^{n+1}\vektor{n\\k} \quad=\quad \sum_{k=1}^{n+1}\vektor{n\\ k-1} [/mm] + [mm] \sum_{k=0}^{n}\vektor{n\\k}$ [/mm] (***)
> [mm]\summe_{k=0}^{n} \vektor{n \\
k}[/mm] entspricht [mm]2^{n}[/mm]
... nach Induktionsvoraussetzung, richtig. (*)
> Wie bring ich [mm]\summe_{k=0}^{n} \vektor{n \\
k-1}[/mm] auf eine
> andere Form?
> Wie wende ich hier eine Indexverschiebung an?
>
> Etwa so?:
> [mm]\summe_{k=1}^{n} \vektor{n \\
k}[/mm] + [mm]\vektor{n \\
0}[/mm]
>
> [mm]\vektor{n \\
0}[/mm] wäre ja 1
nicht ganz. Du hast in die falsche Richtung verschoben. Wir wollen, dass die Summe [mm] $\sum_{k=1}^{n+1}\vektor{n\\ k-1}$ [/mm] bei $k = 0$ anfängt und bei $k = n$ aufhört. Dafür musst du also k durch k+1 ersetzen. (**)
Dann bist schon fast fertig, wenn du deine Erkenntnissen in (*) und (**) in (***) einsetzt!
Grüße,
Stefan
|
|
|
| |
|
Ich danke dir!
Hätte aber noch ein paar Fragen.
1) Wieso ist [mm] \summe_{k=0}^{n+1}\vektor{n \\ k} [/mm] dasselbe wie [mm] \summe_{k=0}^{n}\vektor{n \\ k}?
[/mm]
2) Wieso ist [mm] \summe_{k=0}^{n+1}\vektor{n \\ k-1} [/mm] dasselbe wie [mm] \summe_{k=1}^{n+1}\vektor{n \\ k-1}? [/mm]
Wenn ich es also richtig verschiebe bekomm ich folgendes raus:
[mm] \summe_{k=0}^{n+1}\vektor{n \\ k} [/mm] + [mm] 2^{n} [/mm] und das entspricht [mm] 2^{n+1}
[/mm]
Ich danke euch!
Lg
|
|
|
| |
|
| Status: |
(Antwort) fertig | | Datum: | 13:54 Mo 13.06.2011 | | Autor: | barsch |
Hi,
> Hätte aber noch ein paar Fragen.
>
> 1) Wieso ist [mm]\summe_{k=0}^{n+1}\vektor{n \\
k}[/mm] dasselbe wie [mm]\summe_{k=0}^{n}\vektor{n \\
k}?[/mm]
ich hatte ja geschrieben: [mm] {{n \choose k}}=0 \ \ \text{für} \ \ k>n [/mm].
Dann ist doch [mm]\summe_{k=0}^{n+1}\vektor{n \\
k}=\summe_{k=0}^{n}\vektor{n \\
k}+{{n \choose n+1}}=\summe_{k=0}^{n}\vektor{n \\
k}+0[/mm], da [mm]n+1>n[/mm].
> 2) Wieso ist [mm]\summe_{k=0}^{n+1}\vektor{n \\
k-1}[/mm] dasselbe wie [mm]\summe_{k=1}^{n+1}\vektor{n \\
k-1}?[/mm]
Erst einmal ist [mm] {{n \choose k}}[/mm] nur für nichnegative k definiert; was stünde da, wenn du nur den Summand für k=0 betrachtest?
> Wenn ich es also richtig verschiebe bekomm ich folgendes
> raus:
> [mm]\summe_{k=0}^{n+1}\vektor{n \\
k}[/mm] + [mm]2^{n}[/mm] und das
> entspricht [mm]2^{n+1}[/mm]
Das ist zwar korrekt, es fehlt aber der entscheidende Zwischenschritt. Betrachte diesen Teil: [mm]\summe_{k=1}^{n+1}\vektor{n \\
k-1}[/mm]
Du willst, dass die Summanden die gleichen bleiben, die Summe aber von k=0 bis n (nicht n+1) läuft. Jetzt kommt die Indexverschiebung:
[mm]\summe_{k=1}^{n+1}\vektor{n \\
k-1}=[/mm][mm]\summe_{k=0}^{n}\vektor{n \\
(k+1)-1}=...[/mm]
Und dann alles zusammensetzen:
[mm]\summe_{k=0}^{n+1}{{n+1 \choose k}}=\summe_{k=0}^{n+1}{{n \choose k-1}}+\summe_{k=0}^{n+1}{{n \choose k}}=... [/mm]
Gruß
barsch
|
|
|
| |
|
> Erst einmal ist [mm]{{n \choose k}}[/mm] nur für nichnegative k
> definiert; was stünde da, wenn du nur den Summand für k=0
> betrachtest?
>
Das wäre dann [mm] \vektor{n \\ -1} [/mm] und das wäre nicht definiert. Aus diesem Grund muss ich k=1 annehmen und k=0 fällt somit weg?
Ich danke dir! Nun wird mir einiges klarer.
Lg
|
|
|
| |
|
| Status: |
(Antwort) fertig | | Datum: | 16:08 Mo 13.06.2011 | | Autor: | barsch |
> Das wäre dann [mm]\vektor{n \\
-1}[/mm] und das wäre nicht
> definiert. Aus diesem Grund muss ich k=1 annehmen und k=0
> fällt somit weg?
[mm]\vektor{n \\
-1}=0[/mm]
Gruß
|
|
|
| |
|
Hallo dreamweaver,
ich denke zwar, dass der Weg, den Du mit den anderen gerade beackerst, auch der ist, den der Aufgabensteller haben will.
Wenn Du aber [mm] (a+b)^n=\summe_{k=0}^{n}\vektor{n\\k}a^k*b^{n-k} [/mm] benutzen darfst, dann bist Du viel schneller fertig, sei es mit oder (normalerweise) ohne Induktion. Setze dazu a=b=1.
Grüße
reverend
|
|
|
| |
|
> Man zeige mittels vollständiger Induktion:
>
> [mm]\summe_{k=0}^{n}\vektor{n \\ k}[/mm] = [mm]2^{n}[/mm]
Hallo dreamweaver,
einen netten Beweis durch vollständige Induktion kann
man aufstellen, wenn man von der kombinatorischen
Bedeutung von [mm] \vektor{n \\ k} [/mm] ausgehen darf:
[mm] \vektor{n \\ k} [/mm] steht für die Anzahl der Möglichkeiten, aus
einer n-elementigen Grundmenge eine k-elementige
Teilmenge herauszugreifen. Die angegebene Summe steht
dann für die Anzahl aller Teilmengen der Grundmenge.
Nun bleibt nur noch zu zeigen, dass sich die Anzahl
der möglichen Teilmengen verdoppelt, wenn man der
ursprünglichen (n-elementigen) Grundmenge ein
weiteres Element hinzufügt. Außer den schon vor-
handenen [mm] 2^n [/mm] Teilmengen kommen genau noch alle
diejenigen dazu, die aus einer der schon vorhandenen
Teilmengen mit dem zugefügten neuen Element
bestehen.
LG Al-Chw.
|
|
|
|
