Vollständige Induktion < Induktion < eindimensional < reell < Analysis < Hochschule < Mathe < Vorhilfe
|
| Aufgabe | Sei die Folge [mm] $g(n)\!\$ [/mm] gegeben durch:
$g(0) = [mm] 5\!\$
[/mm]
$g(n+1) = 2*g(n)+3$
Das heißt: $g(1) = 13, g(2) = 29, g(3) = [mm] 61\!\$
[/mm]
Diese Folgengleichung kann auch so geschrieben werden, dass jeder Wert direkt berechnet werden kann. Finden Sie die beiden Konstanten, durch die die Gleichung vervollständigt wird und beweisen Sie die Gültigkeit mittels vollständiger Induktion (Idealerweise ergeben sich die Konstanten während der Induktion, aber es ist auch möglich, sie vorher anzugeben und dann ihre Gültigkeit zu zeigen):
[mm] $g(n)=\Box [/mm] * [mm] 2^{(n+1)}-\Box$ [/mm] |
Hallo,
ich habe mich durch diese Aufgabe leider ins Bockshorn jagen lassen und benötige jetzt Hilfe.
Zunächst habe ich die Gleichung erraten: $g(n)=4 * [mm] 2^{(n+1)}-3$. [/mm] Dann:
Induktionsanfang n=0: [mm] $g(0)=4*2^{(0+1)}-3=4*2-3=8-3=5$
[/mm]
Induktionsschritt: $n [mm] \mapsto [/mm] n+1$
Induktionsvoraussetzung: Für alle $n [mm] \in \IN$ [/mm] gilt $g(n)=4 [mm] \cdot{} 2^{(n+1)}-3$
[/mm]
Beweis:
[mm] $g(n+1)=4*2^{((n+1)+1)}-3$
[/mm]
[mm] $=4*2^{(n+2)}-3$
[/mm]
[mm] $=4*2^{n}*2^{2}-3$
[/mm]
[mm] $=16*2^{n}-3$
[/mm]
[mm] $=8*2^{(n+1)}-3$
[/mm]
Das scheint zwar zu stimmen, aber ich bin mir unsicher, ob die vollständige Induktion hier so in Ordnung ist und nicht-"idealerweise" haben sich bei mir die Konstanten auch nicht während der Induktion ergeben...
Wäre nett, wenn jemand kurz Zeit für ein Feedback hätte.
Vielen Dank!
Gruß
el_grecco
|
|
| |
|
| Status: |
(Antwort) fertig  | | Datum: | 19:35 Do 20.09.2012 | | Autor: | Marcel |
Hallo,
> Sei die Folge [mm]g(n)\!\[/mm] gegeben durch:
>
> [mm]g(0) = 5\!\[/mm]
> [mm]g(n+1) = 2*g(n)+3[/mm]
>
> Das heißt: [mm]g(1) = 13, g(2) = 29, g(3) = 61\!\[/mm]
>
> Diese Folgengleichung kann auch so geschrieben werden, dass
> jeder Wert direkt berechnet werden kann. Finden Sie die
> beiden Konstanten, durch die die Gleichung vervollständigt
> wird und beweisen Sie die Gültigkeit mittels
> vollständiger Induktion (Idealerweise ergeben sich die
> Konstanten während der Induktion, aber es ist auch
> möglich, sie vorher anzugeben und dann ihre Gültigkeit zu
> zeigen):
>
> [mm]g(n)=\Box * 2^{(n+1)}-\Box[/mm]
> Hallo,
>
> ich habe mich durch diese Aufgabe leider ins Bockshorn
> jagen lassen und benötige jetzt Hilfe.
>
>
> Zunächst habe ich die Gleichung erraten: [mm]g(n)=4 * 2^{(n+1)}-3[/mm].
> Dann:
>
> Induktionsanfang n=0: [mm]g(0)=4*2^{(0+1)}-3=4*2-3=8-3=5[/mm]
>
> Induktionsschritt: [mm]n \mapsto n+1[/mm]
>
> Induktionsvoraussetzung: Für alle [mm]n \in \IN[/mm] gilt [mm]g(n)=4 \cdot{} 2^{(n+1)}-3[/mm]
>
> Beweis:
>
> [mm]g(n+1)=4*2^{((n+1)+1)}-3[/mm]
Edit: das ist doch das, was Du am Ende des Induktionsbeweises raushaben sollst!!
Du musst hier "die Induktionsannahme verbraten":
Nach Voraussetzung wissen wir ja
$$g(n+1)=2*g(n)+3$$
und die zu verbratene Induktionsannahme ist
[mm] $$g(n)=4*2^{n+1}-3\,,$$
[/mm]
und durch Umformungen sollst Du dann am Ende zu
[mm] $$=4*2^{((n+1)+1)}-3$$
[/mm]
gelangen. Wenn das getan, dann ist der Induktionsbeweis gelungen!
(Den Induktionsanfang hast Du ja schon - das darf man nicht vergessen!!)
Du hast das aber nirgends getan? Ich meine, wenn ich behaupte, dass
das, was rauskommen soll, rauskommt, ist das kein Beweis, dass das,
was rauskommen soll, auch rauskommt!!
> [mm]=4*2^{(n+2)}-3[/mm]
>
> [mm]=4*2^{n}*2^{2}-3[/mm]
>
> [mm]=16*2^{n}-3[/mm]
>
> [mm]=8*2^{(n+1)}-3[/mm]
>
>
> Das scheint zwar zu stimmen, aber ich bin mir unsicher, ob
> die vollständige Induktion hier so in Ordnung ist und
> nicht-"idealerweise" haben sich bei mir die Konstanten auch
> nicht während der Induktion ergeben...
>
> Wäre nett, wenn jemand kurz Zeit für ein Feedback
> hätte.
am Ende hättest Du besser noch
[mm] $$=8*2^{(n+1)}-3=\red{4}*2^{n+\red{2}}-3$$
[/mm]
da stehen, aber ansonsten scheint mir das Okay.
Du hast die Konstanten doch vorher bestimmt - raten braucht man auch
dann nicht wirklich, denn wenn [mm] $g(n)=a*2^{n+1}-b$ [/mm] sein soll, und Du
[mm] $g(0)=5\,$ [/mm] und [mm] $g(1)=13\,$ [/mm] weißt, wirst Du alleine damit doch schon
notwendige Bedingungen an [mm] $a\,$ [/mm] und [mm] $b\,$ [/mm] erhalten.
Was hier vermutlich gemeint war mit "idealerweise ergeben sich
die Konstanten während der Induktion":
Sei mal [mm] $g(n+1)=2*g(n)+3\,,$ [/mm] und wir nehmen an, es wäre
[mm] $$g(n)=a*2^{n+1}-b\,.$$ [/mm]
Im Induktionsschritt steht dann ja
$$g(n+1)=2*g(n)+3$$
und dort kann man [mm] $g(n)=a*2^{n+1}-b$ [/mm] einsetzen
[mm] $$g(n+1)=2*(a*2^{n+1}-b)+3$$
[/mm]
[mm] $$\gdw g(n+1)=a*2^{n+2}+3-2b\,.$$
[/mm]
Weiter wollen wir aber auch
[mm] $$g(n+1)\stackrel{!}{=}a*2^{n+2}-b$$
[/mm]
als Ergebnis des Induktionsschrittes haben.
Das geht genau dann nur, wenn [mm] $3-2b=-b\,,$ [/mm] also wenn [mm] $b=3\,$ [/mm] ist.
Und wie man dann [mm] $a\,$ [/mm] bestimmen würde, ist Dir sicher klar: Man weiß
ja nun
[mm] $$g(0)=a*2^1-b=a*2^1-3$$
[/mm]
und das soll
[mm] $$\stackrel{!}{=}5$$
[/mm]
sein.
Nebenbei:
Auch, wenn geübte Leute "die Konstanten während des Prozesses des
Induktionsbeweises finden", finde ich es dennoch sinnvoller, egal, auf
welchem Wege man sie nun gefunden hat, DANACH nochmal mit den
konkreten Konstanten den Induktionsbeweis so zu führen, wie Du es
getan hast. (Oder sollen wir besser sagen: "Wie Du es tun wolltest"?!)
Die Gefahr, dass man andernfalls etwas übersieht (z.B. das
man nur notwendige Bedingungen gefunden hat, und einfach nicht prüft,
ob die auch wirklich hinreichend sind!), ist andernfalls nämlich nicht gerade
klein.
Also generell bei solchen Aufgaben: Wenn man so weit ist, dass man (mit
konkreten Parametern) eine Behauptung nun glaubt, beweisen zu können,
den Induktionsbeweis so führen, wie Du es tun wolltest - diese obige Idee
eines "konstruktiven Induktionsbeweises" birgt vermeidbare Gefahren -
so ein "konstruktiver Induktionsbeweis" ist m.E. nach auch nicht wirklich
ideal, wie hier behauptet wird, sondern eher suboptimal!
P.S.
Eventuell ergänzend zu obigem Edit:
Man kann auch sagen, dass man im Induktionsbeweis
[mm] $$g(n+1)=4*2^{n+2}-3$$
[/mm]
zu zeigen hat, dann wie oben bei Dir umformen und gelangt dann zu
[mm] $$g(n+1)=8*2^{(n+1)}-3$$
[/mm]
Aber damit bist Du dann auch nicht fertig, es wäre noch
[mm] $$=2*(4*2^{n+1}-3)+3$$
[/mm]
zu schreiben - und wie wird man dann fertig? Naja: Man muss ja auch bei
dieser Vorgehensweise die Induktionsannahme noch irgendwie mit
einfließen lassen...
Gruß,
Marcel
|
|
|
| |
|
Hallo Marcel,
erstmal ein großes DANKE für Deine ausführliche und saubere Ausführung!
Jetzt sollte es stimmen:
$g(0) = [mm] 5\!\$
[/mm]
$g(n+1) = [mm] 2\cdot{}g(n)+3$
[/mm]
[mm] $g(n)=4*2^{(n+1)}-3$
[/mm]
Induktionsanfang n=0: [mm] $g(0)=4\cdot{}2^{(0+1)}-3=4\cdot{}2-3=8-3=5$
[/mm]
Induktionsschritt: $n [mm] \mapsto [/mm] n+1$
Induktionsvoraussetzung: Für alle $ n [mm] \in \IN [/mm] $ gilt $ g(n)=4 [mm] \cdot{} 2^{(n+1)}-3 [/mm] $
Zu zeigen: [mm] $g(n+1)=4*2^{((n+1)+1)}-3$
[/mm]
Beweis:
$ g(n+1)=2*g(n)+3$
[mm] $=2*(4*2^{(n+1)}-3)+3$
[/mm]
[mm] $=4*2^{((n+1)+1)}-6+3$
[/mm]
[mm] $=4*2^{((n+1)+1)}-3$
[/mm]
Ich ärgere mich auf jeden Fall in Grund und Boden. Das waren in der Klausur quasi geschenkte Punkte, von denen ich viele liegen gelassen habe. ![[anon]](/images/smileys/anon.png "[anon]")
Im Wintersemester klappt das mit den Klausuren quasi wie von selbst und im Sommersemester ist es wie verhext: trotz deutlich mehr Lerneinsatz gibt es viele Enttäuschungen.
Naja mal sehen wie es in der Nachholklausur demnächst klappen wird.
Vielen Dank nochmal!
Gruß
el_grecco
|
|
|
| |
|
| Status: |
(Antwort) fertig | | Datum: | 21:29 Do 20.09.2012 | | Autor: | Marcel |
Hallo,
> Hallo Marcel,
>
> erstmal ein großes DANKE für Deine ausführliche und
> saubere Ausführung!
> Jetzt sollte es stimmen:
>
>
> [mm]g(0) = 5\!\[/mm]
> [mm]g(n+1) = 2\cdot{}g(n)+3[/mm]
Behauptung (und später auch Induktionsannahme)
> [mm]g(n)=4*2^{(n+1)}-3[/mm]
(für alle $n [mm] \in \IN_0$).
[/mm]
> Induktionsanfang n=0:
> [mm]g(0)=4\cdot{}2^{(0+1)}-3=4\cdot{}2-3=8-3=5[/mm]
>
> Induktionsschritt: [mm]n \mapsto n+1[/mm]
>
> Induktionsvoraussetzung: Für alle [mm]n \in \IN[/mm] gilt [mm]g(n)=4 \cdot{} 2^{(n+1)}-3[/mm]
>
> Zu zeigen: [mm]g(n+1)=4*2^{((n+1)+1)}-3[/mm]
>
> Beweis:
>
> [mm]g(n+1)=2*g(n)+3[/mm]
(dies gilt nach Definition von [mm] $g\,$)
[/mm]
> [mm]=2*(4*2^{(n+1)}-3)+3[/mm]
(dies folgt aus der Induktionsannahme)
> [mm]=4*2^{((n+1)+1)}-6+3[/mm]
>
> [mm]=4*2^{((n+1)+1)}-3[/mm]
>
![[ok]](/images/smileys/ok.gif "[ok]")
> Ich ärgere mich auf jeden Fall in Grund und Boden. Das
> waren in der Klausur quasi geschenkte Punkte, von denen ich
> viele liegen gelassen habe.
Na, hoffentlich wirkt sich das nicht allzu arg aus!
> Im Wintersemester klappt das mit den Klausuren quasi wie
> von selbst und im Sommersemester ist es wie verhext: trotz
> deutlich mehr Lerneinsatz gibt es viele Enttäuschungen.
Anscheinend musst Du immer im Sommersemester ein Urlaubssemester
einschieben. 
Neee, komisch, ich weiß nicht, woran das bei Dir liegt. Zu heiß war der
Sommer ja nun auch nicht, sonst würde ich "Konzentrationsschwächen"
erklären können...
> Naja mal sehen wie es in der Nachholklausur demnächst
> klappen wird.
Uh, okay, d.h. die Klausur ging daneben? Aber solange die Nachholklausur
ja im oder nahe des Winter(s) geschrieben wird...
> Vielen Dank nochmal!
Na gerne, kein Thema! 
Viel Erfolg bei Deinen Klausuren schonmal vorweg!!
Gruß,
Marcel
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig  | | Datum: | 21:47 Do 20.09.2012 | | Autor: | el_grecco |
Hallo Marcel,
Danke, jetzt sollte ich es hoffentlich begriffen haben (wird sich in der Klausur zeigen).
> > Ich ärgere mich auf jeden Fall in Grund und Boden. Das
> > waren in der Klausur quasi geschenkte Punkte, von denen ich
> > viele liegen gelassen habe.
>
> Na, hoffentlich wirkt sich das nicht allzu arg aus!
>
> > Im Wintersemester klappt das mit den Klausuren quasi wie
> > von selbst und im Sommersemester ist es wie verhext: trotz
> > deutlich mehr Lerneinsatz gibt es viele Enttäuschungen.
>
> Anscheinend musst Du immer im Sommersemester ein
> Urlaubssemester
> einschieben.
> Neee, komisch, ich weiß nicht, woran das bei Dir liegt.
> Zu heiß war der
> Sommer ja nun auch nicht, sonst würde ich
> "Konzentrationsschwächen"
> erklären können...
>
Kein Witz: es ist wirklich wie verhext.
Ich hatte gehofft, dass dieses "Phänomen" wenigstens kurz vor dem Abschluss des Studiums nicht mehr auftreten wird, aber weit gefehlt...
> > Naja mal sehen wie es in der Nachholklausur demnächst
> > klappen wird.
>
> Uh, okay, d.h. die Klausur ging daneben? Aber solange die
> Nachholklausur
> ja im oder nahe des Winter(s) geschrieben wird...
Leider knapp nicht bestanden und genau die Punkte, die ich bei dieser Aufgabe liegen gelassen habe, haben mir am Ende gefehlt. Sollte ich noch einen Master dranhängen, probiere ich im Sommersemester mal die Strategie "Zu wenig ist immer noch zu viel!", selbst wenn sich dieses "Phänomen" wieder zeigen sollte, kann ich es wenigstens auf mangelnden Fleiß schieben...
> > Vielen Dank nochmal!
>
> Na gerne, kein Thema!
>
> Viel Erfolg bei Deinen Klausuren schonmal vorweg!!
>
Danke!
> Gruß,
> Marcel
Gruß
el_grecco
|
|
|
|
