Vollständige Induktion < Induktion < eindimensional < reell < Analysis < Hochschule < Mathe < Vorhilfe
|
| Status: |
(Frage) beantwortet  | | Datum: | 15:28 Di 04.06.2013 | | Autor: | amarus |
| Aufgabe | Eine Funktion f auf den natürlichen Zahlen sei definiert durch
f(0) = 1
f(1) = 7
f(n+1) = 3 * f(n) - 2*f(n-1) (für [mm] n\ge1)
[/mm]
Beweisen Sie folgende Aussagen:
1) f ist monoton wachsend, d.h. f(n) [mm] \le [/mm] f(n+1)
2) f(n) ist stets ungerade
3) es gilt immer [mm] f(n)\le 6*2^n [/mm] |
Ich habe leider überhaupt keine Ahnung wie ich beginnen soll :-/ die Begrifflichkeiten als solche sind mir bekannt, aber ich kann es nicht übertragen :-/
|
|
| |
|
| Status: |
(Antwort) fertig  | | Datum: | 16:16 Di 04.06.2013 | | Autor: | Marcel |
Hallo,
> Eine Funktion f auf den natürlichen Zahlen sei definiert
> durch
>
> f(0) = 1
>
> f(1) = 7
>
> f(n+1) = 3 * f(n) - 2*f(n-1) (für [mm]n\ge1)[/mm]
>
>
> Beweisen Sie folgende Aussagen:
>
> 1) f ist monoton wachsend, d.h. f(n) [mm]\le[/mm] f(n+1)
klar ist $f(1)=7 [mm] \ge 1=f(0)\,.$
[/mm]
I.V.: Sei nun $n [mm] \in \IN=\{1,2,3,...\}$ [/mm] so, dass $f(n) [mm] \le f(n+1)\,.$
[/mm]
Zu zeigen ist (Induktionsschritt): $f(n+2) [mm] \ge f(n+1)\,.$
[/mm]
Es gilt
[mm] $$f(n+2)-f(n+1)=\underbrace{3*f(n+1)-2*f(n)}_{=f(n+2)}-f(n+1)=2*(f(n+1)-f(n))\,.$$
[/mm]
Mach' mal weiter! (I.V. benutzen und die Behauptung folgern!)
> 2) f(n) ist stets ungerade
Das solltest Du hinbekommen: Für [mm] $n=0\,$ [/mm] sowie für [mm] $n=1\,$ [/mm] ist das trivial.
I.V. Sei also $n [mm] \in \IN$ [/mm] so, dass [mm] $f(k)\,$ [/mm] ungerade für alle $0 [mm] \le [/mm] k [mm] \le n\,.$
[/mm]
Induktionsschritt: Nun sind [mm] $f(n)\,$ [/mm] und $f(n-1)$ ungerade. Warum ergibt
dann
[mm] $$3*\text{ ungerade Zahl} [/mm] - [mm] 2*\text{ ungerade Zahl}$$
[/mm]
wieder eine ungerade Zahl?
> 3) es gilt immer [mm]f(n)\le 6*2^n[/mm]
> Ich habe leider überhaupt
> keine Ahnung wie ich beginnen soll
Mal wieder Induktion:
Für [mm] $n=0\,$ [/mm] bzw. [mm] $n=1\,$...
[/mm]
Gelte $f(k) [mm] \le 6*2^k$ [/mm] für alle $0 [mm] \le [/mm] k [mm] \le n\,.$ [/mm] Dann gilt insbesondere [mm] $f(n-1)\le 6*2^{n-1}$ [/mm] und $f(n) [mm] \le 6*2^n\,.$
[/mm]
Dann
$$f(n+1)=3*f(n)-2*f(n-1)=f(n)+2*(f(n)-f(n-1)) [mm] \le 6*2^n+2*(f(n)-f(n-1))$$
[/mm]
wegen der I.V..
Um den Beweis zu vervollständigen, reicht es, zu beweisen, dass
$$f(n)-f(n-1) [mm] \le 6*2^{n-1}$$
[/mm]
für alle $n [mm] \in \IN$ [/mm] gilt. (Mach' Dir das bitte klar!)
Hierbei hilft es, nochmal in die Definition zu gucken:
$$f(n+1)=3*f(n)-2*f(n-1) [mm] \iff f(n+1)-f(n)=2*(f(n)-f(n-1))\,.$$
[/mm]
Das hilft dann, um diesen Induktionsbeweis zu führen! (Tatsächlich haben
wir sogar $f(n)-f(n-1) [mm] \red{\;=\;}6*2^{n-1}$ [/mm] für alle $n [mm] \in \IN$!)
[/mm]
Gruß,
Marcel
|
|
|
| |
|
| Status: |
(Antwort) fertig | | Datum: | 16:27 Di 04.06.2013 | | Autor: | Sax |
Hi,
3. ergibt sich ganz einfach, wenn du (mit Induktion) zeigst, dass für alle n
f(n+1) = 2*f(n) + 5
gilt.
Gruß Sax.
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig  | | Datum: | 16:31 Di 04.06.2013 | | Autor: | Marcel |
Hi Sax,
> Hi,
>
> 3. ergibt sich ganz einfach, wenn du (mit Induktion)
> zeigst, dass für alle n
> f(n+1) = 2*f(n) + 5
wie ergibt sich das damit einfach? Ich hatte bei meiner ersten Antwort definitiv
einen Denkfehler drin, den ich mittlerweile korrigiert habe.
Das von Dir gesagte ist "fast" trivial:
$$f(n+1)=3*f(n)-2*f(n-1) [mm] \iff [/mm] f(n+1)-2*f(n)=f(n)-2*f(n-1)$$
zeigt die Behauptung unter Beachtung von [mm] $f(1)-2*f(0)=7-2*1=5\,.$
[/mm]
Gruß,
Marcel
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig | | Datum: | 16:49 Di 04.06.2013 | | Autor: | Sax |
Hallo Marcel,
"gnz einfach", weil sich der Induktionsschritt auf die eine Zeile
edit : alles Unsinn
$f(n+1) = 2*f(n)+5 [mm] \le 2*6*2^n [/mm] + 5 = [mm] 6*2^{n+1}+5 \le 6*2^{n+1} [/mm] $
reduziert.
richtig ist :
Aus der Darstellung, aber auch aus der in der Aufgabenstellung angegebenen lässt sich die explizite Formel f(n) = [mm] 6*2^n-5 [/mm] gewinnen und damit alle Behauptungen zeigen.
Gruß Sax.
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig | | Datum: | 19:21 Di 04.06.2013 | | Autor: | Marcel |
Hallo Sax,
> richtig ist :
>
> Aus der Darstellung, aber auch aus der in der
> Aufgabenstellung angegebenen lässt sich die explizite
> Formel f(n) = [mm]6*2^n-5[/mm] gewinnen und damit alle
damit hast Du natürlich recht. Wenn man quasi mit 3. beginnt und dann
erstmal bemerkt, dass für alle $n [mm] \in \IN$:
[/mm]
[mm] $$f(n)-f(n-1)=6*2^{n-1}$$
[/mm]
sowie
$$f(n+1)-2*f(n)=f(n)-2*f(n-1)=...=5$$
folgt natürlich
[mm] $$5=6*2^{n-1}-f(n-1)$$
[/mm]
und damit für alle $n [mm] \in \IN$
[/mm]
[mm] $$f(n-1)=6*2^{n-1}-5$$
[/mm]
bzw. für alle $n [mm] \in \IN_0$
[/mm]
[mm] $$f(n)=6*2^n-5\,.$$
[/mm]
So, wie ich den Beweis aber durchgegangen bin, übt man halt bei jedem
Schritt quasi nochmal Induktion. 
Gruß,
Marcel
|
|
|
|
