Vollständige Induktion < Analysis < Hochschule < Mathe < Vorhilfe
|
| Status: |
(Frage) beantwortet  | | Datum: | 16:29 Mi 26.10.2005 | | Autor: | Ernesto |
Ich benötige Beistand bei folgenden Aufgaben ich beisse mir die Zähne aus . Ich habe alles Versucht Binominalkoeefizient und verschiedene Identitäten, aber es hilft alles nichts.
nun zum ernst der lage
[mm] \summe_{k=1}^{n} \vektor{n \\ k} [/mm] = [mm] 2^n
[/mm]
bitt um beistand
Gruß Thomas
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig  | | Datum: | 17:02 Mi 26.10.2005 | | Autor: | Roadrunner |
Hallo Ernesto!
Kann es sein, dass Du die Aufgabe falsch abgeschrieben hast und die Laufindex bei $k \ = \ [mm] \red{0}$ [/mm] starten muss? Oder es heißt [mm] $2^{n \ \red{- \ 1}}$ [/mm] ?
Anderenfalls erhalte ich nämlich auch nichts vernünftiges heraus ...
Gruß vom
Roadrunner
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig | | Datum: | 18:26 Mi 26.10.2005 | | Autor: | Ernesto |
hast recht, der index muss bei null beginnen , sorry
|
|
|
| |
|
An dieser Aufgabe beiße ich mir z.Z. auch die Zähne aus. Habe folgende Idee.
Induktionsanfang ist klar, stimmt auch soweit:
"n->n+1"
[mm] \summe_{k=0}^{n+1} \vektor{n+1 \\ k} [/mm]
Jetzt müsste ich nach der Regel [mm] \vektor{n+1 \\ k}= \vektor{n \\ k}+ \vektor{n \\ k-1} [/mm] den Term unter dem Summenzeichen zerlegen können. Nur leider kann dann mein Summenzeichen nicht mehr bei K=0 beginnen, da bei k-1 dann eine negative Zahl herauskäme. So komme ich nicht weiter.
2^(n+1)=2 [mm] \summe_{k=1}^{n} \vektor{n \\ k} [/mm] komme ich auch nicht weiter. [mm] \summe_{k=1}^{n} \vektor{n \\ k}+\summe_{k=1}^{n} \vektor{n \\ k} [/mm] müsste ich doch unter einem Summenzeichen zusammenfassen können. Hilft mir aber auch nicht weiter.
Wäre für Tipps dankbar.
Oder ist gleich der Induktionsschritt falsch und es müsste heißen:
[mm] \summe_{k=1}^{n+1} \vektor{n \\ k} [/mm] . Denn eigentlich dürfte ich unter der Summe ja nichts verändern.
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig | | Datum: | 20:21 Mi 26.10.2005 | | Autor: | Mira1 |
Ich muss diese Aufgabe auch für mein Übungsblat lösen.
Ich denke es müste [mm] \summe_{k=0}^{n+1} \vektor{n \\ k} [/mm] heißen. da du ja die summe für die nächst gößere Zahl zeigwn willst.
Ich habe angefangen mit:
[mm] \summe_{k=0}^{n+1} \vektor{n \\ k}
[/mm]
= [mm] \summe_{k=0}^{n+1} \bruch{(n+1)!}{k!(n+1-k)!}
[/mm]
= [mm] \summe_{k=0}^{n} \bruch{n!}{k!(n-k)!} [/mm] + [mm] \bruch{(n+1)!}{k!(n+1-k)!}
[/mm]
aber ich bin mir nicht so sicher... das ist ein ziemliches rumgewusel mit der oberen grenze.
Mein Ziel ist es aber aus 2^(n+1) zu kommen was ja [mm] 2^n*2^1 [/mm] ist und auf [mm] 2^n [/mm] komm ich mit der induktionsvoraussetzung... aber ich komme wie ihr nicht weiter
|
|
|
| |
|
> An dieser Aufgabe beiße ich mir z.Z. auch die Zähne aus.
> Habe folgende Idee.
>
> Induktionsanfang ist klar, stimmt auch soweit:
>
> "n->n+1"
>
> [mm]\summe_{k=0}^{n+1} \vektor{n+1 \\ k}[/mm]
>
> Jetzt müsste ich nach der Regel [mm]\vektor{n+1 \\ k}= \vektor{n \\ k}+ \vektor{n \\ k-1}[/mm]
> den Term unter dem Summenzeichen zerlegen können.
Hallo,
mach einen kleinen Kunstgriff vorweg, und Deine Schwierigkeiten werden verschwinden:
[mm] \summe_{k=0}^{n+1} \vektor{n+1 \\ k}
[/mm]
[mm] =\vektor{n+1 \\ 0}+\vektor{n+1 \\ n+1}+\summe_{k=1}^{n} \vektor{n+1 \\ k}=...
[/mm]
Jetzt kannst Du weitermachen wie von Dir geplant.
Nun sag' ich Dir noch zwei "Tricks".
Wenn Du [mm] \summe_{i=1}^{n}a_i [/mm] dastehen hast, willst aber [mm] \summe_{0=1}^{n}a_i [/mm] haben, kannst Du es so machen:
[mm] \summe_{i=1}^{n}a_i= -a_{0}+\summe_{i=0}^{n}a_i [/mm] .
(Für die obere Grenze ensprechend, falls es mal so ein Problem geben sollte.)
Und noch etwas. Manchmal ist [mm] \summe_{i=1}^{n}a_{i-1} [/mm] sehr lästig. Abhilfe schafft das Verschieben der Summationsgrenze. Es ist [mm] \summe_{i=1}^{n}a_{i-1}=\summe_{i=0}^{n-1}a_{i}.
[/mm]
(Mach' Dir klar, daß es so ist, dann kannst Du es Dir leichter merken.)
Und nun hoffe ich, daß Du mit Deiner Aufgabe ganz schnell ans Ziel kommst.
Gruß v. Angela
Nur
> leider kann dann mein Summenzeichen nicht mehr bei K=0
> beginnen, da bei k-1 dann eine negative Zahl herauskäme. So
> komme ich nicht weiter.
> 2^(n+1)=2 [mm]\summe_{k=1}^{n} \vektor{n \\ k}[/mm] komme ich auch
> nicht weiter. [mm]\summe_{k=1}^{n} \vektor{n \\ k}+\summe_{k=1}^{n} \vektor{n \\ k}[/mm]
> müsste ich doch unter einem Summenzeichen zusammenfassen
> können. Hilft mir aber auch nicht weiter.
> Wäre für Tipps dankbar.
> Oder ist gleich der Induktionsschritt falsch und es müsste
> heißen:
>
> [mm]\summe_{k=1}^{n+1} \vektor{n \\ k}[/mm] .
Neeeeeeeeeein!!!!!!!!!!!!!!!!! Bloß nicht sowas!!!!!!!!!!!!!
Denn eigentlich dürfte
> ich unter der Summe ja nichts verändern.
|
|
|
| |
|
Wer sagt eigentlich, dass man es mit vollständiger Induktion machen muss.
Ist anders leichter:
[mm] \summe_{k=0}^{n} \vektor{n \\ k}
[/mm]
= [mm] \summe_{k=0}^{n} \vektor{n \\ k}1^{m}
[/mm]
= [mm] \summe_{k=0}^{n} \vektor{n \\ k}1^{k}1^{m-k} [/mm]
Damit wäre man beim binomischen Lehrsatz für den gilt [mm] (a+b)^{n} [/mm]
a=b=1.
Also [mm] \summe_{k=0}^{n} \vektor{n \\ k}=(1+1)^{n}=2^{n} \Box
[/mm]
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig | | Datum: | 20:23 Mi 26.10.2005 | | Autor: | Mira1 |
Mein Übungsblatt sagt leider vollständige induktion. Auf diese Idee hatte mich auch schon ein Buch gebracht...
|
|
|
| |
|
So, es geht auch mit vollständiger Induktion.
Beh.: [mm] \summe_{k=0}^{n} \vektor{n \\ k}=2^{n}
[/mm]
Induktionsanfang bei n=1
[mm] \summe_{k=0}^{1} \vektor{1 \\ k}=2=2^{1}
[/mm]
Induktionsschluss "n->n+1"
zzg.: [mm] \summe_{k=0}^{n+1} \vektor{n+1 \\ k}=2^{n+1}
[/mm]
[mm] 2^{n+1}=2*2^{n}=2 \summe_{k=0}^{n} \vektor{n \\ k}
[/mm]
[mm] =\summe_{k=0}^{n} \vektor{n \\ k}+\summe_{k=0}^{n} \vektor{n \\ k}=\summe_{k=1}^{n+1} \vektor{n \\ k-1}+\summe_{k=0}^{n} \vektor{n \\ k}=\summe_{k=1}^{n} \vektor{n \\ k-1}+1+1+\summe_{k=1}^{n} \vektor{n \\ k}=1+\summe_{k=1}^{n} (\vektor{n \\ k-1}+ \vektor{n \\ k})+1=1+\summe_{k=1}^{n} \vektor{n+1 \\ k}+1=\summe_{k=0}^{n+1} \vektor{n+1 \\ k}
[/mm]
[mm] \Box
[/mm]
|
|
|
| |
|
| Status: |
(Frage) beantwortet | | Datum: | 23:00 Do 27.10.2005 | | Autor: | Mira1 |
Der Beweis sieht super aus. ich komme aber leider nur bis zum vierten Schritt mit, also bis zu den zwei Summen.
Warum kannst du dann die Indesverschiebung so machen?
Im nächsten Schritt kann ich nicht nachvollziehen, wo die +1+1 herkommen, und wieso die Indexverschiebung wieder weg ist
Als nächstes komme ich nicht mit wenn die Summen zusammen gefast werden, also: [mm] \summe_{k=1}^{n} \vektor{ \vektor{n\\ k-1} \vektor{n\\ k}} [/mm] zu [mm] \summe_{k=1}^{n} \vektor{n+1\\ k}
[/mm]
und wo verschwinden am Schulß die 1en hin? Kann man so einfach den Index zurück schieben?
|
|
|
| |
|
> Der Beweis sieht super aus. ich komme aber leider nur bis
> zum vierten Schritt mit, also bis zu den zwei Summen.
> Warum kannst du dann die Indesverschiebung so machen?
Hallo,
daß [mm] \summe_{k=0}^{n} \vektor{n \\ k}=\summe_{k=1}^{n+1} \vektor{n \\ k-1} [/mm] ist, siehst Du am schnellsten mit einem Beispiel ein - wie so oft.
Schreib Dir doch mal auf, was [mm] \summe_{k=0}^{5} \vektor{5 \\ k} [/mm] ist. Einfach hinschreiben, nicht die Binominalkoeffizienten ausrechenen. So. Und nun [mm] \summe_{k=1}^{6} \vektor{5 \\ k-1} [/mm] . Und? Klar?
> Im nächsten Schritt kann ich nicht nachvollziehen, wo die
> +1+1 herkommen, und wieso die Indexverschiebung wieder weg
> ist
Hier wird in der ersten Summe statt bis n+1 nur bis n summiert. Damit das Gleichheitszeichen gilt braucht man noch [mm] +\vektor{n \\ (n+1)-1}=1.
[/mm]
Und in der zweiten Summe wird statt ab 0 erst ab 1 summiert, also muß man [mm] \vektor{n \\ 0}=1 [/mm] addieren.
>
> Als nächstes komme ich nicht mit wenn die Summen zusammen
> gefast werden, also: [mm]\summe_{k=1}^{n} \vektor{ \vektor{n\\ k-1} \vektor{n\\ k}}[/mm]
> zu [mm]\summe_{k=1}^{n} \vektor{n+1\\ k}[/mm]
Das wäre nicht zu begreifen, wenn es so dort stünde. ABER es steht [mm]\summe_{k=1}^{n} \vektor{ \vektor{n\\ k-1} + \vektor{n\\ k}}[/mm] . Das ist [mm]\summe_{k=1}^{n} \vektor{n+1\\ k}[/mm], aufgrund des Additionssatzes: [mm] \vektor{a \\ l}+ \vektor{a \\ l+1} =\vektor{a+1 \\ l+1}. [/mm] (Vorlesung, Übung)
>
> und wo verschwinden am Schulß die 1en hin? Kann man so
> einfach den Index zurück schieben?
1= [mm] \vektor{n+1 \\ 0} [/mm] und 1= [mm] \vektor{n+1 \\ n+1} [/mm] und die wandern zum Schluß unter die Fittiche der Summe, denn die Summation läuft nun von 0 bis n+1 statt von 1 bis n.
Mein Tip für den Anfang: solange Dir die Summen noch fremd sind, guck nicht einfach drauf und grübele, sondern schreib sie Dir als Addition mit Pünktchen, zumindest auf Deinem Schmierpapier. Manches erklärt sich dann von selbst. [mm] \summe_{i=1}^{n}a_i=a_1+a_2+a_3+...+a_{n-1}+a_n.
[/mm]
Gruß v. Angela
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig | | Datum: | 17:56 Fr 28.10.2005 | | Autor: | Mira1 |
Vielen Dank für die tolle Induktion und die super Erlärung. Damit war das ganze garnicht mehr so schwer.  Aber alleine wäre ich auf die ganzen Tricks im Leben nicht gekommen!
Vielen Dank!
|
|
|
|
