Rekursionsgleichung

Neue Frage »

Angy Auf diesen Beitrag antworten »
Rekursionsgleichung
Hallo,

ich habe folgende Rekursionsgleichung:




Anscheinend kann man diese Gleichung sowohl durch Induktionsbeweis als auch durch Vereinfachung mit Hilfe der O-Notation lösen.

Ich habe nur keine Idee wie ich das machen soll. Ich drehe mich ständig im Kreis. Kann mir jemand bitte helfen.

Gruß,
Angy
Marcyman Auf diesen Beitrag antworten »

Ist die explizite Gleichung nicht einfach f(n)=2n ? Oder worum gehts bei der Aufgabe?
Angy Auf diesen Beitrag antworten »

Zitat:
Original von Marcyman
Ist die explizite Gleichung nicht einfach f(n)=2n ? Oder worum gehts bei der Aufgabe?


Wenn ich jetzt für n Werte eintrage:











Somit gehe ich auch davon aus dass f(n) = 2n aber ich muss für die Lösung sowohl einen Induktionsbeweis als auch durch Vereinfachung mit Hilfe der O-Notation angeben. Und genau da liegt mein Problem.

Gruss,
Angy
Marcyman Auf diesen Beitrag antworten »

Keine Ahnung, was O-Notation ist. Aber mit vollständiger Induktion dürfte das doch im nu zu machen sein. Hier mal grob skizziert:

für A(n): f(n)=2n <-- IA

für A(n+1): f(n+1)=2(n+1)
<=> f(n)+2=2n+2 <-- wegen Rekursionsvorschrift
<=> 2n+2 = 2n+2 <-- wegen IA
Ben Sisko Auf diesen Beitrag antworten »

Vollständige Induktion sollte also jetzt klar sein.

O-Notation kenn ich nur die folgende: Eine Funktion f ist vom Typ o(h), wenn sie schneller als die Nullfolge h gegen Null strebt, also wenn . Das ist also "fast nix" und ich glaube mich zu erinnern, dass man es in der Rechnung tatsächlich fast wie ne Null behandelt. Oder zumindest in der Interpretation.

Ich sehe aber nicht, was das hiermit zu tun hat? verwirrt Meinst du also ne andere Notation? Wenn du dabei noch Hilfe brauchst, bitte posten!

Gruß vom Ben
Angy Auf diesen Beitrag antworten »

Hallo Leute,

ich glaube ich habe es verstanden. Hier ein anderes Beispiel:




Ich vermute, dass , somit ist

Beweis durch vollständige Induktion:

Induktionsanfang (IA): Man zeige, dass gilt






Induktionsvoraussetzung (IV): Es gelte für ein
Induktionsschluss (IS): Man schließe von n auf n+1




(*) nun kann man für per Induktionsvorrausetzung einsetzen


(**)
(**)
q.e.d

Ist es richtig bewiesen?

Eine andere Frage wenn ich anstatt den Schritt (*) einfach nach f(n) auflöse. Ist dies erlaubt? Also,



(**)


q.e.d

Ich bedanke mich schon mal für Eure Hilfe.

Gruss,
Angy


(**)Korrektur dank Ben: (oh jeh... schande über mich)
 
 
Ben Sisko Auf diesen Beitrag antworten »

Du machst einen Fehler, denn .

Ausserdem verstehe ich nicht ganz, was der Umweg über g(n) soll. Da machst du den Fehler auf beiden Seiten und merkst es deswegen gar nicht Augenzwinkern

Du kannst es einfach so beweisen:

Behauptung:

Induktionsanfang: n=0
, OK

Induktionsschritt von n nach n+1:



Gruß vom Ben
Angy Auf diesen Beitrag antworten »

Danke für den Hinweis. Ich habe es bereits korregiert.

Mal davon abgesehen ob es einen einfacheren Induktionsbeweis gibt, sind meine beide Lösungswege richtig?

Gruss,
Angy
Ben Sisko Auf diesen Beitrag antworten »

In deinem 2. Versuch hast du es ja schon ohne das g(n) gemacht. Im 1. Versuch sind die rechenschritte richtig, aber es ist immer etwas unschön, in einem Beweis auf so etwas wie 1=1 hinzuarbeiten. In deinem 2. Versuch ist es besser.

Gruß vom Ben
Angy Auf diesen Beitrag antworten »

Hi Ben,

mir ist gerade etwas aufgefallen. Du hast geschrieben:

Zitat:
Original von Ben Sisko
...
Du kannst es einfach so beweisen:

Behauptung:
...

Induktionsschritt von n nach n+1:



Gruß vom Ben


Somit wäre ja aber das widerspricht doch deiner Behauptung dass , oder nicht?
Ben Sisko Auf diesen Beitrag antworten »

Hab´s korrigiert. Kleiner Rechenfehler, bzw. Schreibfehler.

Gruß vom Ben
Neue Frage »
Antworten »



Verwandte Themen

Die Beliebtesten »
Die Größten »
Die Neuesten »