Re: Vollständige Induktion

[Reinhard Wallner <wallnerr***AT***sbox.tugraz.at>]

Manuel Frech schrieb:
> AndiFe schrieb:
>
> > Frage: Bei 2n > n^2
> >
> > Okay: Ab N=5 Gültig  ist klar...
> >
> > nur dann beim "Schluss":
> > 1)
> > 2^n+1 = 2x2^n > 2x n^2 ... okay... Beide seiten mal 2... Wie kommt der 
> > da drauf? warum mal 2 und ned mal 5 z.B.
> >
> > 2)
> > 2x2^n > 2x n^2 = n^2 +n^2 >= n^2 + 5n =.... warum hier 5n... vorher 
> > will man das im vorhinein wissen... des ergibt doch keinen Sinn... des 
> > is ja aus der Luft gegriffen oder? bzw. weil man schon das Ergebnis 
> > kennt, form ich mir das jetzt so irgendwie zusammen?
> >
> > die weiteren berechnung ergeben dann natürlich wieder einen Sinn...
> Ich habe da auch ein wenig überlegen müssen. Bin dann darauf gekommen 
> (ich hoffe es stimmt so):
>     2*2^n > 2*n²
> ..... das die ursprüngliche Ungleich;
> Der nächste Schritt ist, dass wir für den "kleineren" Teil etwas finden, 
> dass etwa kleiner oder gleichgroß, allerdings nicht größer ist (2*n² = 
> n²+n²) und wir müssen uns immer näher an die Induktionsvoraussetzung 
> herantasten.
> Wir müssen ja bei unserem Induktionsschluss irgendwie auf der rechten 
> Seite unserer Ungleichung irgendwie auf eine Form der rechten Seite der 
> Induktionsbehauptung zu kommen. Dazu formen wir den Term mit Hilfe der 
> Induktionsbasis (5) um und erstellen uns eine weitere Ungleichung.
>     n²+n² >= n²+5n
> Das n²+5n ist wiederum größer als n² + 2n + 1; somit:
>     n²+5n > n² + 2n + 1   (=> (n+1)²
>     n²+5n > (n+1)²
>
> Alles in allem:
>     2*2^n > 2*n²
>         n²+n² >= n²+5n
>             n²+5n > n² + 2n + 1
>             n²+5n > (n+1)²
>     2*2^n > (n+1)²
>
> und unser beweis is komplett.
>
> Hoffe ich konnte weiterhelen (und es simmt so).
>     

Ist im Prinzip korrekt. Der Beweis besteht ja eigentlich aus zwei Teilen 
(wo würde ich ihn machen):

1 Behauptung. n^2 >= 2n+1
Bew: Induktionsbasis (IB): n=3: Aussage korrekt
     Induktionsvorraussetzung (IV): Aussage stimmt bis n (n^2 >= 2n+1)
     Induktionsschritt (IS): Wir müssen zeigen, dass die Gleichung auch 
für n+1 gilt.
   (n+1)^2 = n^2+2n+1 >= 2n+1 + 2n+1 = 2n+2 +2n >= 2n+2 + 1 = 2*(n+1) +1
             ~~~      ^^ ~~~~                ~~ ^^        ~
                      IV                   gilt für jedes n>0, n aus N.

=> 1.Beh. gilt auch für n+1 und daher für jede natürliche Zahl >=3.

2. Behauptung. 2^n > n^2
Bew: IB: n=5: Aussage korrekt
     IV: Aussage stimmt bin n (2^n > n^2)
     IS: zu zeigen: Aussage stimmt für n+1.
     2^(n+1) = 2*2^n > 2*n^2 = n^2 + n^2 >= n^2 + 2n+1 = (n+1)^2
                 ~~~ ^^  ~~~         ~~~ ^^       ~~~~
                     IV                   1.

=> 2.Beh. gilt auch für n+1 und damit für jede natürliche Zahl >=5.


Vielleicht ist nun die scheinbar willkürliche Wahl etwas klarer geworden.

MfG Reinhard