vollständige Induktion < Algorithmen < Schule < Informatik < Vorhilfe
|
| Status: |
(Frage) beantwortet  | | Datum: | 18:13 Sa 21.11.2009 | | Autor: | Tizian |
| Aufgabe | Zeigen Sie durch vollständige Induktion, dass für alle natürlichen Zahlen f n = n gilt.
(1) f 0 = 0
(2) f 1 = 1
(3) f (n+2) = 2*f (n+1) - f n |
[mm] \forall [/mm] a [mm] \in \IN [/mm] : f a = a
Induktionsanfang: f 0 = 0 sei eine wahre Aussage.
f 0
-(1)--> 0 = 0 w.A.
Induktionsschritt
Induktionsvoraussetzung: f a = a
zu zeigen: f(a+1)=a+1
Induktionsbeweis:
f a = a |+1
f (a) +1 = a + 1
--Induktionsvoraussetzung--> a + 1 = a + 1 w.z.b.w.
Also der Beweis kommt mir persönlich etwas schwammig vor. Ich hab es auch auf andere Art und Weise probiert (z.B. f (a+1) soll durch Umformen (a+1) werden, ich bin allerdings immer an dem endlosen Rekursionsanker gescheitert).
Ich würde mich sehr über eine Hilfestellung freuen.
LG Tizian
|
|
| |
|
> Zeigen Sie durch vollständige Induktion, dass für alle
> natürlichen Zahlen f n = n gilt.
Hallo,
Indizes bitte mit Unterstrich, große Indizes zusätzlich in geschweifte Klammern.
> (1) f 0 = 0
> (2) f 1 = 1
> (3) f (n+2) = 2*f (n+1) - f n
Du hast also eine rekursiv definierte Folge [mm] f_n [/mm] und sollst zeigen
[mm] f_n=n [/mm] fürr alle [mm] n\in \IN.
[/mm]
> Induktionsanfang:
Zu zeigen:
> f 0 = 0 sei ist eine wahre Aussage.
>
> f 0
> -(1)--> 0 = 0 w.A.
Bißchen kryprisch aufgeschrieben. Mach's doch so:
[mm] f_0=0 [/mm] nach(1).
>
> Induktionsschritt
>
> Induktionsvoraussetzung: f a = a für ein [mm] a\in \IN.
[/mm]
Induktionsschluß:
> zu zeigen:
Dann ist
> [mm] f_{a+1}=a+1
[/mm]
>
> Induktionsbeweis:
Es ist [mm] f_{a+1}= 2*f_{a} [/mm] - [mm] f_{a-1} [/mm] (nach (3))
= ... Jetzt verwende die Induktionsvoraussetzung. Du wirst merken, daß Du sie noch um [mm] f_{a-1}=a-1 [/mm] ergänzen mußt, im selben Zuge brauchst Du beim Induktionsanfang noch [mm] f_1=1 [/mm] - was ja kein Problem ist.
Gruß v. Angela
|
|
|
| |
|
| Status: |
(Frage) beantwortet | | Datum: | 18:50 Sa 21.11.2009 | | Autor: | Tizian |
Mit welcher Begründung darf/kann ich denn die Induktionsvoraussetzung [mm] f_{a-1}=a-1 [/mm] erweitern?
Muss ich mir den Induktionsanfang anders wählen?
Sei [mm] f_{a-1}=a-1 [/mm] teil Induktionsvoraussetzung, so kann ich die Induktion abschließen.
|
|
|
| |
|
> Mit welcher Begründung darf/kann ich denn die
> Induktionsvoraussetzung [mm]f_{a-1}=a-1[/mm] erweitern?
> Muss ich mir den Induktionsanfang anders wählen?
Hallo,
ich hab ja gesagt: dann brauchst Du [mm] f_0=0 [/mm] und [mm] f_1=1.
[/mm]
Die Indvoraussetzung ist dann: es gilt [mm] f_{a-1}=a-1 [/mm] und [mm] f_a=a [/mm] für ein [mm] a\in \IN.
[/mm]
Da wir den Induktionsanfang mit den beiden gemacht haben, haben wir's dort für a=1 verankert.
> Sei [mm]f_{a-1}=a-1[/mm] teil Induktionsvoraussetzung, so kann ich
> die Induktion abschließen.
Versteh ich jetzt nicht.
Gruß v. Angela
|
|
|
| |
|
| Status: |
(Frage) beantwortet | | Datum: | 19:05 Sa 21.11.2009 | | Autor: | Tizian |
Der zweite Teil ist unwichtig.
Aus dem Induktionsanfang würde ich jetzt nur folgenden Schluss ziehen:
[mm] f_{a}=a
[/mm]
[mm] f_{a}-f_{1}=a-1
[/mm]
Darf man dann einfach sagen: [mm] f_{a-1}=a-1 [/mm] ?
|
|
|
| |
|
> Der zweite Teil ist unwichtig.
>
> Aus dem Induktionsanfang würde ich jetzt nur folgenden
> Schluss ziehen:
Hallo,
aus dem Induktionsanfang zieht man erstmal überhaupt keine Schlüsse.
Induktion hast Du verstanden?
Man nimmt ja an, daß die Aussage für ein n gilt, und zeigt, daß sie dann auch fürs darauffolgende gilt.
Das ist natürlich alles für die Katz', sofern es überhaupt kein n gibt, für das die Aussage gilt. Und damit das nicht passiert, braucht man den Induktionsanfang für eine konkrete Zahl als Anker.
Dann hat man: gilt die Aussage für , dann auch für 1+1=2, dann auch für 2+1=3 usw.
Das ist das Prinzip.
In Deiner Aufgabe werfen wir den Anker mit der Gültigkeit von [mm] f_0=0 [/mm] und [mm] f_1 [/mm] =1.
Wir setzen dann voraus (einfach so!, in der Hoffnung, daß es stimmt!) daß es ein a gibt, für welches [mm] f_{a-1}=a-1 [/mm] und [mm] f_a=a.
[/mm]
Und nun zeigen wir, daß es unter dieser Voraussetzung (!) für die darauffolgende Zahl auch gilt, daß also [mm] f_{a+1}=a+1.
[/mm]
Was haben wir gewonnen?
Wir wissen f(0)=0 und f(1)=1.
Unser Beweis sagt für a=1: dann ist auch f(2)=2
Und wieder sagt unser Beweis für a=2: dann ist auch f(3)=3.
usw.
Gruß v. Angela
|
|
|
|
