Induktionsbeweis < Induktion < eindimensional < reell < Analysis < Hochschule < Mathe < Vorhilfe
|
| Aufgabe | Zeigen Sie mittels vollständiger Induktion, dass
[mm] \summe_{l=1}^{n-1}l \vektor{n-1 \\ l}=(n-1)*2^{n-2}
[/mm]
Hinweis: Verwenden Sie das Binomialgesetz [mm] \vektor{n \\ k} [/mm] = [mm] \vektor{n-1 \\ k-1}+\vektor{n-1 \\ k}. [/mm] |
Hallo zusammen,
Ich habe die Umformung bei der Induktion leider nicht komplett hinbekommen? Hat jemand von euch vielleicht einen Hinweis? Mein Lösung sieht bis dato wie folgt aus:
Beh: Es gilt
[mm] \summe_{l=1}^{n-1}l \vektor{n-1 \\ l}=(n-1)*2^{n-2}.
[/mm]
Beweis per Induktion über n:
I.A:
Sei n=1, dann gilt:
[mm] \summe_{l=1}^{n-1}l \vektor{n-1 \\ l} [/mm] = [mm] \summe_{l=1}^{1-1}l \vektor{1-1 \\ l} [/mm] = 0 = [mm] (1-1)*2^{1-2} [/mm] = [mm] (n-1)*2^{n-2}.
[/mm]
I.S:
Es gelte [mm] \summe_{l=1}^{n-1}l \vektor{n-1 \\ l}=(n-1)*2^{n-2}. [/mm] Dann gilt:
[mm] \summe_{l=1}^{(n+1)-1}l \vektor{(n+1)-1 \\ l} [/mm] = [mm] \summe_{l=1}^{(n+1)-1}l(\vektor{n-1 \\ l-1}+\vektor{n-1 \\ l})=[IV] (n-1)*2^{n-2}+l\vektor{n-1 \\ l}=(n-1)*2^{n-2}+l*\bruch{(n-1)!}{l!*((n-1)-l)!}=(n-1)*2^{n-2}+\bruch{l*(n-1)!}{l!*((n-1)-l)!}=(n-1)*2^{n-2}+\bruch{(n-1)!}{(l-1)!*((n-1)-l)!}
[/mm]
=...
[mm] =n*2^{n-1}=((n+1)-1)*2^{(n+1)}-2
[/mm]
Vielen Dank!
Ich habe diese Frage in keinem Forum auf anderen Internetseiten gestellt.
|
|
| |
|
| Status: |
(Antwort) fertig  | | Datum: | 02:11 Di 03.11.2015 | | Autor: | DieAcht |
Hallo JohnDoe123!
![[willkommenmr]](/images/smileys/willkommenmr.png "[willkommenmr]")
> Zeigen Sie mittels vollständiger Induktion, dass
> [mm]\summe_{l=1}^{n-1}l \vektor{n-1 \\ l}=(n-1)*2^{n-2}[/mm]
für alle [mm] $n\in\IN$.
[/mm]
> Hinweis: Verwenden Sie das Binomialgesetz [mm]\vektor{n \\ k}[/mm] =
> [mm]\vektor{n-1 \\ k-1}+\vektor{n-1 \\ k}.[/mm]
> Hallo zusammen,
>
> Ich habe die Umformung bei der Induktion leider nicht
> komplett hinbekommen? Hat jemand von euch vielleicht einen
> Hinweis? Mein Lösung sieht bis dato wie folgt aus:
>
> Beh: Es gilt
>
> [mm]\summe_{l=1}^{n-1}l \vektor{n-1 \\ l}=(n-1)*2^{n-2}.[/mm]
für alle [mm] $n\in\IN$.
[/mm]
> Beweis per Induktion über n:
> I.A:
> Sei n=1, dann gilt:
>
> [mm]\summe_{l=1}^{n-1}l \vektor{n-1 \\ l}[/mm] = [mm]\summe_{l=1}^{1-1}l \vektor{1-1 \\ l}[/mm]
> = 0 = [mm](1-1)*2^{1-2}[/mm] = [mm](n-1)*2^{n-2}.[/mm]
Wie habt ihr die Summe
[mm] $\sum_{k=l}^{m}a_k$
[/mm]
für [mm] $l>m\$ [/mm] definiert?
Eine Möglichkeit:
Die Summe
[mm] $\sum_{k=l}^{m}a_k$
[/mm]
ist eine Kurzschreibweise für
[mm] $\sum_{k\in I}a_k$
[/mm]
mit
[mm] $I:=\{z\in\IZ\mid l\le z\le m\}$.
[/mm]
Für [mm] $I=\emptyset$ [/mm] definieren wir
[mm] $\sum_{k\in I}a_k=\sum_{k\in\emptyset}a_k=0$.
[/mm]
Jetzt wieder du!
> I.S:
> Es gelte [mm]\summe_{l=1}^{n-1}l \vektor{n-1 \\ l}=(n-1)*2^{n-2}.[/mm]
für ein beliebiges [mm] $n\in\IN$.
[/mm]
> Dann gilt:
>
> [mm]\summe_{l=1}^{(n+1)-1}l \vektor{(n+1)-1 \\ l}[/mm] =
> [mm]\summe_{l=1}^{(n+1)-1}l(\vektor{n-1 \\ l-1}+\vektor{n-1 \\ l})=[IV] (n-1)*2^{n-2}+l\vektor{n-1 \\ l}[/mm]
Das ist leider (in vieler Hinsicht) Quark!
Zu zeigen:
[mm] $\sum_{l=1}^{n}l*\binom{n}{l}=n\cdot{}2^{n-1}$.
[/mm]
Beweis:
[mm] $\sum_{l=1}^{n}l*\binom{n}{l}$
[/mm]
[mm] $\overset{\text{Hinweis}}{=}\sum_{l=1}^{n}l*\left(\binom{n-1}{l-1}+\binom{n-1}{l}\right)=\sum_{l=1}^{n}l*\binom{n-1}{l-1}+\sum_{l=1}^{n}l*\binom{n-1}{l}$
[/mm]
[mm] $\overset{\text{Indexshift}}{=}\sum_{l=0}^{n-1}\left((l+1)*\binom{n-1}{l}\right)+\sum_{l=0}^{n-1}l*\binom{n-1}{l}=2*\sum_{l=0}^{n-1}l*\binom{n-1}{l}+\sum_{l=0}^{n-1}\binom{n-1}{l}$
[/mm]
[mm] $\overset{\text{IV}}{=}2*(n-1)*2^{n-2}+2^{n-1}=n*2^{n-1}$.
[/mm]
Möglicherweise fehlt dabei der Nachweis von
[mm] $\sum_{k=0}^{n}\binom{n}{k}=2^n$ [/mm] für alle [mm] $n\in\IN_0$.
[/mm]
Die letzte Aussage kann (auch) induktiv (über [mm] $n\$) [/mm] gezeigt werden.
Alternativ (Binomischen Lehrsatz):
[mm] $2^n=(1+1)^n=\sum_{k=0}^{n}\binom{n}{k}$.
[/mm]
Gruß
DieAcht
|
|
|
| |
|
> Hallo JohnDoe123!
>
>
Vielen Dank!
>
>
> > Zeigen Sie mittels vollständiger Induktion, dass
> > [mm]\summe_{l=1}^{n-1}l \vektor{n-1 \\ l}=(n-1)*2^{n-2}[/mm]
>
> für alle [mm]n\in\IN[/mm].
>
> > Hinweis: Verwenden Sie das Binomialgesetz [mm]\vektor{n \\ k}[/mm] =
> > [mm]\vektor{n-1 \\ k-1}+\vektor{n-1 \\ k}.[/mm]
> > Hallo
> zusammen,
> >
> > Ich habe die Umformung bei der Induktion leider nicht
> > komplett hinbekommen? Hat jemand von euch vielleicht einen
> > Hinweis? Mein Lösung sieht bis dato wie folgt aus:
> >
> > Beh: Es gilt
> >
> > [mm]\summe_{l=1}^{n-1}l \vektor{n-1 \\ l}=(n-1)*2^{n-2}.[/mm]
>
> für alle [mm]n\in\IN[/mm].
>
> > Beweis per Induktion über n:
> > I.A:
> > Sei n=1, dann gilt:
> >
> > [mm]\summe_{l=1}^{n-1}l \vektor{n-1 \\ l}[/mm] = [mm]\summe_{l=1}^{1-1}l \vektor{1-1 \\ l}[/mm]
> > = 0 = [mm](1-1)*2^{1-2}[/mm] = [mm](n-1)*2^{n-2}.[/mm]
>
> Wie habt ihr die Summe
>
> [mm]\sum_{k=l}^{m}a_k[/mm]
>
> für [mm]l>m\[/mm] definiert?
>
> Eine Möglichkeit:
>
> Die Summe
>
> [mm]\sum_{k=l}^{m}a_k[/mm]
>
> ist eine Kurzschreibweise für
>
> [mm]\sum_{k\in I}a_k[/mm]
>
> mit
>
> [mm]I:=\{z\in\IZ\mid l\le z\le m\}[/mm].
>
> Für [mm]I=\emptyset[/mm] definieren wir
>
> [mm]\sum_{k\in I}a_k=\sum_{k\in\emptyset}a_k=0[/mm].
Wir haben vorher leider nix definiert, es handelt sich nicht um eine Mathe Vorlesung, sondern um eine über Algorithmen in der scheinbar alles vorausgesetzt wird. In früheren Vorlesungen wurde aber eine Summe, bei der l>n ist als 0 definiert.
>
> Jetzt wieder du!
>
> > I.S:
> > Es gelte [mm]\summe_{l=1}^{n-1}l \vektor{n-1 \\ l}=(n-1)*2^{n-2}.[/mm]
>
> für ein beliebiges [mm]n\in\IN[/mm].
>
> > Dann gilt:
> >
> > [mm]\summe_{l=1}^{(n+1)-1}l \vektor{(n+1)-1 \\ l}[/mm] =
> > [mm]\summe_{l=1}^{(n+1)-1}l(\vektor{n-1 \\ l-1}+\vektor{n-1 \\ l})=[IV] (n-1)*2^{n-2}+l\vektor{n-1 \\ l}[/mm]
>
> Das ist leider (in vieler Hinsicht) Quark!
>
> Zu zeigen:
>
> [mm]\sum_{l=1}^{n}l*\binom{n}{l}=n\cdot{}2^{n-1}[/mm].
>
> Beweis:
>
> [mm]\sum_{l=1}^{n}l*\binom{n}{l}[/mm]
>
> [mm]\overset{\text{Hinweis}}{=}\sum_{l=1}^{n}l*\left(\binom{n-1}{l-1}+\binom{n-1}{l}\right)=\sum_{l=1}^{n}l*\binom{n-1}{l-1}+\sum_{l=1}^{n}l*\binom{n-1}{l}[/mm]
>
> [mm]\overset{\text{Indexshift}}{=}\sum_{l=0}^{n-1}\left((l+1)*\binom{n-1}{l}\right)+\sum_{l=0}^{n-1}l*\binom{n-1}{l}=2*\sum_{l=0}^{n-1}l*\binom{n-1}{l}+\sum_{l=0}^{n-1}\binom{n-1}{l}[/mm]
>
Ich kann leider noch nicht nachvollziehen, wie du das ( +1) aus dem Binom "herausgezogen" hast. Magst du das bitte noch einmal erklären?
> [mm]\overset{\text{IV}}{=}2*(n-1)*2^{n-2}+2^{n-1}=n*2^{n-1}[/mm].
Die IV war ja [mm]\summe_{l=1}^{n-1}l* \vektor{n-1 \\ l}=(n-1)*2^{n-2}.[/mm] Aber das ist doch nicht das selbe wie [mm]\summe_{l=0}^{n-1}l* \vektor{n-1 \\ l}=(n-1)*2^{n-2}.[/mm] oder überseh ich da was?
>
> Möglicherweise fehlt dabei der Nachweis von
>
> [mm]\sum_{k=0}^{n}\binom{n}{k}=2^n[/mm] für alle [mm]n\in\IN_0[/mm].
>
> Die letzte Aussage kann (auch) induktiv (über [mm]n\[/mm]) gezeigt
> werden.
>
> Alternativ (Binomischen Lehrsatz):
>
> [mm]2^n=(1+1)^n=\sum_{k=0}^{n}\binom{n}{k}[/mm].
Wenn wir das Binomialgesetz ohne Beweis nutzen dürfen geh ich davon aus, das der Binomische Lehrsatz auch genutzt werden darf.
>
>
> Gruß
> DieAcht
Vielen Dank schonmal, und lieben Gruß!
|
|
|
| |
|
| Status: |
(Antwort) fertig | | Datum: | 20:09 Di 03.11.2015 | | Autor: | DieAcht |
> > Zu zeigen:
> >
> > [mm]\sum_{l=1}^{n}l*\binom{n}{l}=n\cdot{}2^{n-1}[/mm].
> >
> > Beweis:
> >
> > [mm]\sum_{l=1}^{n}l*\binom{n}{l}[/mm]
> >
> >
> [mm]\overset{\text{Hinweis}}{=}\sum_{l=1}^{n}l*\left(\binom{n-1}{l-1}+\binom{n-1}{l}\right)=\sum_{l=1}^{n}l*\binom{n-1}{l-1}+\sum_{l=1}^{n}l*\binom{n-1}{l}[/mm]
> >
> >
> [mm]\overset{\text{Indexshift}}{=}\sum_{l=0}^{n-1}\left((l+1)*\binom{n-1}{l}\right)+\sum_{l=0}^{n-1}l*\binom{n-1}{l}=2*\sum_{l=0}^{n-1}l*\binom{n-1}{l}+\sum_{l=0}^{n-1}\binom{n-1}{l}[/mm]
> >
> Ich kann leider noch nicht nachvollziehen, wie du das ( +1)
> aus dem Binom "herausgezogen" hast. Magst du das bitte noch
> einmal erklären?
Gerne.
Wir setzen
[mm] $a_l=l*\binom{n-1}{l-1}$ [/mm] für alle [mm] $l\in\IN$.
[/mm]
(Was ist [mm] $a_{l+1}$?)
[/mm]
Wir wollen zeigen, dass
[mm] $\sum_{l=1}^{n}a_l=\sum_{l=0}^{n-1}a_{l+1}$.
[/mm]
gilt.
In der Tat gilt
[mm] $\sum_{l=1}^{n}a_l=a_1+\ldots+a_n$
[/mm]
und
[mm] $\sum_{l=0}^{n-1}a_{l+1}=a_{0+1}+\ldots+a_{n-1+1}=a_1+\ldots+a_n$,
[/mm]
so dass die Behauptung folgt.
Im Grunde ist das ein Indexshift
[mm] $\sum_{l=1}^{n}a_l=\sum_{l=1+m}^{n+m}a_{l-m}$
[/mm]
mit $m:=-1$.
> > [mm]\overset{\text{IV}}{=}2*(n-1)*2^{n-2}+2^{n-1}=n*2^{n-1}[/mm].
> Die IV war ja [mm]\summe_{l=1}^{n-1}l* \vektor{n-1 \\ l}=(n-1)*2^{n-2}.[/mm]
> Aber das ist doch nicht das selbe wie [mm]\summe_{l=0}^{n-1}l* \vektor{n-1 \\ l}=(n-1)*2^{n-2}.[/mm]
> oder überseh ich da was?
Berechne [mm] $l*\binom{n-1}{l}\$ [/mm] für [mm] $l=0\$. [/mm] 
Übrigens: Wir haben (für die rechte Summe beim Indexshift) verwendet, dass
[mm] $\sum_{l=1}^{n}l*\binom{n-1}{l}=\sum_{l=0}^{n-1}l*\binom{n-1}{l}$
[/mm]
gilt.
Für letzteres berechne [mm] $l*\binom{n-1}{l}\$ [/mm] für [mm] $l=n\$ [/mm] durch
[mm] $\binom{n}{k}=\produkt_{j=1}^{k}\frac{n+1-j}{j}$.
[/mm]
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig  | | Datum: | 22:14 Di 03.11.2015 | | Autor: | JohnDoe123 |
Danke Dir für die Mühe, ich habs verstanden :)
|
|
|
|
