Induktionsbeweis < Analysis < Hochschule < Mathe < Vorhilfe
|
| Status: |
(Frage) beantwortet  | | Datum: | 10:33 Di 22.02.2005 | | Autor: | baddi |
Hallo ich habe versucht folgenden Formel zu beweisen.
[mm] $\summe_{i=0}^{n}$ $\vektor{n \\ k}$ $=2^n$
[/mm]
Sie war auf unserem Analysis - Übungsblatt.
Ich habe die Induktionsverankerung, natürlich hinbekommen.
Also für n=0 kommt hallt 1 raus. Ok.
Nun meine nächsten Schritte:
n --> n+1
[mm] $\summe_{i=0}^{n+1}$ [/mm] = [mm] $\summe_{i=0}^{n}$$\vektor{n \\ k}$ [/mm] + [mm] $\vektor{n+1 \\ n+1}$
[/mm]
<=> (nach Funktionsverankerung)
[mm] $\summe_{i=0}^{n+1}$ $=2^n$ [/mm] + [mm] $\vektor{n+1 \\ n+1}$
[/mm]
=> Wenn [mm] $\vektor{n+1 \\ n+1}$ [/mm] = [mm] $2^1$ [/mm] wäre die Formel induktiv bewiesen.
Wir wissen:
[mm] $\vektor{n \\ k}$=$\bruch{n!}{k!*(n-k)!}$
[/mm]
[mm] $\vektor{n+1 \\ n+1}$=$\bruch{(n+1)!}{(n+1)!*((n+1)-(n+1))!}$ [/mm] =
[mm] =$\bruch{(n+1)!}{(n+1)!*(0)!}$=$\bruch{(n+1)!}{(n+1)!*1}$ [/mm] = 1
Damit wäre doch wohl gezeigt das die Formel nicht gilt da,
[mm] 1=$1^1$$\not=2^1$
[/mm]
Aber dass kann es doch wohl nicht sein.
Habe ich einen Fehler mit dem Binominialkoeffizient gemacht ?
|
|
| |
|
| Status: |
(Antwort) fertig  | | Datum: | 10:58 Di 22.02.2005 | | Autor: | andreas |
hi
gesetzt den fall ihr habt den binomischen lehrsatz schon davor beweisen kannst du den einfach hernehem und $x=y=1$ setzen und bist fertig, wenn nicht, dann ist induktion schon die richtige idee.
>
> [mm]\summe_{i=0}^{n}[/mm] [mm]\vektor{n \\ k}[/mm] [mm]=2^n[/mm]
>
> Sie war auf unserem Analysis - Übungsblatt.
>
> Ich habe die Induktionsverankerung, natürlich
> hinbekommen.
> Also für n=0 kommt hallt 1 raus. Ok.
>
> Nun meine nächsten Schritte:
> n --> n+1
> [mm]\summe_{i=0}^{n+1}[/mm] = [mm]\summe_{i=0}^{n}[/mm][mm]\vektor{n \\ k}[/mm] +
> [mm]\vektor{n+1 \\ n+1}[/mm]
i.a. gilt [m] \binom{n+1}{k} \not= \binom{n}{k} [/m], also darfst du die summe so nicht aufspalten. was hier hilfreich wäre, ist z.b. die folgende formel (durch direktes ausrechnen) zu beweisen und zu benutzen:
[m] \binom{n+1}{k} = \binom{n}{k-1} + \binom{n}{k} [/m]
für $n, k [mm] \in \mathbb{N}_0, [/mm] k [mm] \leq [/mm] n$ und damit dann den mittleren teil der von dir betrachtete summe [m] \sum_{k=0}^{n+1} \binom{n+1}{k} = \binom{n+1}{0} + \sum_{k=1}^n \binom{n+1}{k} + \binom{n+1}{n+1} [/m] aufzuspalten!
grüße
andreas
|
|
|
| |
|
| Status: |
(Frage) beantwortet | | Datum: | 11:23 Di 22.02.2005 | | Autor: | baddi |
Hallo Andreas (und andere :),
nimm es mir nicht übel aber ich bin wie immer ein Widerporst ;)
und lenke noch nicht ein, weil ich es noch nicht einsehen kann.
Wird sicher wieder peinlich werden für mich.
> gesetzt den fall ihr habt den binomischen lehrsatz
Ich erinnere mich nicht mehr, was dass sein soll. Aber...
> > Nun meine nächsten Schritte:
> > n --> n+1
> > [mm]\summe_{i=0}^{n+1}[/mm] = [mm]\summe_{i=0}^{n}[/mm][mm]\vektor{n \\ k}[/mm] +
> > [mm]\vektor{n+1 \\ n+1}[/mm]
>
> i.a. gilt [m]\binom{n+1}{k} \not= \binom{n}{k} [/m], also darfst
> du die summe so nicht aufspalten.
Halt halt halt haaaallllt ;) moment mal.
Eine Summe ist doch eine Summe eine Summe ;)
Will sagen, Wenn da steht z.B.:
[mm]\summe_{i=0}^{3}[/mm]=[mm]\vektor{3 \\ 0}[/mm]+[mm]\vektor{3 \\ 1}[/mm]+[mm]\vektor{3 \\ 3}[/mm]
Da sind wir einig ?
[mm]\summe_{i=0}^{2}[/mm]=[mm]\vektor{3 \\ 0}[/mm]+[mm]\vektor{3 \\ 1}[/mm]
Da sind wir einig ?
Dann ist doch auch
[mm]\summe_{i=0}^{3}[/mm]=[mm]\summe_{i=0}^{2}[/mm]=+[mm]\vektor{3 \\ 3}[/mm]
Da sind wir einig ?
[mm]\summe_{i=0}^{n+1}[/mm] = [mm]\summe_{i=0}^{n}[/mm][mm]\vektor{n \\ k}[/mm] + [mm]\vektor{(n+1) \\ (n+1)}[/mm]
Warum sind wir uns hier nicht mehr einig ?
:)
|
|
|
| |
|
| Status: |
(Antwort) fertig | | Datum: | 11:39 Di 22.02.2005 | | Autor: | Marcel |
Hallo Baddi!
> Hallo Andreas (und andere :),
> nimm es mir nicht übel aber ich bin wie immer ein
> Widerporst ;)
> und lenke noch nicht ein, weil ich es noch nicht einsehen
> kann.
> Wird sicher wieder peinlich werden für mich.
>
>
> > gesetzt den fall ihr habt den binomischen lehrsatz
> Ich erinnere mich nicht mehr, was dass sein soll. Aber...
>
> > > Nun meine nächsten Schritte:
> > > n --> n+1
> > > [mm]\summe_{i=0}^{n+1}[/mm] = [mm]\summe_{i=0}^{n}[/mm][mm]\vektor{n \\ k}[/mm]
> +
> > > [mm]\vektor{n+1 \\ n+1}[/mm]
> >
> > i.a. gilt [m]\binom{n+1}{k} \not= \binom{n}{k} [/m], also darfst
>
> > du die summe so nicht aufspalten.
Andreas hat vollkommen Recht. Denn:
Gucken wir uns dein Vorgehen nocheinmal an:
> ...
> Nun meine nächsten Schritte:
> n --> n+1
> [mm] $\summe_{i=0}^{n+1}$ [/mm] = [mm] $\summe_{i=0}^{n}$$\vektor{n \\ k}$ [/mm] + [mm] $\vektor{n+1 \\ n+1}$
[/mm]
> <=> (nach Funktionsverankerung)
> [mm] $\summe_{i=0}^{n+1}$ $=2^n$ [/mm] + [mm] $\vektor{n+1 \\ n+1}$
[/mm]
> => Wenn [mm] $\vektor{n+1 \\ n+1}$ [/mm] = [mm] $2^1$ [/mm] wäre die Formel induktiv
> bewiesen.
Der Induktionsschritt ist doch folgendes:
Unter der Induktionsvoraussetzung [mm] $(\star)$[/mm] [m]\summe_{i=0}^{n}{n \choose i}=2^n[/m] hast du zu zeigen, dass dann die Gleichung [mm] $(\star)$ [/mm] auch gilt, wenn man überall das $n$ durch $n+1$ ersetzt.
Du müßtest also ansetzen:
$n [mm] \mapsto [/mm] n+1$:
[m]\summe_{i=0}^{\blue{n+1}}{\blue{n+1} \choose i}=\left(\summe_{i=0}^{n}{\blue{n+1} \choose i}\right)+{n+1 \choose n+1}={n+1 \choose 0}+\left(\summe_{i=1}^{n}{n+1 \choose i}\right)+{n+1 \choose n+1}=\dots[/m]
[Du hattest bei der Summe vergessen, das $n$ innerhalb des Binomialkoeffizienten durch $n+1$ zu ersetzen. Daher habe ich es hier blau geschrieben!]
und jetzt wende den Tipp von Andreas auf den Ausdruck [m]{n+1 \choose i}[/m] an, um dann die Induktionsvoraussetzung anwenden zu können etc..
Viele Grüße,
Macel
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig  | | Datum: | 11:43 Di 22.02.2005 | | Autor: | Marcel |
Hallo Baddi!
So nebenbei:
> > > [mm]\summe_{i=0}^{n+1}[/mm] = [mm]\summe_{i=0}^{n}[/mm][mm]\vektor{n \\ k}[/mm]
> +
> > > [mm]\vektor{n+1 \\ n+1}[/mm]
Das ist natürlich anders gemeint, als es da steht. Du schreibst unter dem Summenzeichen den Laufindex $i$, aber im Binomialkoeffizient $k$. Passe bitte auf, dass du immer die gleiche Variable als Laufindex benutzt! Irgendwie typisch, dass da immer Fehler passieren  .
Viele Grüße,
Marcel
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig | | Datum: | 12:00 Di 22.02.2005 | | Autor: | Marcel |
Hi Baddi!
Auch, wenn ich hoffe, dass du mittlerweile deinen anderer Fehler gesehen hast, muss ich hier auch noch was zu sagen:
> Hallo Andreas (und andere :),
> [mm]\summe_{i=0}^{3}[/mm]=[mm]\vektor{3 \\ 0}[/mm]+[mm]\vektor{3 \\ 1}[/mm]+[mm]\vektor{3 \\ 3}[/mm]
Das wäre:
[mm]\summe_{i=0}^{3}{3 \choose i}={3 \choose 0}+{3 \choose 1}\red{+ {3 \choose 2}}+{3 \choose 3}[/mm]
> Da sind wir einig ?
Nein, s.o.
> [mm]\summe_{i=0}^{2}[/mm]=[mm]\vektor{3 \\ 0}[/mm]+[mm]\vektor{3 \\ 1}[/mm]
> Da sind
> wir einig ?
Nein, auch hier ist ein Fehler. Es ist:
[m]\sum_{i=0}^2{3 \choose i}={3 \choose 0}+{3 \choose 1}\red{+{3 \choose 2}}[/m]
.
.
.
PS: Schreibe doch bitte anstatt:
[mm] $\sum_{i=0}^3$ [/mm] auch das, was du meinst:
[mm] $\sum_{i=0}^3{3 \choose i}$ [/mm]
Entsprechendes an den anderen Stellen...
Viele Grüße,
Marcel
|
|
|
| |
|
| Status: |
(Antwort) fertig | | Datum: | 11:05 Di 22.02.2005 | | Autor: | Marcel |
Hallo Baddi!
> Hallo ich habe versucht folgenden Formel zu beweisen.
>
> [mm]\summe_{i=0}^{n}[/mm] [mm]\vektor{n \\ k}[/mm] [mm]=2^n[/mm]
Über Induktion geht das natürlich auch. Aber rechne doch auch spaßeshalber mal folgendes ($n [mm] \in \IN_{\,0}$):
[/mm]
[m]2^n=(1+1)^n[/m]
Und jetzt wende auf Letzteres mal den  binomischen Lehrsatz an.
Viele Grüße,
Marcel
|
|
|
|
![[bonk]](/images/smileys/bonk.gif "[bonk]"){kind=small}
![[sorry]](/images/smileys/sorry.gif "[sorry]"){kind=small}
, das hatte ich eben wohl überlesen (wollen ![[grins]](/images/smileys/grins.gif "[grins]"){kind=small}
)!
