Vollständige Induktion (1) < Induktion < eindimensional < reell < Analysis < Hochschule < Mathe < Vorhilfe
|
| Status: |
(Frage) beantwortet  | | Datum: | 11:07 Mo 27.10.2014 | | Autor: | tobmu |
| Aufgabe | Beweisen Sie mittels vollständiger Induktion:
Die Abbildung T : [mm] \IN \to \IN [/mm] sei gegeben durch
T(1) = 1 und
T(n) = T(n-1)+n.
Es gilt T(n) [mm] \le n^{2} [/mm] für alle n [mm] \in \IN. [/mm] |
Hallo liebe Community,
ich habe Beweise mit vollständiger Induktion leider nur anhand von Summen gelernt und weiß nicht, wie ich hier vorgehen soll. Es wäre super, wenn ihr mir den Lösungsweg hierfür verraten könntet.
Bitte entschuldigt die kurze Frist. Ich werde mich das nächste Mal früher melden!
Danke im Vorraus!
Ich habe diese Frage in keinem Forum auf anderen Internetseiten gestellt.
|
|
| |
|
> Beweisen Sie mittels vollständiger Induktion:
> Die Abbildung T : [mm]\IN \to \IN[/mm] sei gegeben durch
> T(1) = 1 und
> T(n) = T(n-1)+n.
> Es gilt T(n) [mm]\le n^{2}[/mm] für alle n [mm]\in \IN.[/mm]
>
>
> Hallo liebe Community,
>
> ich habe Beweise mit vollständiger Induktion leider nur
> anhand von Summen gelernt und weiß nicht, wie ich hier
> vorgehen soll. Es wäre super, wenn ihr mir den Lösungsweg
> hierfür verraten könntet.
Hallo,
nun, so direkt "verraten" mögen wir hier nichts.
Aber wir helfen Dir gerne beim Entwickeln einer Lösung.
Daß Du vollständige Induktion bisher nur anhand von Beispielen mit Summen gelernt und geübt hast, ist nicht schlimm. Mit irgendwas muß es ja losgehen.
Wichtig ist, daß Du das Prinzip der vollständigen Induktion verstanden hast - und es dann selbständig auf andere passende Aufgaben übertragen kannst.
Für den Fall, daß Du Dich bisher sehr auf den reinen Rechenvorgang und weniger auf das Prinzip an sich konzentriert hast, schildere ich Dir nochmal den Ablauf der vollständigen Induktion.
Induktion:
Beh.
Eine Aussage gilt für alle [mm] n\in \IN.
[/mm]
Induktionsanfang
Man zeigt, daß die Aussage für n=1 gilt
Induktionsvoraussetzung
Man nimmt an, daß die Aussage für ein festes [mm] n\in\IN [/mm] gilt.
(Hier ist nichts zu zeigen, tun oder denken. Man schreibt einfach hin:
"Die Aussage gelte für ein [mm] n\in \IN)
[/mm]
Induktionsschluß
Hier wird dann gezeigt, daß die Aussage unter der gemachten Voraussetzung auch für n+1 stimmt.
Nun wenden wir uns Deiner Aufgabe zu.
Zunächst wird hier wie oben angegeben eine Funktion T definiert, die aus den nat. Zahlen in die nat. Zahlen abbildet.
Über diese Funktion T wird nun behauptet, daß
[mm] T(n)\le n^2 [/mm] für alle [mm] n\in \IN [/mm] ist.
(Du könntest jetzt - auch wenn wir es so für den Beweis nicht brauchen, mal für n=1,2,3,4,5 testen, ob die Behauptung stimmt. Mach das mal! Es hilft beim Verständnis der Funktion.)
Danach beginnen wir den Induktionsbeweis:
Induktion:
Beh.
Es ist
[mm] T(n)\le n^2 [/mm] für alle [mm] n\in \IN.
[/mm]
Induktionsanfang
Zeige, daß die Aussage für n=1 gilt:
T(1)=... (Und? Ist das [mm] \le 1^2? [/mm] Ja. Paßt.)
Induktionsvoraussetzung
Für ein [mm] n\in \IN [/mm] gelte
[mm] T(n)\le n^2.
[/mm]
(Hier ist nichts mehr zu tun, denken, schreiben, arbeiten.)
Induktionsschluß
Hier wird dann gezeigt, daß die Aussage unter der gemachten Voraussetzung auch für n+1 stimmt.
Zu zeigen ist hier also [mm] T(n+1)\le (n+1)^2.
[/mm]
Los geht's:
T(n+1)= (verwende die Definition von T)
[mm] \le [/mm] (verwende die Induktionsvoraussetzung)
überlege jetzt, warum das
[mm] \le (n+1)^2 [/mm] ist.
Versuch's mal.
LG Angela
> Bitte entschuldigt die kurze Frist. Ich werde mich das
> nächste Mal früher melden!
>
> Danke im Vorraus!
>
> Ich habe diese Frage in keinem Forum auf anderen
> Internetseiten gestellt.
|
|
|
|
