Vollständige Induktion < Induktion < eindimensional < reell < Analysis < Hochschule < Mathe < Vorhilfe
|
| Status: |
(Frage) beantwortet  | | Datum: | 19:01 Di 16.02.2010 | | Autor: | XeZZ |
| Aufgabe | [mm] f1(k)=2f1(k-1)+3*2^{k}+4 [/mm]
f1(0)=2
[mm] f2(k)=3*2^{2k}+2^{k}-1
[/mm]
Behauptung f1(n)<f2(n) für n [mm] \ge [/mm] 2
Beweis per vollständiger Induktion über n |
So also der nächste Beweis bei dem ich in der Mitte festhänge.... (den Ind. Anfang lass ich mal weg)
Ind. Schritt:
Behauptung: [mm] 2f1(n)+3+2^{n+1}+4<3*2^{2(n+1)}+2^{n+1}-1
[/mm]
Beweis:
[mm] 2f1(n-1)+3*2^{n}+4<3*2^{2n}+2^{n}-1 [/mm] | auf der rechten seite setze ich nun für n-->n+1 ein / Auf beiden Seiten wird 1 addiert
[mm] 2f1(n-1)+3*2^{n}+5<3*2^{2(n+1)}+2^{n+1} [/mm] | Rechts 2 ausklammern
[mm] 2f1(n-1)+3*2^{n}+5<2(3*2^{2n+1}+2^{n}) [/mm] | auf der linken seite setze ich nun für n-->n+1 ein
[mm] 2(2f1(n-1)+3*2^{n}+5)+3*2^{n}+4<2(3*2^{2n+1}+2^{n}) [/mm]
So nun habe ich auf beiden seiten nen Therm mit Faktor 2 davor. Links ists der alte und rechts ists aber neu und alt vermsicht. Muss ich da nun den neuen Teil aus der Klammer ziehn um ihn mit dem neuen Teil auf der linken Seite zu vergleichen? Und wenn ja wie soll ich das anstellen :)? (Ich hoffe man versteht was ich meine ich kann das grade irgendwie nicht präzise in Worte fassen)
|
|
| |
|
| Status: |
(Antwort) fertig  | | Datum: | 19:34 Di 16.02.2010 | | Autor: | leduart |
Hallo wieder versteh ich nicht, warum du nicht mit der Ind.vors wirklich arbeitest.
Vors f1(n)<f2(n)
also [mm] $f1(n)<3\cdot{}2^{2k}+2^{k}-1 [/mm] $
daraus [mm] f1(n+1)=2f1(n)+3*2^{k+1}+4< 2*(3\cdot{}2^{2k}+2^{k}-1)
[/mm]
und den letzten Schritt machst du jetzt selbst.
irgendwie setzt du die Vors nicht richtig bzw zielstrebig ein.
Gruss leduart
|
|
|
| |
|
| Status: |
(Frage) beantwortet | | Datum: | 19:52 Di 16.02.2010 | | Autor: | XeZZ |
> Vors f1(n)<f2(n)
> also [mm]f1(n)<3\cdot{}2^{2k}+2^{k}-1[/mm]
> daraus [mm]f1(n+1)=2f1(n)+3*2^{k+1}+4< 2*(3\cdot{}2^{2k}+2^{k}-1)[/mm]
Mh ich vertseh nicht ganz was du meinst mit der Ind. Vors.
Und den Schritt dort kann ich grade garnicht nachvollziehn.
du hast ja links f(n+1) eingesetzt und auf der rehcten seite eifnach f2(n)*2. Aber ansich hast du ja nicht nur um den Faktor 2 erweitert beid em Schritt von n auf n+1 sondern noch [mm] +3*2^{k+1}+4 [/mm] dabei und das ist rechts nicht.
Versteh ich denn richtig,d ass es im prinzip nurnoch darum geht den Teil, der auf der rechten Seite durch das *2 so umzuformen, dass man eindeutig sieht, dass er [mm] >(3*2^{k+1}+4) [/mm] ist?
|
|
|
| |
|
| Status: |
(Antwort) fertig | | Datum: | 20:05 Di 16.02.2010 | | Autor: | leduart |
Hallo
du hast recht, ich hab die 2 Summanden nicht aufgeschrieben, sorry
also richtig muss es heissen:
$ [mm] f1(n+1)=2f1(n)+3\cdot{}2^{k+1}+4< 2\cdot{}(3\cdot{}2^{2k}+2^{k}-1) +3\cdot{}2^{k+1}+4$
[/mm]
hier hab ich mit [mm] 2*f1(n)<2*(3\cdot{}2^{2k}+2^{k}-1)
[/mm]
die Ind.vors eingesetzt.
nun musst du nur noch zeigen, dass das [mm] <(3\cdot{}2^{2(k+1)}+2^{k+1}-1) [/mm] ist und bist fertig.
Gruss leduart
|
|
|
| |
|
| Status: |
(Frage) beantwortet | | Datum: | 20:32 Di 16.02.2010 | | Autor: | XeZZ |
Ok danke so macht das für mich auch wieder Sinn :)
Und die Ind. vors ist die Induktionsvorraussetzung und damit die behauptung ja?
|
|
|
| |
|
Hallo,
> Ok danke so macht das für mich auch wieder Sinn :)
>
> Und die Ind. vors ist die Induktionsvorraussetzung und
> damit die behauptung ja?
Nein! Und bitte Voraussetzung nur mit einem "r"
Mit der Induktionsvoraussetzung nimmst du an (bzw. setzt du voraus), dass die zu zeigende Aussage für ein beliebiges, aber festes [mm] $n\in\IN$ [/mm] gilt.
Die (Induktions-)Behauptung ist dann, dass die Aussage auch für $n+1$ gilt:
Hier so:
Induktionsvoraussetzung (IV): Sei [mm] $n\in\IN$ [/mm] ($n>2$) beliebig, aber fest und gelte [mm] $f_1(n)
(Ind.-)Beh.: es gilt: [mm] $f_1(n+1)
Dies ist dann zu zeigen (unter Verwendung der IV)
Gruß
schachuzipus
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig  | | Datum: | 21:09 Di 16.02.2010 | | Autor: | XeZZ |
ok danke dann werd ich mal weitersehn kommen noch nen paar Beweise die nächsten tage :P
|
|
|
|
