Abbildungen/Rekursion < Sonstiges < Hochschule < Mathe < Vorhilfe
|
| Aufgabe | Die Abbildungen [mm]f,g: \IN_0 \to \IN_0[/mm] seien folgendermaßen definiert:
[mm] f(0) =0, f(1) = 1, f(n) = 3f(n-1) - 2f(n-2)[/mm] für alle [mm] n \ge 2[/mm], bzw.
[mm] g(0) = 0, g(n) = g(n-1) + 2^{n-1}[/mm] für alle [mm] n \ge 1.[/mm]
Zeigen Sie, dass [mm]f = g[/mm] gilt, d.h. beide Rekursionsvorschriften stellen dieselbe Funktion dar.
Geben Sie eine explizite Formel für [mm]f(n)[/mm] an, d.h. eine Funktionsvorschrift, die nicht rekursiv
definiert ist. |
Verdammt!
Ich sitz hier seit ca. 1 Stunde und was einfach nicht was ich tun soll? Jemand der mir einen anstupser in die richtige Richtung geben kann?
Was ist an Wissen vorrausgesetzt, schaue mir grad Rekursion und Abbildungen genauer an in meinem Buch.
Ich geh erstmal davon aus das ich f=g setzen muss also die beiden Vorschriften erstmal aufschreiben auf beiden Seiten. Geht es um eine Äquivalenzrelation oder was soll das ganze?
|
|
| |
|
| Status: |
(Antwort) fertig  | | Datum: | 21:39 Do 04.11.2010 | | Autor: | abakus |
> Die Abbildungen [mm]f,g: \IN_0 \to \IN_0[/mm] seien folgendermaßen
> definiert:
> [mm]f(0) =0, f(1) = 1, f(n) = 3f(n-1) - 2f(n-2)[/mm] für alle [mm]n \ge 2[/mm],
> bzw.
> [mm]g(0) = 0, g(n) = g(n-1) + 2^{n-1}[/mm] für alle [mm]n \ge 1.[/mm]
>
> Zeigen Sie, dass [mm]f = g[/mm] gilt, d.h. beide
Also muss f(0)=g(0) gelten (das tut es),
außerdem f(1)=g(1) (tut es das?),
und letztendlich müsste
f(n) =g(n) sein.
Nun gilt
g(n)=g(n-1) + [mm] 2^{n-1}
[/mm]
und
f(n) = 3f(n-1) - 2f(n-2)
Letzteres kann man auseinandernehmen zu
f(n)= f(n-1)+2f(n-1)-2f(n-2)
Zu zeigen wäre (wegen f(n)=g(n)) also die Übereinstimmung der hinteren Teile.
Weise nach, dass [mm] 2f(n-1)-2f(n-2)=2^{n-1} [/mm] gilt.
Gruß Abakus
> Rekursionsvorschriften stellen dieselbe Funktion dar.
> Geben Sie eine explizite Formel für [mm]f(n)[/mm] an, d.h. eine
> Funktionsvorschrift, die nicht rekursiv
> definiert ist.
> Verdammt!
>
> Ich sitz hier seit ca. 1 Stunde und was einfach nicht was
> ich tun soll? Jemand der mir einen anstupser in die
> richtige Richtung geben kann?
>
> Was ist an Wissen vorrausgesetzt, schaue mir grad Rekursion
> und Abbildungen genauer an in meinem Buch.
>
> Ich geh erstmal davon aus das ich f=g setzen muss also die
> beiden Vorschriften erstmal aufschreiben auf beiden Seiten.
> Geht es um eine Äquivalenzrelation oder was soll das
> ganze?
>
|
|
|
| |
|
f(n) = 3f(n-1) - 2f(n-2)
Letzteres kann man auseinandernehmen zu
f(n)= f(n-1)+2f(n-1)-2f(n-2)
Kannst du darauf nochmal eingehen? Versteh den Schritt nicht!
|
|
|
| |
|
| Status: |
(Antwort) fertig | | Datum: | 12:16 Sa 06.11.2010 | | Autor: | abakus |
> f(n) = 3f(n-1) - 2f(n-2)
> Letzteres kann man auseinandernehmen zu
> f(n)= f(n-1)+2f(n-1)-2f(n-2)
>
>
>
> Kannst du darauf nochmal eingehen? Versteh den Schritt
> nicht!
Hallo,
ich habe lediglich
3*f(n-1)
zerlegt in
1*f(n-1) + 2*f(n-1)
Gruß Abakus
|
|
|
| |
|
| Status: |
(Frage) beantwortet  | | Datum: | 14:09 So 07.11.2010 | | Autor: | emse88 |
Also ich sitze gerade an der gleichen Aufgabe.
Ich weiß zwar noch nicht, wie ich f=g zeige, ich habe
aber schonmal ne Vorschrift ohne Rekursion gefunden.
Ist h(x) = 2*(2^(x-1))-1 korrekt? Bis x=5 stimmt es überein.
|
|
|
| |
|
> Also ich sitze gerade an der gleichen Aufgabe.
> Ich weiß zwar noch nicht, wie ich f=g zeige, ich habe
> aber schonmal ne Vorschrift ohne Rekursion gefunden.
>
> Ist h(x) = 2*(2^(x-1))-1 korrekt? Bis x=5 stimmt es
> überein.
Hallo,
![[willkommenmr]](/images/smileys/willkommenmr.png "[willkommenmr]") .
Deine Vorschrift stimmt, es ist [mm] h(n)=2^n-1.
[/mm]
Beweise jetzt per Induktion [mm] f(n)=2^n-1, g(n)=2^n-1.
[/mm]
Dann müssen ide Funktionen ja wohl oder übel gleich sein..
Gruß v. Angela
|
|
|
| |
|
| Status: |
(Frage) beantwortet | | Datum: | 18:48 So 07.11.2010 | | Autor: | emse88 |
Also ich weißb zwar, wie eine vollst. Induktion geht, habe dies aber bis jetzt nur mit Folgen gemacht. Wie muss ich die Induktion im I.S. aufbauen, wenn ich auf der linken Seite eine rekursive Abbildung habe und rechts dann eben [mm] (2^n)-1?
[/mm]
|
|
|
| |
|
> Also ich weißb zwar, wie eine vollst. Induktion geht, habe
> dies aber bis jetzt nur mit Folgen gemacht.
Hallo,
dann liegst Du mit dieser Aufgabe goldrichtig!
f und g bilden doch beide aus den natürlichen Zahlen heraus ab - nichts anderes sind Folgen: Abbildungen aus dem [mm] \IN [/mm] in eine andere Menge.
Wenn's Dir besser bekömlich ist, kannst Du auch schreiben [mm] a_n:=f(n) [/mm] und [mm] b_n:=g(n), [/mm] und ziehst dann das Ding durch.
> Wie muss ich
> die Induktion im I.S. aufbauen, wenn ich auf der linken
> Seite eine rekursive Abbildung habe und rechts dann eben
> [mm](2^n)-1?[/mm]
Genauso, wie Du es kennst:
Induktionsbehauptung: es ist [mm] f(n+1)=2^{n+1}-1.
[/mm]
Beweis:
f(n+1)=3f(n)-2f(n) [mm] \qquad [/mm] (Rekursion)
= ... - ... [mm] \qquad [/mm] (Induktionsannahme)
= ...
Gruß v. Angela
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig  | | Datum: | 20:26 So 07.11.2010 | | Autor: | emse88 |
Danke, habe es jetzt hinbekommen. Man muss bei der Umformung einmal ziemlich um die Ecke denken, aber wenn mans hat, ist es einfach, wie immer. ^.^
|
|
|
| |
|
| Status: |
(Frage) beantwortet | | Datum: | 20:28 So 07.11.2010 | | Autor: | Rudy |
O.O wie hast du es gelöst???
Ich hab es immernoch nicht geschaft.
|
|
|
| |
|
>
> O.O wie hast du es gelöst???
> Ich hab es immernoch nicht geschaft.
Hallo,
vielleicht zeigst Du mal, wie weit Deine Induktion gediehen ist und an welcher Stelle genau Du hängst.
Gruß v. Angela
|
|
|
| |
|
| Status: |
(Frage) reagiert/warte auf Reaktion  | | Datum: | 21:54 So 07.11.2010 | | Autor: | Blackpearl |
die letzten beiden schritte die du mit "...." angedeutet hast, kannst du mir dazu mal weiterhelfen?
was setze ich jetzt für das k ein also den laufindex in der induktion? was mach ich ausserdem mit dem f?
|
|
|
| |
|
> die letzten beiden schritte die du mit "...." angedeutet
> hast, kannst du mir dazu mal weiterhelfen?
Hallo,
dann bereite alles vor, damit man Dir gut weiterhelfen kann.
Es war f wie definiert?
Diezu zeigende Aussage ist welche?
BEWEIS (durch Induktion)
Induktionsanfang: ...
Induktionsannahme: Es sei ... für ...
Induktionsbehauptung: Dann gilt ...
Beweis: Es ist f(n+1)= ...
Gruß v. Angela
>
> was setze ich jetzt für das k ein also den laufindex in
> der induktion? was mach ich ausserdem mit dem f?
|
|
|
| |
|
f war definiert als
[mm] f = 2^n -1[/mm]
die zu zeigende behauptung ist:
[mm] f(n+1)=3f(n) -2f(n)[/mm]
aber auf die vollstaendige induktion komm ich nicht klar ich weiss einfach garnicht was ich da tun soll
|
|
|
| |
|
> f war definiert als
> [mm]f\red{ (n)}= 2^n -1[/mm]
>
> die zu zeigende behauptung ist:
> [mm]f(n+1)=3f(n) -2f(n\red{-1})[/mm]
EDIT: Nein! f war definiert (!) durch f(0):=0, f(1):=1, f(n):=3f(n-1)-2f(n-2).
Da gibt's nix zu zeigen.
Zu zeigen ist, daß [mm] f(n)=2^n-1 [/mm] richtig ist.
>
> aber auf die vollstaendige induktion komm ich nicht klar
> ich weiss einfach garnicht was ich da tun soll
Hallo,
dann nimm Dir jetzt erstmal ein schlaues Buch o.ä., lies Dich schlauer und starte einen Versuch. Bei  Induktion müßte es auch erklärt sein.
Gruß v. Angela
|
|
|
| |
|
ok dann mal zum induktionsanfang.. der stimmt doch dann nichmehr?
bei n=1 z.B.:
f(1+1)= 3f(1) - 2f(1)
2 = 1 (f) ???
|
|
|
| |
|
> ok dann mal zum induktionsanfang.. der stimmt doch dann
> nichmehr?
Hallo,
Du willst doch die Behauptung [mm] f(n)=2^n-1 [/mm] beweisen.
f(n)=3f(n-1) - 2f(n-2) ist nichts, was man beweisen muß, sondern Teil der Definition der Funktion/Folge.
Schreib Dir doch mal die ersten 10 Funktionswerte auf, damit Du kapierst, was eine rekursiv definierte Funktion ist.
Die zu beweisende Behauptung ist also [mm] f(n)=2^n-1.
[/mm]
In Induktionsanfang mußt Du also vorrechnen, daß [mm] f(1)=2^1-1 [/mm] richtig ist.
f(1) entnimmst Du der Definition von f, [mm] 2^1-1 [/mm] rechnest Du aus.
Dann mach weiter mit Induktionsannahme usw.
Gruß v. Angela
|
|
|
| |
|
> Die Abbildungen [mm]f,g: \IN_0 \to \IN_0[/mm] seien folgendermaßen
> definiert:
> [mm]f(0) =0, f(1) = 1, f(n) = 3f(n-1) - 2f(n-2)[/mm] für alle [mm]n \ge 2[/mm],
> bzw.
> [mm]g(0) = 0, g(n) = g(n-1) + 2^{n-1}[/mm] für alle [mm]n \ge 1.[/mm]
>
> Zeigen Sie, dass [mm]f = g[/mm] gilt, d.h. beide
> Rekursionsvorschriften stellen dieselbe Funktion dar.
> Geben Sie eine explizite Formel für [mm]f(n)[/mm] an, d.h. eine
> Funktionsvorschrift, die nicht rekursiv
> definiert ist.
Hallo,
es sind hier zwei Funktionen rekursiv angegeben, dh. es wird gesagt, wie man einen Funktionswert jeweils durch Rückgriff auf vorhergehende Funktionswerte berechnen kann.
Mein Vorschlag: such' erstmal die explzite Funktionsvorschrift.
(Explizite Vorschift ist sawas wie [mm] h(x):=x^2+5 [/mm] oder [mm] h(x):=sin(3x)+e^{4711\wurzel{2}}
[/mm]
Diese Vorschrift findet man hier recht leicht.
Rechne einfach mal die ersten 10 Funktionswerte von f aus.
f(0)=0
f(1)=1
f(2)=...
[mm] \vdots
[/mm]
Nun schöpfe einen Verdacht, wie die Funktionsvorschrift lautet: f(n):=...
Beweise diese Formel nun duch vollständige Induktion.
Beweise dann duch vollständige Induktion, daß g(n) dieselbe explizite Darstellung hat.
Gruß v. Angela
|
|
|
| |
|
| Status: |
(Antwort) fertig | | Datum: | 06:43 Mo 08.11.2010 | | Autor: | felixf |
Moin!
> Die Abbildungen [mm]f,g: \IN_0 \to \IN_0[/mm] seien folgendermaßen
> definiert:
> [mm]f(0) =0, f(1) = 1, f(n) = 3f(n-1) - 2f(n-2)[/mm] für alle [mm]n \ge 2[/mm],
> bzw.
> [mm]g(0) = 0, g(n) = g(n-1) + 2^{n-1}[/mm] für alle [mm]n \ge 1.[/mm]
>
> Zeigen Sie, dass [mm]f = g[/mm] gilt, d.h. beide
> Rekursionsvorschriften stellen dieselbe Funktion dar.
> Geben Sie eine explizite Formel für [mm]f(n)[/mm] an, d.h. eine
> Funktionsvorschrift, die nicht rekursiv
> definiert ist.
> Verdammt!
>
> Ich sitz hier seit ca. 1 Stunde und was einfach nicht was
> ich tun soll? Jemand der mir einen anstupser in die
> richtige Richtung geben kann?
Gleichheit zeigt man schnell per Induktion:
Gilt die Behauptung fuer alle $n' < n$, so ist $f(n) = 3 f(n - 1) - 2 f(n - 2) = 3 g(n - 1) - 2 g(n - 2) = 3 g(n - 2) + 3 [mm] \cdot 2^{n-2} [/mm] - 2 g(n - 2) = g(n - 2) + [mm] 2^{n - 2} [/mm] + 2 [mm] \cdot 2^{n-2} [/mm] = g(n - 1) + [mm] 2^{n-1} [/mm] = g(n)$.
Und die Formel leitet man via $g(n)$ her: es ist $g(n) = g(n - 1) + [mm] 2^{n-1} [/mm] = g(n - 2) + [mm] 2^{n-2} [/mm] + [mm] 2^{n-1} [/mm] = [mm] \dots [/mm] = 0 + [mm] 2^0 [/mm] + [mm] 2^1 [/mm] + [mm] \dots [/mm] + [mm] 2^{n-1} [/mm] = [mm] \sum_{k=0}^{n-1} 2^k$.
[/mm]
Nach der geometrischen Summenformel ist das gleich [mm] $\frac{2^n - 1}{2 - 1} [/mm] = [mm] 2^n [/mm] - 1$.
LG Felix
|
|
|
| |
|
| Status: |
(Frage) beantwortet | | Datum: | 01:00 Do 11.11.2010 | | Autor: | jikz |
Hallo!
Wäre es möglich, dass Du diesen Ausdruck:
> Gilt die Behauptung fuer alle [mm]n' < n[/mm], so ist [mm]f(n) = 3 f(n - 1) - 2 f(n - 2) = 3 g(n - 1) - 2 g(n - 2) = 3 g(n - 2) + 3 \cdot 2^{n-2} - 2 g(n - 2) = g(n - 2) + 2^{n - 2} + 2 \cdot 2^{n-2} = g(n - 1) + 2^{n-1} = g(n)[/mm].
noch einmal erläuterst und inwiefern das etwas mit Induktion zu tun hat? Ich hab's versucht nachzuvollziehen, stehe aber irgendwie auf dem Schlauch.
Beim ersten Schritt
[mm]f(n) = 3 f(n - 1) - 2 f(n - 2) = 3 g(n - 1) - 2 g(n - 2)[/mm]
dachte ich mir, dass davon ausgegangen wird, dass f(n) = g(n), also ist es logisch, dass die f funktion durch die g funktion getauscht werden kann.
Beim nächsten Schritt versteh ich aber nicht mehr ganz was die Absicht war? geht es um einen Induktionsschritt von n-2 auf n-1?
[mm]3 g(n - 2) + 3 \cdot 2^{n-2} - 2 g(n - 2)[/mm]
Wie entsteht das [mm]3 \cdot 2^{n-2}[/mm]?
Es wäre toll, wenn Du da noch einmal etwas ausführlicher andeuten könntest, wie genau Deine Argumentation hier funktioniert.
> Nach der geometrischen Summenformel ist das gleich
> [mm]\frac{2^n - 1}{2 - 1} = 2^n - 1[/mm].
Was genau ist hier gleich? Ich meine - was hast Du in die geo. Summenformel eingesetzt und womit gleich gesetzt (bzw. aus welcher Stelle den Ausdruck genommen)?
Sorry, dass ich so grundlegende Dinge frage und grad eher wenige Zusammenhänge sehe. Ich bin jedoch sehr daran interessiert die Gedankengänge nachvollziehen zu können.
> LG Felix
>
Grüße zurück, Thomas
|
|
|
| |
|
> Hallo!
>
> Wäre es möglich, dass Du diesen Ausdruck:
>
> > Gilt die Behauptung fuer alle [mm]n' < n[/mm], so ist [mm]f(n) = 3 f(n - 1) - 2 f(n - 2) = 3 g(n - 1) - 2 g(n - 2) = 3 g(n - 2) + 3 \cdot 2^{n-2} - 2 g(n - 2) = g(n - 2) + 2^{n - 2} + 2 \cdot 2^{n-2} = g(n - 1) + 2^{n-1} = g(n)[/mm].
>
> noch einmal erläuterst und inwiefern das etwas mit
> Induktion zu tun hat? Ich hab's versucht nachzuvollziehen,
> stehe aber irgendwie auf dem Schlauch.
Hallo,
wir haben
$ f(0) =0, f(1) = 1, f(n) = 3f(n-1) - 2f(n-2) $ für alle $ n [mm] \ge [/mm] 2 $, bzw.
$ g(0) = 0, g(n) = g(n-1) + [mm] 2^{n-1} [/mm] $ für alle $ n [mm] \ge [/mm] 1. $
Das ist Definition, hier gibt es nichts zu beweisen.
Per Induktion soll nun bewiesen werden die
Beh.: f(n)=g(n) für alle [mm] n\in \IN
[/mm]
I.A.: ... paßt.
Induktionsvoraussetzung:
es sei [mm] n\in \IN, [/mm] und
es gelte f(k)=g(k) für alle [mm] 0\le k\le [/mm] n-1.
[Bem: dann gilt die Aussage insbes. für k=n-1 und k=n-2]
Induktionsschluß:
zu zeigen: dann ist auch f(n)=g(n)
Bew.
> $f(n) = 3 f(n - 1) - 2 f(n - 2)
das ist die Def. von f
> = 3 g(n - 1) - 2 g(n - 2)
Hier wird die Induktionsannahme benutzt
> = 3 g(n - 2) + 3 [mm] \cdot 2^{n-2} [/mm] - 2 g(n - 2)
Das ist die Def. von g, verwendet für g(n-1)
> = g(n - 2) + [mm] 2^{n - 2} [/mm] + 2 [mm] \cdot 2^{n-2} [/mm]
Termumformung
> = g(n - 1) + [mm] 2^{n-1} [/mm] = g(n)$.
Def. von g, verwendet für g(n-1)
>
> > Nach der geometrischen Summenformel ist das gleich
> > [mm]\frac{2^n - 1}{2 - 1} = 2^n - 1[/mm].
>
> Was genau ist hier gleich? Ich meine - was hast Du in die
> geo. Summenformel eingesetzt und womit gleich gesetzt (bzw.
> aus welcher Stelle den Ausdruck genommen)?
Ich weiß nicht, ob es Dir ganz klar ist: der Beweis für die Gleichheit von f und g ist nun abgeschlossen.
Felix' nächstes Ziel ist die Herleitung der expliziten Darstellung von g.
Er stellt fest, daß $ g(n) = [mm] \sum_{k=0}^{n-1} 2^k [/mm] $, und nutzt hierfür dann die Formel für die endl. geometr. Reihe.
> Sorry, dass ich so grundlegende Dinge frage und grad eher
> wenige Zusammenhänge sehe. Ich bin jedoch sehr daran
> interessiert die Gedankengänge nachvollziehen zu können.
Ich weiß nicht, wieviel Du gelesen hast im Thread.
Mein Lösungsvorschlag war etwas anders:
1.Experimentell eine Vermutung für die explizite Darstellung finden,
2. diese per Induktion für beiden Funktionen beweisen,
3. wenn's gelingt, müssen f und g ja gleich sein.
Gruß v. Angela
|
|
|
|
