Rekursionsgleichung einsetzen (Beweis?)

Neue Frage »

mathers Auf diesen Beitrag antworten »
Rekursionsgleichung einsetzen (Beweis?)
Hallo zusammen,

wollte mal fragen, ob dieses Vorgehen erlaubt ist?

Nehmen wir an, wir haben eine Rekursionsgleichung einer Folge gegeben.

und sei gegeben.

Jetzt wollen wir - wie üblich - eine explizite Darstellung finden.
Nehmen wir dazu an, dass wir eine Vermutung haben, was in expliziter Darstellung ist.

Jetzt rechnen wir aus:
* über die explizite Darstellung
* und setzen die explizite Darstellung in die rekusive ein und prüfen ob eine wahre Aussage entsteht

Damit haben wir die Vermutung (explizite Formel) bewiesen?

Grüße!
Elvis Auf diesen Beitrag antworten »

Das hört sich nach vollständiger Induktion an. Hast du ein Beispiel, an dem wir das verifizieren können ? Übrigens bin ich nicht sicher, ob es immer eine explizite Darstellung gibt.
mathers Auf diesen Beitrag antworten »

Hallo und danke schonmal für die Antwort.

Ich dachte auch schon an Induktion als Beweismethode.
Außerdem weiß ich auch, dass es schwierig oder unmöglich sein kann, eine explizite Formel zu finden.

Die Frage ist allgemein und ich möchte wissen, ob die Methodik so logisch korrekt ist (ohne Induktion) ?

Durch a0, a(n+1):=f(a_n) [*] ist eine Folge eindeutig bestimmt.
Dann vermuten wir a(n) = ..... (Terme, hängen nur von n ab)
Dann einsetzen a(0) = a0 prüfen und Rekursiongleichung prüfen.
Haben wir damit gezeigt, dass die Folge, die [*] eindeutig gegeben ist, der expliziten Darstellung genügt?
Elvis Auf diesen Beitrag antworten »

Die allgemeine Formulierung ist unverständlich. Mache ein Beispiel, dann ist das ziemlich sicher entweder a) vollständige Induktion oder b) falsch. (Meine Phantasie reicht nicht aus, um mir eine weitere Möglichkeit einfallen zu lassen.)
mathers Auf diesen Beitrag antworten »

Ok, dann machen wir ein Beispiel

Gegeben sei
a0 := 5
a(n+1) := a(n) + 1
Ohne zu wissen, wie die explizite Darstellung von a(n) lautet, ist a(n) für alle natürlichen Zahlen n wohldefiniert durch die beiden obigen Gleichungen (D).

Behauptung / Vermutung (B):
a(n) = 5+n für alle n (explizite Darstellung)

Prüfen (Einsetzen von "(B)" in "(D)")
und wir sehen a(0)=5+0 = 5=a0, klappt
und a(n+1)=a(n)+1 wird zu: 5+(n+1) = (5+n)+1, klappt

Ist damit bewiesen, dass die eindeutig durch D definierte Folge die explizite Darstellung aus B besitzt?
Elvis Auf diesen Beitrag antworten »

Ja, das klappt, denn das ist vollständige Induktion über n.
 
 
mathers Auf diesen Beitrag antworten »

Hi nochmal,

kannst du mir bitte erklären, wo das vollständige Induktion ist?

Vielleicht denke ich zu kompliziert, aber ist das wirklich äquivalent dazu eine Induktionsvoraussetzung, und so weiter zu formulieren?
Elvis Auf diesen Beitrag antworten »

Behauptung:
Beweis:
Induktionsanfang:
Induktionsschluss:
q.e.d.
mathers Auf diesen Beitrag antworten »

Danke
Neue Frage »
Antworten »



Verwandte Themen

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