www.vorhilfe.de
- Förderverein -
Der Förderverein.

Gemeinnütziger Verein zur Finanzierung des Projekts Vorhilfe.de.
Hallo Gast!einloggen | registrieren ]
Startseite · Mitglieder · Impressum
Forenbaum
^ Forenbaum
Status VH e.V.
  Status Vereinsforum

Gezeigt werden alle Foren bis zur Tiefe 2

Navigation
 Startseite...
 Suchen
 Impressum
Das Projekt
Server und Internetanbindung werden durch Spenden finanziert.
Organisiert wird das Projekt von unserem Koordinatorenteam.
Hunderte Mitglieder helfen ehrenamtlich in unseren moderierten Foren.
Anbieter der Seite ist der gemeinnützige Verein "Vorhilfe.de e.V.".
Partnerseiten
Weitere Fächer:

Open Source FunktionenplotterFunkyPlot: Kostenloser und quelloffener Funktionenplotter für Linux und andere Betriebssysteme
Forum "Schul-Informatik Algorithmen" - vollständige Induktion
vollständige Induktion < Algorithmen < Schule < Informatik < Vorhilfe
Ansicht: [ geschachtelt ] | ^ Forum "Schul-Informatik Algorithmen"  | ^^ Alle Foren  | ^ Forenbaum  | Materialien

vollständige Induktion: Korrektur; Erklärung
Status: (Frage) beantwortet Status 
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

        
Bezug
vollständige Induktion: Antwort
Status: (Antwort) fertig Status 
Datum: 18:30 Sa 21.11.2009
Autor: angela.h.b.


> 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

Bezug
                
Bezug
vollständige Induktion: Frage (beantwortet)
Status: (Frage) beantwortet Status 
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.

Bezug
                        
Bezug
vollständige Induktion: Antwort
Status: (Antwort) fertig Status 
Datum: 18:55 Sa 21.11.2009
Autor: angela.h.b.


> 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


Bezug
                                
Bezug
vollständige Induktion: Frage (beantwortet)
Status: (Frage) beantwortet Status 
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] ?

Bezug
                                        
Bezug
vollständige Induktion: Antwort
Status: (Antwort) fertig Status 
Datum: 19:48 Sa 21.11.2009
Autor: angela.h.b.


> 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





Bezug
Ansicht: [ geschachtelt ] | ^ Forum "Schul-Informatik Algorithmen"  | ^^ Alle Foren  | ^ Forenbaum  | Materialien


^ Seitenanfang ^
ev.vorhilfe.de
[ Startseite | Mitglieder | Impressum ]