starke vollständige induktion < Induktion < eindimensional < reell < Analysis < Hochschule < Mathe < Vorhilfe
|
| Status: |
(Frage) beantwortet  | | Datum: | 17:14 So 02.11.2008 | | Autor: | Peano08 |
| Aufgabe | Sei f:N-->N definiert durch
[mm] f(n):=\left\{\begin{matrix}
1, & \mbox{falls }n\mbox{ =1} \\
4*f(n/2), & \mbox{falls }n\mbox{ gerade} \\
f(n-1)+2*n-1, & \mbox{sonst. }
\end{matrix}\right. [/mm]
Finden Sie eine geschlossene Form für f(n) und beweisen Sie deren Richtigkeit mittels starker vollständiger Induktion. |
Also die geschlossene Form ist [mm] f(n)=n^2, [/mm] und wenn ich das mit vollst. Induktion versuche, gelingt mir auch der Beweis:
I.A. n=1: 1^=1
I.V. [mm] n^2=4*(n/2)^2 [/mm] (gerade) und [mm] n^2=(n-1)^2+2n-1 [/mm] (sonst)
I.S. ist trivial.... (zuviel schreibarbeit)
Meine Frage ist jetzt, ist das dann schon die starke vollst. Induktion, oder wie muss ich den I.A., I.V., I.S. wählen, damit ich das hinkriege?
Ich hab nämlich grad mal garkeine Idee.
Ich habe diese Frage in keinem Forum auf anderen Internetseiten gestellt.
Peano
|
|
| |
|
| Status: |
(Antwort) fertig  | | Datum: | 18:16 So 02.11.2008 | | Autor: | pelzig |
Bei der starken vollst. Induktion darfst du in der Induktionsvorraussetzung verlangen, dass die Behauptung für alle [mm] $k\red{\le} [/mm] n$ (anstatt nur für $k=n$, wie bei der "normalen Induktion").
Alles was man mit normaler Induktion beweisen kann, kann man also auch mit starker Induktion beweisen (m.a.W.: Das Prinzip der starken Induktion folgt aus dem (normalen) Induktionsprinzip). Also bist du im Grunde fertig 
Gruß, Robert
|
|
|
| |
|
| Status: |
(Frage) überfällig  | | Datum: | 19:03 So 02.11.2008 | | Autor: | Peano08 |
gut, dass ist ja dann nicht mehr so schwer...
muss ich denn dann zwei induktionen machen und den 1. fall im i.A. verwenden, oder krieg ich das auch zusammen gelöst?
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig  | | Datum: | 19:36 Di 04.11.2008 | | Autor: | matux |
$MATUXTEXT(ueberfaellige_frage)
|
|
|
|
