Vollständige Induktion < Induktion < eindimensional < reell < Analysis < Hochschule < Mathe < Vorhilfe
|
| Status: |
(Frage) beantwortet  | | Datum: | 22:09 Fr 19.10.2007 | | Autor: | Tyskie84 |
Hi hab ein kleines Problem bei einem Induktionsbeweis:
Beweise [mm] \summe_{k=0}^{n}k*\vektor{n \\ k}=n [/mm] * [mm] 2^{n-1}
[/mm]
Mein Induktionschritt ist folgender:
[mm] \summe_{k=0}^{n+1}k*\vektor{n+1 \\ k}=(n+1)*2^{n}
[/mm]
[mm] =\summe_{k=0}^{n}k*\vektor{n \\ k}+(n+1)*\vektor{n \\ n+1}
[/mm]
so und ab hier komm ich nicht weiter da [mm] \vektor{n \\ n+1} [/mm] ja = 0 ist!!!!
Kann mir hier jemand weiterhelfen???
Ich habe diese Frage in keinem Forum auf anderen Internetseiten gestellt
|
|
| |
|
> Hi hab ein kleines Problem bei einem Induktionsbeweis:
>
> Beweise [mm]\summe_{k=0}^{n} k*\vektor{n \\ k}[/mm] = n * 2^(n-1)
>
> Mein Induktionschritt ist folgender:
>
> [mm]\summe_{k=0}^{n+1} k*\vektor{n+1 \\ k}=[/mm] (n+1)*2^(n)
Hallo,
![[willkommenmr]](/images/smileys/willkommenmr.png "[willkommenmr]") .
> [mm]\summe_{k=0}^{n+1} k*\vektor{n+1 \\ k}=[/mm] (n+1)*2^(n)
ist das, was im Induktionsschritt zu zeigen ist.
Du mußt nun mit [mm] \summe_{k=0}^{n+1} k*\vektor{n+1 \\ k} [/mm] starten und das so lange und richtig umformen, bis Du am Ende [mm] (n+1)*2^n [/mm] erhältst.
> [mm]=\summe_{k=0}^{n} k*\vektor{n \\ k}[/mm] + [mm](n+1)*\vektor{n \\ n+1}[/mm]
Das stimmt nicht.
Schau:
[mm] \summe_{k=0}^{n+1} k*\vektor{n+1 \\ k}
[/mm]
[mm] =\summe_{k=0}^{n} k*\vektor{n+1 \\ k} [/mm] + [mm] (n+1)*\vektor{n+1 \\ n+1}
[/mm]
Es ist ja k der Summationsindes. Wenn Du nun nur bis k=n summierst, mußt Du noch den Summanden, in welchem k=n+1 ist, addieren.
Gruß v. Angela
|
|
|
| |
|
| Status: |
(Frage) beantwortet | | Datum: | 22:43 Fr 19.10.2007 | | Autor: | Tyskie84 |
Also ich habe [mm] \summe_{k=1}^{n+1}k*\vektor{n+1 \\k}=
[/mm]
[mm] \summe_{k=0}^{n+1}k*\vektor{n \\ k}+\vektor{n \\ k-1}=
[/mm]
[mm] \summe_{k=0}^{n}*\vektor{n-1 \\ k}+\vektor{n \\ k-1}+(n+1)*\vektor{n-1 \\ n+1}+\vektor{n \\ n} [/mm] so und hier komme ich nicht weiter...
[mm] \vektor{n \\ n} [/mm] ist ja 1 und [mm] \vektor{n-1 \\ n+1} [/mm] ist ja n*(n+1) aber ich komm nicht auf [mm] (n+1)*2^n
[/mm]
|
|
|
| |
|
| Status: |
(Antwort) fertig  | | Datum: | 01:09 Sa 20.10.2007 | | Autor: | leduart |
Hallo
Was du hier schreibst ist viel falscher (wenn es sowas gibt) als was du vorher hattest.
Angela hatte dier doch die Verbesserung zu deinem ersten Versuch geschrieben:
> Also ich habe [mm]\summe_{k=1}^{n+1}k*\vektor{n+1 \\k}=[/mm]
>
> [mm]\summe_{k=0}^{n+1}k*\vektor{n \\ k}+\vektor{n \\ k-1}=[/mm]
wo kommt denn das k-1 her?
[mm]\summe_{k=1}^{n+1}k*\vektor{n+1 \\k}=\summe_{k=1}^{n}k*\vektor{n \\k}+(n+1)*\vektor{n+1 \\n+1}[/mm]
jetzt für den ersten Teil die Induktionsvors einsetzen.
Gruss leduart
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig  | | Datum: | 22:30 Fr 19.10.2007 | | Autor: | koepper |
Hallo,
nur ein kleiner Tipp:
Es geht einfach und schnell ohne Induktion.
Schreibe 2 als (1 + 1) und wende den binomischen Lehrsatz an.
Gruß und gute N8
Will
|
|
|
| |
|
ich hab das mal verfolgt und komm irgendwie nicht weiter.
[mm] \sum_{k=0}^{n}{ k *{n \choose k}} [/mm]
von n auf n+1 gefolgert ergibt sich
[mm] \sum_{k=0}^{n+1}{ k *{n+1 \choose k}} =\sum_{k=0}^{n}{ k *{n+1 \choose k}} [/mm] + (n+1)
/br
[mm] ={\sum_{k=0}^{n} k*[{n \choose k}+{n \choose k-1}]} [/mm] + n+1
/br
[mm] ={\sum_{k=0}^{n} k*{n \choose k}}+{\sum_{k=0}^{n} k*{n \choose k-1}} [/mm] + n+1
= [mm] n*2^{n-1} [/mm] + [mm] {\sum_{k=0}^{n} k*{n \choose k-1}} [/mm] + n+1
[mm] =n*2^{n-1} [/mm] + [mm] {\sum_{k=1}^{n} k*{n \choose k-1}} [/mm] + n+1
[mm] =n*2^{n-1} [/mm] + [mm] {\sum_{k=0}^{n-1} {(k+1)}*{n \choose k}} [/mm] + n+1
[mm] =n*2^{n-1} [/mm] + [mm] {\sum_{k=0}^{n} {(k+1)}*{n \choose k}} [/mm]
= [mm] {\sum_{k=0}^{n} {n \choose k}*{(k+k+1)}}
[/mm]
= [mm] {\sum_{k=0}^{n} {n \choose k}*{(2k+1)}}
[/mm]
hmm und da ist schluß.
die letzten 2 umformungen scheinen mir eher sinnlos...und ich krieg die summe nicht weg.
welche formel übersehe ich denn da..
das nervt mich, seitdem ich das gesehen hab.
|
|
|
| |
|
| Status: |
(Antwort) fertig | | Datum: | 22:06 Fr 26.10.2007 | | Autor: | koepper |
Hallo,
für Beweise gilt die Regel: je kürzer und einfacher desto besser:
$n * [mm] 2^{n-1} [/mm] = n * (1 + [mm] 1)^{n-1} [/mm] = n * [mm] \sum_{k = 0}^{n - 1} [/mm] {n - 1 [mm] \choose [/mm] k} = [mm] \sum_{k = 1}^{n} [/mm] n * {n - 1 [mm] \choose [/mm] k - 1} = [mm] \sum_{k = 1}^{n} [/mm] k * {n [mm] \choose [/mm] k} = [mm] \sum_{k = 0}^{n} [/mm] k * {n [mm] \choose [/mm] k}$
Denn $n * {n - 1 [mm] \choose [/mm] k - 1} = k * {n [mm] \choose [/mm] k}$, wie man leicht nachrechnet.
Gruß
Will
|
|
|
| |
|
| Status: |
(Frage) beantwortet | | Datum: | 21:19 So 28.10.2007 | | Autor: | cloui |
ich hab mal ne frage, wieso ist
[mm] \sum_{k = 1}^{n}k*\vektor{n\\k}=\sum_{k = 0}^{n}k*\vektor{n\\k} [/mm] ???
|
|
|
| |
|
| Status: |
(Antwort) fertig | | Datum: | 21:26 So 28.10.2007 | | Autor: | Loddar |
Hallo cloui!
[mm] $$\sum_{k = 0}^{n}k*\vektor{n\\k} [/mm] \ = \ [mm] \sum_{k = 0}^{0}k*\vektor{n\\k}+\sum_{k = 1}^{n}k*\vektor{n\\k} [/mm] \ = \ [mm] \underbrace{0*\vektor{n\\0}}_{= \ 0*1 \ = \ 0}+\sum_{k = 1}^{n}k*\vektor{n\\k} [/mm] \ = \ [mm] \sum_{k = 1}^{n}k*\vektor{n\\k}$$
[/mm]
Gruß
Loddar
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig | | Datum: | 21:34 So 28.10.2007 | | Autor: | cloui |
ah ok ich verstehe :) vielen dank
|
|
|
| |
|
| Status: |
(Frage) beantwortet | | Datum: | 21:55 So 28.10.2007 | | Autor: | cloui |
jetzt muss ich nochmal nerven :)
kannst du vllt den rechenweg aufschreiben wie man darauf kommt
$ n [mm] \cdot{} [/mm] {n - 1 [mm] \choose [/mm] k - 1} = k [mm] \cdot{} [/mm] {n [mm] \choose [/mm] k} $, ?
|
|
|
| |
|
| Status: |
(Antwort) fertig | | Datum: | 21:57 So 28.10.2007 | | Autor: | Loddar |
Hallo cloui!
Sieh mal diese Antwort. Das funktioniert hier dann analog ...
Gruß
Loddar
|
|
|
| |
|
> ich hab das mal verfolgt und komm irgendwie nicht weiter.
> [mm]\sum_{k=0}^{n}{ k *{n \choose k}}[/mm]
> von n auf n+1 gefolgert ergibt sich
> [mm]\sum_{k=0}^{n+1}{ k *{n+1 \choose k}} =\sum_{k=0}^{n}{ k *{n+1 \choose k}}[/mm]
> + (n+1)
> /br
> [mm]={\sum_{k=0}^{n} k*[{n \choose k}+{n \choose k-1}]}[/mm] + n+1
> /br
> [mm]={\sum_{k=0}^{n} k*{n \choose k}}+{\sum_{k=0}^{n} k*{n \choose k-1}}[/mm]
> + n+1
>
> = [mm]n*2^{n-1}[/mm] + [mm]{\sum_{k=0}^{n} k*{n \choose k-1}}[/mm] + n+1
>
> [mm]=n*2^{n-1}[/mm] + [mm]{\sum_{k=1}^{n} k*{n \choose k-1}}[/mm] + n+1
>
> [mm]=n*2^{n-1}[/mm] + [mm]{\sum_{k=0}^{n-1} {(k+1)}*{n \choose k}}[/mm] +
> n+1
>
> [mm]=n*2^{n-1} + {\sum_{k=0}^{n} {(k+1)}*{n \choose k}}[/mm]
[mm]=n*2^{n-1} + \sum_{k=0}^{n} k*{n \choose k} + \sum_{k=0}^{n} {n \choose k}[/mm]
kommst nun alleine weiter? 
PS: [mm]\sum_{k=0}^{n} {n \choose k} = 2^n[/mm]
|
|
|
|
