Beweis von Behauptungen < Induktion < eindimensional < reell < Analysis < Hochschule < Mathe < Vorhilfe
|
| Aufgabe | Beweisen Sie per vollständiger Induktion die folgenden Behauptungen.
(a) Für jede natürliche Zahl n [mm] \ge [/mm] 2 gilt [mm] \sum_{i=1}^{n} \frac{1}{(n-1)*n}=1-\frac{1}{n}.
[/mm]
(b) Steht [mm] F_t [/mm] für die i-te Fibonacci-Zahl, so gibt es für alle [mm] n\in \mathbb{N}:\sum_{i=1}^{n}F_i=F_{n+2}-1
[/mm]
(*) Für alle [mm] n\in \mathbb{N} [/mm] gilt [mm] \sum_{i=1}{n} i^2=\frac{n(n+1)(2n+1)}{6}. [/mm] |
Hallo Leute,
im Fach 'Algorithmen' wird vollständige Induktion als Wissen vorausgesetzt und ich bin etwas unerfahren damit. Vielleicht könnt ihr mir weiterhelfen.
Mein Lösungsweg:
(a)
Ich vermutete der Induktionsanfang beginnt bei entsprechend bei n=2.
Induktionsanfang n=2
[mm] \sum_{i=1}^{2} \frac{1}{(n-1)*n}=?+ \frac{1}{2}
[/mm]
Das Fragezeichen deshalb, weil für n=1 doch ein ungültiges [mm] \frac{1}{0} [/mm] entstehen würde ?
Bei mir steht ja als Anfang der Reihe ein i=1, aber das kommt doch gar nicht in der Reihe vor? Muss ich vielleicht nur zwei Mal n=2 benutzen??
Vielen Dank im Voraus!
|
|
| |
|
Hallo.
Ich schreibe vom Mobiltelefon und kann leider nicht zitieren ...
Du vermutest richtig, dass der IA bei n=2 liegt.
In der Aufgabenstellung steckt bereits ein Fehler. Der Laufindex an der Summe ist i,in der Summe steht etwas völlig unabhängig von i. Es wird also n-mal der konstante Term [mm] $\frac [/mm] {1}{n (n-1)} $ addiert, was 1/(n-1) ergäbe.
Richtig: für alle $ [mm] n\in \|N, [/mm] n [mm] \ge [/mm] 2$ gilt: [mm] $\sum\limits_{i=1}^n \frac [/mm] {1}{i (i-1)}=1-1/n $
Im IA setze alle n auf 2. Rechterhand muss also 1-1/2 stehen
Gruß
schachuzipus
|
|
|
| |
|
Hey,
vielen Dank für die Antwort.
Der Aufgabensteller macht gerne mal Fehler und ich vermute das ist auch gemeint.
Dennoch verstehe ich es auch bei
$ [mm] \sum\limits_{i=1}^n \frac [/mm] {1}{i (i-1)} $ nicht wie man bei einem Induktionsanfang von n=2 überhaupt etwas angeben kann?
Für i=1 kann ich doch gar nichts hinschreiben, weil doch [mm] \frac{1}{0} [/mm] entsteht?
Vielen Dank!
|
|
|
| |
|
| Status: |
(Antwort) fertig  | | Datum: | 21:07 So 24.11.2013 | | Autor: | DieAcht |
Hallo,
> Hey,
> vielen Dank für die Antwort.
>
> Der Aufgabensteller macht gerne mal Fehler und ich vermute
> das ist auch gemeint.
> Dennoch verstehe ich es auch bei
> [mm]\sum\limits_{i=1}^n \frac {1}{i (i-1)}[/mm] nicht wie man bei
> einem Induktionsanfang von n=2 überhaupt etwas angeben
> kann?
Genau! Guck nochmal nach wo der Laufindex anfängt!
Was soll eigentlich unter der Aufgabe b) dieses (*) sein und wo gehört es hin?
>
> Für i=1 kann ich doch gar nichts hinschreiben, weil doch
> [mm]\frac{1}{0}[/mm] entsteht?
>
> Vielen Dank!
Gruß
DieAcht
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig  | | Datum: | 21:05 So 24.11.2013 | | Autor: | DieAcht |
Hallo,
> Richtig: für alle [mm]n\in \|N, n \ge 2[/mm] gilt:
> [mm]\sum\limits_{i=1}^n \frac {1}{i (i-1)}=1-1/n[/mm]
Auch dann haben wir ein Problem, denn für $n=2$ starten wir trotzdem mit $i=1$ und damit erhalten für das erste Glied immer [mm] \frac{1}{1(1-1)}.
[/mm]
Gruß
DieAcht
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig | | Datum: | 21:11 So 24.11.2013 | | Autor: | mtr-studi |
Ich darf das Foto anscheinend nicht hochladen.
Auf jeden Fall steht das ganz genau so explizit in der Aufgabe.
Kann man den beim Aufgabenteil (b) irgendwas machen? :-/
Zu dem Stern:
Ich dachte zuerst das wäre eine Anmerkung, aber es ist nur eine Zusatzaufgabe.
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig | | Datum: | 21:38 So 24.11.2013 | | Autor: | DieAcht |
Lade das Bild irgendwo anders hoch.
www.fotos-hochladen.net zum Beispiel..
Gruß
DieAcht
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig | | Datum: | 22:36 So 24.11.2013 | | Autor: | mtr-studi |
http://s14.directupload.net/images/131124/q45uh26p.jpg
|
|
|
| |
|
| Status: |
(Korrektur) kleiner Fehler  | | Datum: | 00:17 Mo 25.11.2013 | | Autor: | Marcel |
Hallo Schachu,
ist jetzt nicht wirklich direkt Dein Fehler, aber:
> Hallo.
>
> Ich schreibe vom Mobiltelefon und kann leider nicht
> zitieren ...
>
> Du vermutest richtig, dass der IA bei n=2 liegt.
>
>
> In der Aufgabenstellung steckt bereits ein Fehler. Der
> Laufindex an der Summe ist i,in der Summe steht etwas
> völlig unabhängig von i. Es wird also n-mal der konstante
> Term [mm]\frac {1}{n (n-1)}[/mm] addiert, was 1/(n-1) ergäbe.
>
> Richtig: für alle [mm]n\in \|N, n \ge 2[/mm] gilt:
> [mm]\sum\limits_{i=1}^n \frac {1}{i (i-1)}=1-1/n[/mm]
das kann auch nicht richtig sein:
[mm] $\sum_{i=1}^n \frac{1}{i*(i-1)}=\frac{1}{\red{1*0}}+...=\frac{1}{\red{0}}+...$
[/mm]
Gruß,
Marcel
|
|
|
| |
|
Jo,
ich schreibe nie wieder vom Handy. Keine Vorschau, kein Zitat, kein Schmierblatt ...
Danke fürs Aufpassen!
Gruß
schachuzipus
|
|
|
| |
|
| Status: |
(Antwort) fertig | | Datum: | 00:05 Mo 25.11.2013 | | Autor: | DieAcht |
Hallo,
ich beziehe mich nun auf diesen, von dir, hochgeladenen Link: http://s14.directupload.net/images/131124/q45uh26p.jpg
zu a)
Macht keinen Sinn. Frag nochmal den Übungsleiter!
Da ich nicht weiß, ob du Induktion verstanden hast würde ich vorschlagen, dass du zunächst die Zusatzaufgabe machst.
Übrigens hast du diese im Startpost falsch geschrieben.
zu b)
Zu zeigen: Für alle [mm] n\in\IN [/mm] gilt: [mm] \summe_{i=1}^{n}i^2=\frac{n(n+1)(2n+1)}{6}
[/mm]
Induktionsanfang:
Für $n=1$ gilt: [mm] \summe_{i=1}^{1}i^2=1^2=1=\frac{6}{6}=\frac{1(1+1)(2\cdot 1+1)}{6}
[/mm]
Induktionsvorraussetzung:
Es gelte für ein beliebiges, aber festes [mm] n\in\IN, [/mm] die Behauptung - [mm] \summe_{i=1}^{n}i^2=\frac{n(n+1)(2n+1)}{6}
[/mm]
Induktionsschritt:
Für [mm] n\longrightarrow [/mm] $n+1$ gilt:
[mm] \summe_{i=1}^{n+1}i^2=(\summe_{i=1}^{n}i^2)+(n+1)^2=
[/mm]
Ist dir das soweit klar? Nun folgt mit der Induktionsvorraussetzung:
[mm] =(\summe_{i=1}^{n}i^2)+(n+1)^2=\frac{n(n+1)(2n+1)}{6}+(n+1)^2=
[/mm]
Jetzt musst du nur noch die Pünktchen ausfüllen:
[mm] =\frac{n(n+1)(2n+1)}{6}+(n+1)^2=\ldots=\frac{(n+1)(n+2)(2(n+1)+1)}{6}.
[/mm]
Damit hast du dann gezeigt, dass die Behauptung - [mm] \summe_{i=1}^{n}i^2=\frac{n(n+1)(2n+1)}{6} [/mm] - auch für $n:=n+1$ gilt und bist fertig.
Jetzt du!
Wenn du das verstanden hast, kannst du ja mal alleine probieren folgendes zu beweisen:
Für alle [mm] n\in\IN [/mm] gilt: [mm] \summe_{i=1}^{n}i=\frac{n(n+1)}{2}
[/mm]
zu c)
Die Fibonacci-Folge ist wie folgt rekursiv definiert:
[mm] f_0:=0
[/mm]
[mm] f_1:=1
[/mm]
[mm] f_n:=f_{n-1}+f_{n-2}
[/mm]
Probiere nun selbst nach dem Muster von oben das ganze zu durchschauen und zu beweisen.
Viel Spaß!
Gruß
DieAcht
|
|
|
| |
|
Hey, vielen Dank für die Antwort!
> Hallo,
>
> ich beziehe mich nun auf diesen, von dir, hochgeladenen
> Link:
> http://s14.directupload.net/images/131124/q45uh26p.jpg
>
> zu a)
> Macht keinen Sinn. Frag nochmal den Übungsleiter!
Ja, das habe ich heute gemacht und die Vermutungen waren auch richtig. Es waren direkt 2 Fehler und zwar lautet es nun richtig
[mm] \sum_{i=2}^{n} \frac{1}{(i-1)i}=1-\frac{1}{n} [/mm]
> Da ich nicht weiß, ob du Induktion verstanden hast würde
> ich vorschlagen, dass du zunächst die Zusatzaufgabe
> machst.
> Übrigens hast du diese im Startpost falsch geschrieben.
>
> zu b)
> Zu zeigen: Für alle [mm]n\in\IN[/mm] gilt:
> [mm]\summe_{i=1}^{n}i^2=\frac{n(n+1)(2n+1)}{6}[/mm]
>
> Induktionsanfang:
> Für [mm]n=1[/mm] gilt:
> [mm]\summe_{i=1}^{1}i^2=1^2=1=\frac{6}{6}=\frac{1(1+1)(2\cdot 1+1)}{6}[/mm]
>
> Induktionsvorraussetzung:
> Es gelte für ein beliebiges, aber festes [mm]n\in\IN,[/mm] die
> Behauptung - [mm]\summe_{i=1}^{n}i^2=\frac{n(n+1)(2n+1)}{6}[/mm]
> Induktionsschritt:
> Für [mm]n\longrightarrow[/mm] [mm]n+1[/mm] gilt:
> [mm]\summe_{i=1}^{n+1}i^2=(\summe_{i=1}^{n}i^2)+(n+1)^2=[/mm]
> Ist dir das soweit klar?
Ja, ich wäre selber nicht darauf gekommen, aber es wurde einfach ein Konstantglied aus der Summe gelöst oder?
>Nun folgt mit der Induktionsvorraussetzung:
>
> [mm]=(\summe_{i=1}^{n}i^2)+(n+1)^2=\frac{n(n+1)(2n+1)}{6}+(n+1)^2=[/mm]
Wieso muss auf der reichten Seite auch das [mm] (n+1)^2 [/mm] eingefügt werden? Das verstehe ich nicht ganz.
> Jetzt musst du nur noch die Pünktchen ausfüllen:
>
> [mm]=\frac{n(n+1)(2n+1)}{6}+(n+1)^2=\ldots=\frac{(n+1)(n+2)(2(n+1)+1)}{6}.[/mm]
Ist an dieser Stelle jetzt nur die rechte Seite gemeint und meinen die Punkte, wie ich das entsprechend umforme damit das rauskommt?
Es wurde doch für n einfach n+1 in die vorherige Formel eingesetzt oder nicht?
> Damit hast du dann gezeigt, dass die Behauptung -
> [mm]\summe_{i=1}^{n}i^2=\frac{n(n+1)(2n+1)}{6}[/mm] - auch für
> [mm]n:=n+1[/mm] gilt und bist fertig.
>
> Jetzt du!
>
> Wenn du das verstanden hast, kannst du ja mal alleine
> probieren folgendes zu beweisen:
>
> Für alle [mm]n\in\IN[/mm] gilt: [mm]\summe_{i=1}^{n}i=\frac{n(n+1)}{2}[/mm]
>
Leider habe ich das noch nicht alles verstanden, aber versucht habe ich es trotzdem.
Induktionsanfang für n=1
[mm] \sum_{i=1}^{1} [/mm] i = 1= [mm] \frac{2}{2}=\frac{1(1+1)}{2}
[/mm]
Induktionsvoraussetzung
Es gelte für ein beliebiges, aber festes [mm] n\in \mathbb{N}, [/mm] die Behauptung [mm]\summe_{i=1}^{n}i=\frac{n(n+1)}{2}[/mm]
Induktionsschritt
Für n->n+1
[mm] \sum_{i=1}^{n+1}i=\sum_{i=1}^{n}i+(n+1)=....
[/mm]
Ich weiß leider nicht wie das weitergeht, weil ich das mit der rechten Seite nicht ganz verstehe.
> zu c)
> Die Fibonacci-Folge ist wie folgt rekursiv definiert:
> [mm]f_0:=0[/mm]
> [mm]f_1:=1[/mm]
> [mm]f_n:=f_{n-1}+f_{n-2}[/mm]
> Probiere nun selbst nach dem Muster von oben das ganze zu
> durchschauen und zu beweisen.
Das mit dem Beweis stelle ich erstmal hinten an, weil ich das einfache Beispiel noch nicht verstehe. :-/
|
|
|
| |
|
| Status: |
(Antwort) fertig | | Datum: | 23:19 Mo 25.11.2013 | | Autor: | DieAcht |
Hallo,
> Hey, vielen Dank für die Antwort!
>
> > Hallo,
> >
> > ich beziehe mich nun auf diesen, von dir, hochgeladenen
> > Link:
> > http://s14.directupload.net/images/131124/q45uh26p.jpg
> >
> > zu a)
> > Macht keinen Sinn. Frag nochmal den Übungsleiter!
>
> Ja, das habe ich heute gemacht und die Vermutungen waren
> auch richtig. Es waren direkt 2 Fehler und zwar lautet es
> nun richtig
>
> [mm]\sum_{i=2}^{n} \frac{1}{(i-1)i}=1-\frac{1}{n}[/mm]
>
Okay, dann probier das doch mal aus!
> > Da ich nicht weiß, ob du Induktion verstanden hast würde
> > ich vorschlagen, dass du zunächst die Zusatzaufgabe
> > machst.
> > Übrigens hast du diese im Startpost falsch
> geschrieben.
> >
> > zu b)
> > Zu zeigen: Für alle [mm]n\in\IN[/mm] gilt:
> > [mm]\summe_{i=1}^{n}i^2=\frac{n(n+1)(2n+1)}{6}[/mm]
> >
> > Induktionsanfang:
> > Für [mm]n=1[/mm] gilt:
> > [mm]\summe_{i=1}^{1}i^2=1^2=1=\frac{6}{6}=\frac{1(1+1)(2\cdot 1+1)}{6}[/mm]
>
> >
> > Induktionsvorraussetzung:
> > Es gelte für ein beliebiges, aber festes [mm]n\in\IN,[/mm] die
> > Behauptung - [mm]\summe_{i=1}^{n}i^2=\frac{n(n+1)(2n+1)}{6}[/mm]
> > Induktionsschritt:
> > Für [mm]n\longrightarrow[/mm] [mm]n+1[/mm] gilt:
> > [mm]\summe_{i=1}^{n+1}i^2=(\summe_{i=1}^{n}i^2)+(n+1)^2=[/mm]
> > Ist dir das soweit klar?
>
> Ja, ich wäre selber nicht darauf gekommen, aber es wurde
> einfach ein Konstantglied aus der Summe gelöst oder?
Ich weiß nicht, ob du das richtige meinst..
Es gilt doch anschaulich folgendes:
[mm] \summe_{i=1}^{n+1}i=1+2+\ldots+n+(n+1)
[/mm]
[mm] \cdots [/mm] guck dir nun das hier an:
[mm] \summe_{i=1}^{n+1}i=\summe_{i=1}^{n}i+\summe_{i=n+1}^{n+1}i=(\summe_{i=1}^{n}i)+(n+1)
[/mm]
So klarer?
>
>
> >Nun folgt mit der Induktionsvorraussetzung:
> >
> >
> [mm]=(\summe_{i=1}^{n}i^2)+(n+1)^2=\frac{n(n+1)(2n+1)}{6}+(n+1)^2=[/mm]
>
> Wieso muss auf der reichten Seite auch das [mm](n+1)^2[/mm]
> eingefügt werden? Das verstehe ich nicht ganz.
Sonst ist doch die Gleichung nicht mehr korrekt, siehe oben!
>
>
> > Jetzt musst du nur noch die Pünktchen ausfüllen:
> >
> >
> [mm]=\frac{n(n+1)(2n+1)}{6}+(n+1)^2=\ldots=\frac{(n+1)(n+2)(2(n+1)+1)}{6}.[/mm]
>
> Ist an dieser Stelle jetzt nur die rechte Seite gemeint und
> meinen die Punkte, wie ich das entsprechend umforme damit
> das rauskommt?
Ja genau, du willst zeigen, dass die Behauptung auch für $n+1$ gilt. Die rechte Seite ist nur als "Hilfe" da, damit du weißt, wohin du kommen musst!
>
> Es wurde doch für n einfach n+1 in die vorherige Formel
> eingesetzt oder nicht?
Genau!
>
> > Damit hast du dann gezeigt, dass die Behauptung -
> > [mm]\summe_{i=1}^{n}i^2=\frac{n(n+1)(2n+1)}{6}[/mm] - auch für
> > [mm]n:=n+1[/mm] gilt und bist fertig.
> >
> > Jetzt du!
> >
> > Wenn du das verstanden hast, kannst du ja mal alleine
> > probieren folgendes zu beweisen:
> >
> > Für alle [mm]n\in\IN[/mm] gilt: [mm]\summe_{i=1}^{n}i=\frac{n(n+1)}{2}[/mm]
> >
> Leider habe ich das noch nicht alles verstanden, aber
> versucht habe ich es trotzdem.
>
> Induktionsanfang für n=1
>
> [mm]\sum_{i=1}^{1}[/mm] i = 1= [mm]\frac{2}{2}=\frac{1(1+1)}{2}[/mm]
>
> Induktionsvoraussetzung
>
> Es gelte für ein beliebiges, aber festes [mm]n\in \mathbb{N},[/mm]
> die Behauptung [mm]\summe_{i=1}^{n}i=\frac{n(n+1)}{2}[/mm]
>
> Induktionsschritt
> Für n->n+1
>
> [mm]\sum_{i=1}^{n+1}i=\sum_{i=1}^{n}i+(n+1)=....[/mm]
>
> Ich weiß leider nicht wie das weitergeht, weil ich das mit
> der rechten Seite nicht ganz verstehe.
Das sieht doch schonmal gut aus! Nun setze die Induktionsvorraussetzung ein, also:
[mm] \sum_{i=1}^{n+1}i=\sum_{i=1}^{n}i+(n+1)=\frac{n(n+1)}{2}+(n+1)=\cdots
[/mm]
Wohin musst du nun kommen?
>
> > zu c)
> > Die Fibonacci-Folge ist wie folgt rekursiv definiert:
> > [mm]f_0:=0[/mm]
> > [mm]f_1:=1[/mm]
> > [mm]f_n:=f_{n-1}+f_{n-2}[/mm]
> > Probiere nun selbst nach dem Muster von oben das ganze
> zu
> > durchschauen und zu beweisen.
>
> Das mit dem Beweis stelle ich erstmal hinten an, weil ich
> das einfache Beispiel noch nicht verstehe. :-/
Mach ruhig erst das einfache Beispiel, dann gehen die anderen auch!
>
Gruß
DieAcht
|
|
|
| |
|
Hallo,
entschuldige ich hatte dieses Thema schon ganz "verdrängt".
Also den Großteil der Sachen habe ich jetzt hinbekommen.
> >
> > [mm]\sum_{i=2}^{n} \frac{1}{(i-1)i}=1-\frac{1}{n}[/mm]
> >
>
> Okay, dann probier das doch mal aus!
>
Induktionsanfang
[mm] \sum_{i=2}^{2} \frac{1}{(i-1)i}=\frac{1}{(2-1)2}=\frac{1}{2}=1-\frac{1}{2}
[/mm]
Induktionsvoraussetzung
Es gilt für ein beliebiges, aber festes n [mm] \in \mathbb{N} [/mm] die Behauptung
[mm] \sum_{i=2}^{n} \frac{1}{(i-1)i}=1-\frac{1}{n}
[/mm]
Induktionsschritt
$n->n+1$
[mm] \sum_{i=2}^{n+1} \frac{1}{(i-1)i}=\sum_{i=2}^{n} \frac{1}{(i-1)i}+ \frac{1}{(n+1-1)n+1}
[/mm]
[mm] =\sum_{i=2}^{n} \frac{1}{(i-1)i}+ \frac{1}{n(n+1)}
[/mm]
[mm] =1-\frac{1}{n}+ \frac{1}{n(n+1)}
[/mm]
[mm] =1-\frac{n+1}{n(n+1)}+ \frac{1}{n(n+1)}
[/mm]
[mm] =1+\frac{-n-1}{n(n+1)}+ \frac{1}{n(n+1)}
[/mm]
[mm] =1+\frac{-n-1+1}{n(n+1)}
[/mm]
[mm] =1+\frac{-n}{n(n+1)}
[/mm]
[mm] =1-\frac{n}{n(n+1)}
[/mm]
[mm] =1-\frac{1}{n+1}
[/mm]
> > > Jetzt musst du nur noch die Pünktchen ausfüllen:
> > >
> > >
> >
> [mm]=\frac{n(n+1)(2n+1)}{6}+(n+1)^2=\ldots=\frac{(n+1)(n+2)(2(n+1)+1)}{6}.[/mm]
> >
> > Ist an dieser Stelle jetzt nur die rechte Seite gemeint und
> > meinen die Punkte, wie ich das entsprechend umforme damit
> > das rauskommt?
>
> Ja genau, du willst zeigen, dass die Behauptung auch für
> [mm]n+1[/mm] gilt. Die rechte Seite ist nur als "Hilfe" da, damit du
> weißt, wohin du kommen musst!
Das bekomme ich einfach nicht hin. Ich habe es zuerst versucht auszumultiplizieren und dann wieder zusammenzufassen, aber das habe ich auch nicht geschafft. :-(
> >
> > Es wurde doch für n einfach n+1 in die vorherige Formel
> > eingesetzt oder nicht?
>
> Genau!
>
> >
> > > Damit hast du dann gezeigt, dass die Behauptung -
> > > [mm]\summe_{i=1}^{n}i^2=\frac{n(n+1)(2n+1)}{6}[/mm] - auch für
> > > [mm]n:=n+1[/mm] gilt und bist fertig.
> > >
> > > Jetzt du!
> > >
> > > Wenn du das verstanden hast, kannst du ja mal alleine
> > > probieren folgendes zu beweisen:
> > >
> > > Für alle [mm]n\in\IN[/mm] gilt: [mm]\summe_{i=1}^{n}i=\frac{n(n+1)}{2}[/mm]
> > >
> > Leider habe ich das noch nicht alles verstanden, aber
> > versucht habe ich es trotzdem.
> >
> > Induktionsanfang für n=1
> >
> > [mm]\sum_{i=1}^{1}[/mm] i = 1= [mm]\frac{2}{2}=\frac{1(1+1)}{2}[/mm]
> >
> > Induktionsvoraussetzung
> >
> > Es gelte für ein beliebiges, aber festes [mm]n\in \mathbb{N},[/mm]
> > die Behauptung [mm]\summe_{i=1}^{n}i=\frac{n(n+1)}{2}[/mm]
> >
> > Induktionsschritt
> > Für n->n+1
> >
> > [mm]\sum_{i=1}^{n+1}i=\sum_{i=1}^{n}i+(n+1)=....[/mm]
> >
> > Ich weiß leider nicht wie das weitergeht, weil ich das mit
> > der rechten Seite nicht ganz verstehe.
>
> Das sieht doch schonmal gut aus! Nun setze die
> Induktionsvorraussetzung ein, also:
>
> [mm]\sum_{i=1}^{n+1}i=\sum_{i=1}^{n}i+(n+1)=\frac{n(n+1)}{2}+(n+1)=\cdots[/mm]
>
> Wohin musst du nun kommen?
Ich muss zeigen, dass meine linke Seite zu [mm] \frac{(n+1)(n+2)}{2} [/mm] werden kann ?
$ [mm] \sum_{i=1}^{n+1}i=\sum_{i=1}^{n}i+(n+1)=\frac{n(n+1)}{2}+(n+1)
[/mm]
[mm] =\frac{n(n+1)}{2}+\frac{2(n+1)}{2}
[/mm]
[mm] =\frac{n(n+1)+2(n+1)}{2}
[/mm]
[mm] =\frac{n^2+n+2+2n}{2}
[/mm]
[mm] =\frac{n(n+1)}{2}+\frac{2(n+1)}{2}=\frac{n^2+3n+2}{2}
[/mm]
[mm] =\frac{(n+1)(n+2)}{2}
[/mm]
> >
> > > zu c)
> > > Die Fibonacci-Folge ist wie folgt rekursiv definiert:
> > > [mm]f_0:=0[/mm]
> > > [mm]f_1:=1[/mm]
> > > [mm]f_n:=f_{n-1}+f_{n-2}[/mm]
> > > Probiere nun selbst nach dem Muster von oben das
> ganze
> > zu
> > > durchschauen und zu beweisen.
> >
> > Das mit dem Beweis stelle ich erstmal hinten an, weil ich
> > das einfache Beispiel noch nicht verstehe. :-/
>
> Mach ruhig erst das einfache Beispiel, dann gehen die
> anderen auch!
Steht [mm] F_i [/mm] für die i-te Fibonacci-Zahl,so gilt für alle n [mm] \in \mathbb{N}: \sum_{i=1}^{n}=F_i=F_{n+2}-1
[/mm]
Induktionsanfang
[mm] \sum_{i=1}^{1}F_i=F_{n+2}-1=F_1=1 [/mm]
Kann man das einfach so machen, weil die erste Fibonacci-Zahl die Eins ist? Ansonsten weiß ich nämlich nicht wie man da was machen könnte.
Induktionsvoraussetzung
Es gilt für ein beliebiges, aber festes [mm] n\in \mathbb{N} [/mm] die Behauptung
[mm] \sum_{i=1}^{n}F_i=F_{n+2}-1
[/mm]
Induktionsschritt
$n->n+1$
[mm] \sum_{i=1}^{n+1}F_i= \sum_{i=1}^{n}F_i+F_{n+1}
[/mm]
[mm] =F_{n+2}-1+F_{n+1}
[/mm]
[mm] =F_{n+1}+F_{n+2}-1 [/mm]
Kann ich hier einfach über die Defintion der Fibonacci Folge mit [mm] F_n=F_{n-1}+F_{n-2} [/mm] argumentieren und schreiben:
[mm] =F_{n+3}-1 [/mm]
[mm] =F_{(n+1)+2}-1 [/mm] ?
Vielen Dank im Voraus für deine tolle Hilfe!
|
|
|
| |
|
| Status: |
(Antwort) fertig | | Datum: | 17:24 So 08.12.2013 | | Autor: | Marcel |
Hallo,
> Hallo,
> entschuldige ich hatte dieses Thema schon ganz
> "verdrängt".
>
> Also den Großteil der Sachen habe ich jetzt hinbekommen.
>
>
> > >
> > > [mm]\sum_{i=2}^{n} \frac{1}{(i-1)i}=1-\frac{1}{n}[/mm]
> > >
> >
> > Okay, dann probier das doch mal aus!
> >
>
> Induktionsanfang
>
> [mm]\sum_{i=2}^{2} \frac{1}{(i-1)i}=\frac{1}{(2-1)2}=\frac{1}{2}=1-\frac{1}{2}[/mm]
>
>
> Induktionsvoraussetzung
>
> Es gilt für ein beliebiges, aber festes n [mm]\in \mathbb{N}[/mm]
> die Behauptung
> [mm]\sum_{i=2}^{n} \frac{1}{(i-1)i}=1-\frac{1}{n}[/mm]
>
> Induktionsschritt
> [mm]n->n+1[/mm]
>
> [mm]\sum_{i=2}^{n+1} \frac{1}{(i-1)i}=\sum_{i=2}^{n} \frac{1}{(i-1)i}+ \frac{1}{(n+1-1)n+1}[/mm]
>
> [mm]=\sum_{i=2}^{n} \frac{1}{(i-1)i}+ \frac{1}{n(n+1)}[/mm]
>
> [mm]=1-\frac{1}{n}+ \frac{1}{n(n+1)}[/mm]
>
> [mm]=1-\frac{n+1}{n(n+1)}+ \frac{1}{n(n+1)}[/mm]
>
> [mm]=1+\frac{-n-1}{n(n+1)}+ \frac{1}{n(n+1)}[/mm]
>
> [mm]=1+\frac{-n-1+1}{n(n+1)}[/mm]
> [mm]=1+\frac{-n}{n(n+1)}[/mm]
> [mm]=1-\frac{n}{n(n+1)}[/mm]
> [mm]=1-\frac{1}{n+1}[/mm]
>
>
> > > > Jetzt musst du nur noch die Pünktchen ausfüllen:
> > > >
> > > >
> > >
> >
[mm] ($\*$)[/mm] [mm]=\frac{n(n+1)(2n+1)}{6}+(n+1)^2=\ldots=\frac{(n+1)(n+2)(2(n+1)+1)}{6}.[/mm]
> > >
> > > Ist an dieser Stelle jetzt nur die rechte Seite gemeint und
> > > meinen die Punkte, wie ich das entsprechend umforme damit
> > > das rauskommt?
> >
> > Ja genau, du willst zeigen, dass die Behauptung auch für
> > [mm]n+1[/mm] gilt. Die rechte Seite ist nur als "Hilfe" da, damit du
> > weißt, wohin du kommen musst!
>
> Das bekomme ich einfach nicht hin. Ich habe es zuerst
> versucht auszumultiplizieren und dann wieder
> zusammenzufassen, aber das habe ich auch nicht geschafft.
> :-(
zuerst klammere [mm] $(n+1)\,$ [/mm] vor:
[mm] $\frac{n(n+1)(2n+1)}{6}+(n+1)^2=(n+1)*\left(\frac{n(2n+1)}{6}+(n+1)\right)$
[/mm]
Nennergleich machen:
[mm] ($\*\*$) $(n+1)*\left(\frac{n(2n+1)}{6}+(n+1)\right)=(n+1)*\left(\frac{n(2n+1)+6*(n+1)}{6}\right)$
[/mm]
Im Prinzip reicht es jetzt, wenn Du die ganz rechte Seite von [mm] ($\*$) [/mm] mit [mm] ($\*\*$) [/mm] vergleichst,
nachzuweisen, dass
[mm] $n(2n+1)+6*(n+1)=(n+2)\cdot(2(n+1)+1)$
[/mm]
gilt. Dazu reichen Äquivalenzumformungen (bei denen am Ende das Lesen
der "Rückrichtung" [mm] $\Longleftarrow$ [/mm] eigentlich das einzig interessante ist).
Straight forward ginge das auch:
1. [mm] $n(2n+1)+6*(n+1)=2n^2+7n+6\,.$
[/mm]
Und jetzt kann man
2. [mm] $(2n^2+7n+6):(n+2)\,$
[/mm]
mit Polynomdivision ausrechnen (es sollte dann [mm] $2\cdot(n+1)+1=2n+3$ [/mm] rauskommen).
Gruß,
Marcel
|
|
|
| |
|
| Status: |
(Antwort) fertig | | Datum: | 17:49 So 08.12.2013 | | Autor: | DieAcht |
Hallo,
> Hallo,
> entschuldige ich hatte dieses Thema schon ganz
> "verdrängt".
>
> Also den Großteil der Sachen habe ich jetzt hinbekommen.
>
>
> > >
> > > [mm]\sum_{i=2}^{n} \frac{1}{(i-1)i}=1-\frac{1}{n}[/mm]
> > >
> >
> > Okay, dann probier das doch mal aus!
> >
>
> Induktionsanfang
>
> [mm]\sum_{i=2}^{2} \frac{1}{(i-1)i}=\frac{1}{(2-1)2}=\frac{1}{2}=1-\frac{1}{2}[/mm]
>
>
> Induktionsvoraussetzung
>
> Es gilt für ein beliebiges, aber festes n [mm]\in \mathbb{N}[/mm]
> die Behauptung
> [mm]\sum_{i=2}^{n} \frac{1}{(i-1)i}=1-\frac{1}{n}[/mm]
>
> Induktionsschritt
> [mm]n->n+1[/mm]
>
> [mm]\sum_{i=2}^{n+1} \frac{1}{(i-1)i}=\sum_{i=2}^{n} \frac{1}{(i-1)i}+ \frac{1}{(n+1-1)n+1}[/mm]
>
> [mm]=\sum_{i=2}^{n} \frac{1}{(i-1)i}+ \frac{1}{n(n+1)}[/mm]
>
> [mm]=1-\frac{1}{n}+ \frac{1}{n(n+1)}[/mm]
>
> [mm]=1-\frac{n+1}{n(n+1)}+ \frac{1}{n(n+1)}[/mm]
>
> [mm]=1+\frac{-n-1}{n(n+1)}+ \frac{1}{n(n+1)}[/mm]
>
> [mm]=1+\frac{-n-1+1}{n(n+1)}[/mm]
> [mm]=1+\frac{-n}{n(n+1)}[/mm]
> [mm]=1-\frac{n}{n(n+1)}[/mm]
> [mm]=1-\frac{1}{n+1}[/mm]
![[ok]](/images/smileys/ok.gif "[ok]")
>
>
> > > > Jetzt musst du nur noch die Pünktchen ausfüllen:
> > > >
> > > >
> > >
> >
> [mm]=\frac{n(n+1)(2n+1)}{6}+(n+1)^2=\ldots=\frac{(n+1)(n+2)(2(n+1)+1)}{6}.[/mm]
> > >
> > > Ist an dieser Stelle jetzt nur die rechte Seite gemeint und
> > > meinen die Punkte, wie ich das entsprechend umforme damit
> > > das rauskommt?
> >
> > Ja genau, du willst zeigen, dass die Behauptung auch für
> > [mm]n+1[/mm] gilt. Die rechte Seite ist nur als "Hilfe" da, damit du
> > weißt, wohin du kommen musst!
>
> Das bekomme ich einfach nicht hin. Ich habe es zuerst
> versucht auszumultiplizieren und dann wieder
> zusammenzufassen, aber das habe ich auch nicht geschafft.
> :-(
Siehe Marcel's Antwort.
>
> > >
> > > Es wurde doch für n einfach n+1 in die vorherige Formel
> > > eingesetzt oder nicht?
> >
> > Genau!
> >
> > >
> > > > Damit hast du dann gezeigt, dass die Behauptung -
> > > > [mm]\summe_{i=1}^{n}i^2=\frac{n(n+1)(2n+1)}{6}[/mm] - auch für
> > > > [mm]n:=n+1[/mm] gilt und bist fertig.
> > > >
> > > > Jetzt du!
> > > >
> > > > Wenn du das verstanden hast, kannst du ja mal alleine
> > > > probieren folgendes zu beweisen:
> > > >
> > > > Für alle [mm]n\in\IN[/mm] gilt: [mm]\summe_{i=1}^{n}i=\frac{n(n+1)}{2}[/mm]
> > > >
> > > Leider habe ich das noch nicht alles verstanden, aber
> > > versucht habe ich es trotzdem.
> > >
> > > Induktionsanfang für n=1
> > >
> > > [mm]\sum_{i=1}^{1}[/mm] i = 1= [mm]\frac{2}{2}=\frac{1(1+1)}{2}[/mm]
> > >
> > > Induktionsvoraussetzung
> > >
> > > Es gelte für ein beliebiges, aber festes [mm]n\in \mathbb{N},[/mm]
> > > die Behauptung [mm]\summe_{i=1}^{n}i=\frac{n(n+1)}{2}[/mm]
> > >
> > > Induktionsschritt
> > > Für n->n+1
> > >
> > > [mm]\sum_{i=1}^{n+1}i=\sum_{i=1}^{n}i+(n+1)=....[/mm]
> > >
> > > Ich weiß leider nicht wie das weitergeht, weil ich das mit
> > > der rechten Seite nicht ganz verstehe.
> >
> > Das sieht doch schonmal gut aus! Nun setze die
> > Induktionsvorraussetzung ein, also:
> >
> >
> [mm]\sum_{i=1}^{n+1}i=\sum_{i=1}^{n}i+(n+1)=\frac{n(n+1)}{2}+(n+1)=\cdots[/mm]
> >
> > Wohin musst du nun kommen?
>
>
> Ich muss zeigen, dass meine linke Seite zu
> [mm]\frac{(n+1)(n+2)}{2}[/mm] werden kann ?
>
> $
> [mm]\sum_{i=1}^{n+1}i=\sum_{i=1}^{n}i+(n+1)=\frac{n(n+1)}{2}+(n+1)[/mm]
> [mm]=\frac{n(n+1)}{2}+\frac{2(n+1)}{2}[/mm]
> [mm]=\frac{n(n+1)+2(n+1)}{2}[/mm]
> [mm]=\frac{n^2+n+2+2n}{2}[/mm]
>
> [mm]=\frac{n(n+1)}{2}+\frac{2(n+1)}{2}=\frac{n^2+3n+2}{2}[/mm]
> [mm]=\frac{(n+1)(n+2)}{2}[/mm]
> > >
> > > > zu c)
> > > > Die Fibonacci-Folge ist wie folgt rekursiv definiert:
> > > > [mm]f_0:=0[/mm]
> > > > [mm]f_1:=1[/mm]
> > > > [mm]f_n:=f_{n-1}+f_{n-2}[/mm]
> > > > Probiere nun selbst nach dem Muster von oben das
> > ganze
> > > zu
> > > > durchschauen und zu beweisen.
> > >
> > > Das mit dem Beweis stelle ich erstmal hinten an, weil ich
> > > das einfache Beispiel noch nicht verstehe. :-/
> >
> > Mach ruhig erst das einfache Beispiel, dann gehen die
> > anderen auch!
>
>
> Steht [mm]F_i[/mm] für die i-te Fibonacci-Zahl,so gilt für alle n
> [mm]\in \mathbb{N}: \sum_{i=1}^{n}=F_i=F_{n+2}-1[/mm]
>
> Induktionsanfang
>
> [mm]\sum_{i=1}^{1}F_i=F_{n+2}-1=F_1=1[/mm]
>
> Kann man das einfach so machen, weil die erste
> Fibonacci-Zahl die Eins ist? Ansonsten weiß ich nämlich
> nicht wie man da was machen könnte.
>
>
>
> Induktionsvoraussetzung
>
> Es gilt für ein beliebiges, aber festes [mm]n\in \mathbb{N}[/mm]
> die Behauptung
>
> [mm]\sum_{i=1}^{n}F_i=F_{n+2}-1[/mm]
>
>
> Induktionsschritt
>
> [mm]n->n+1[/mm]
>
>
> [mm]\sum_{i=1}^{n+1}F_i= \sum_{i=1}^{n}F_i+F_{n+1}[/mm]
>
> [mm]=F_{n+2}-1+F_{n+1}[/mm]
> [mm]=F_{n+1}+F_{n+2}-1[/mm]
>
> Kann ich hier einfach über die Defintion der Fibonacci
> Folge mit [mm]F_n=F_{n-1}+F_{n-2}[/mm] argumentieren und schreiben:
>
> [mm]=F_{n+3}-1[/mm]
> [mm]=F_{(n+1)+2}-1[/mm] ?
>
Wenn ihr das schon bewiesen habt, dann ist es in Ordnung.
>
>
>
>
> Vielen Dank im Voraus für deine tolle Hilfe!
>
Ich denke, dass du vollständige Induktion verstanden hast
Gruß
DieAcht
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig | | Datum: | 00:34 Mo 25.11.2013 | | Autor: | Marcel |
Hallo,
> Beweisen Sie per vollständiger Induktion die folgenden
> Behauptungen.
>
> (a) Für jede natürliche Zahl n [mm]\ge[/mm] 2 gilt [mm]\sum_{i=1}^{n} \frac{1}{(n-1)*n}=1-\frac{1}{n}.[/mm]
damit da mal was vernünftiges steht, verweise ich auf
https://matheraum.de/read?i=993011
Ohne Induktion erkennt man dann, dass die Formel sicher
[mm] $\sum_{i=\red{2}}^n \frac{1}{i*(i-1)}=1-\frac{1}{n}$
[/mm]
lautet. (Das stimmt dann auch für $n [mm] \in \IN\,,$ [/mm] also insbesondere [mm] $n=1\,,$
[/mm]
da die leere Summe als 0 definiert ist.)
Gruß,
Marcel
|
|
|
|
