Mathematik online lernen im Mathe-Forum. Nachhilfe online

Startseite » Forum » Rekursion mit wohlfundierter Induktion beweisen

Rekursion mit wohlfundierter Induktion beweisen

Universität / Fachhochschule

Sonstiges

Tags: Induktion, Sonstig, wohlfundiert

birdbox

00:33 Uhr, 09.05.2016

Hallo,

ich weiß noch nicht ganz genau, was ich im Induktionsschritt einer wohlfundierten Induktion machen muss, deshalb hier mal eine Frage zu einer Aufgabe, die wie folgt lautet:

"Wir definieren die Funktion $A : N_{0} \times N_{0} \to N_{0}$ wie folgt:

$A (m, n) := {\begin{array}{rcl} n + 1 \\ A (m - 1, 1) \\ A (m - 1, A (m, n - 1)) \end{array} \begin{array}{rcl} falls m = 0, \\ falls m > 0 und n = 0, \\ falls m > 0 und n > 0. \end{array}$

Offenbar kann die Auswertung von $A (m, n)$ für $(m, n) \in N_{0} \times N_{0}$ mittels Rekursion realisiert werden - sofern die Rekursion überhaupt terminiert!? Verwenden Sie eine wohlfundierte Induktion, um die Termination von $A (m, n)$ für alle Argumente $(m, n) \in N_{0} \times N_{0}$ zu beweisen."

Also zuerst würde ich behaupten, dass die Rekursion terminiert, da m in jedem Fall irgendwann 0 erreicht, im letzten Fall (bei der 2ten Rekursion) wird irgendwann n=0 sein und dann wird auch wieder m verkleinert bis m=0 ist.

So dann zur wohlfundierten Induktion. Um die Induktionsbasis zeigen zu können, brauch ich die minimalen Elemente, das wäre wohl m=n=0, also:

Induktionsbasis: $A (0, 0) = 0 + 1 = 1 \Rightarrow$ also terminiert $\sqrt{}$ .

Für die Induktionshypothese würd ich genau die rekursive Definition aus der Angabe nehmen, allerdings noch definieren, dass es für alle gilt, die kleiner als m,n sind, also ich würde zB die Buchstaben durch x,y ersetzen und dann sagen: mit $0 \leq x \leq m$ und $0 \leq y \leq n$ . Dann aber beim Induktionsschritt wieder mit m und n arbeiten.

So und jetzt zum Schritt.
Also ich muss zeigen, dass jeder Fall terminiert, d.h. ich nehm mir mal jeden Fall einzeln vor, okay. Aber der erste Fall fällt schon mal weg, den hab ich schon bei der Induktionsbasis gezeigt, richtig?
Hmm der zweite Fall ist eigentlich offensichtlich, m wird immer verkleinert und erreicht irgendwann den Basisfall und terminiert dann auch.
Jedoch wie zeige ich das richtig, so dass es passt? Selber Frage für Fall 3.

Stimmt der Rest denn sonst soweit überhaupt?

LG

Für alle, die mir helfen möchten (automatisch von OnlineMathe generiert):
"Ich möchte die Lösung in Zusammenarbeit mit anderen erstellen."

fenti aktiv_icon

10:03 Uhr, 12.05.2016

Servus,

das sieht aufjedenfall gut aus. Führe die Induktion mit "m+1" und "n+1" durch. Dann zeigst du einfach, dass nach jedem rekursiven Aufruf die Argumente kleiner oder gleich bleiben. Dementspechend landest du schlussendlich immer im ersten Schhritt und die Funktion terminiert.

Sei $m \to m + 1$ und $n \to n + 1 :$

$A (m + 1, n + 1) = A (m + 1 - 1, A (m + 1, n + 1 - 1)) = A (m, (A (m + 1, n)) = . .$ .

Ich denke so sollte der Beweis funktionieren.
"
Also ich muss zeigen, dass jeder Fall terminiert, $d . h$ . ich nehm mir mal jeden Fall einzeln vor, okay. Aber der erste Fall fällt schon mal weg, den hab ich schon bei der Induktionsbasis gezeigt, richtig?
"
Warum fällt der erste Fall weg? Nicht wegen der Induktionsbasis, sondern weil hier einfach kein rekursiver Aufruf eintritt. Somit haben wir hier nichts zu beweisen. Das ist einfach immer ein Wert.

Stephan4

23:19 Uhr, 12.05.2016

Habs ausprobiert, wann die Funktion terminiert:
$A (m, n) . .$ . Schritte
$A (4,0) . .$ . $109,$
$A (5,0) . .$ . mehr als $2^{16}$

$A (3,3) . .$ . $2434$
$A (4,3) . .$ . mehr als $2^{16}$ Schritte

$A (3,4) . .$ . $10309$

Seltsame Funktion.

:-)

birdbox

23:13 Uhr, 16.05.2016

Vielen Dank für eure Antworten!!

"Führe die Induktion mit "m+1" und "n+1" durch"
Warum eigentlich? Laut unserem Prof brauchen wir bei wohlfundierter Induktion, keinen +1 Schritt, da wir es ja eigentlich für alle Elemente die kleiner sind, beweisen wollen.

Also ich habs mal durchgeführt und mein Beweis ist eineinhalb Seiten lang geworden, aber ich glaube er dürfte passen.

@Stephan4: Wie hast du das denn ausprobiert??

LG

fenti aktiv_icon

00:06 Uhr, 17.05.2016

Das ist einfach die übliche Herangehensweise, wenn du bereits gezeigt hast dass es für ein $n$ aus den Natürlichen Zahlen gültig ist, musst du eben zeigen dass es auch für ein $n'$ mit $n' = n + 1$ aus den Natürlichen Zahlen gilt.

Soweit ich informiert bin ist aber auch $n - 1$ zulässig.

Stephan4

01:18 Uhr, 17.05.2016

Hab Excel-Formeln verwendet.
$A 1 :$ (leer)
$B 1 :$ "m"
$C 1 :$ "n"
$A 2 :$ (leer)
$B 2 : 3$ (als Beispiel für $m)$
$C 2 : 5$ (als Beispiel für $n)$
$A 3 :$ =WENN(B2;WENN(C2;A2&B3-1;A2);LINKS(A2;LÄNGE(A2)-1))
$B 3 :$ =WERT(WENN(B2;WENN(C2;B2;B2-1);RECHTS(A2)))
$C 3 :$ =WENN(B2;WENN(C2;C2-1;1);C2+1)

Nun $A 3 : C 3$ runter kopieren.
In jeder Zelle ist die vorherige Zelle weiter entwickelt.

Kann man sicher auch programmieren.

:-)

birdbox

17:21 Uhr, 17.05.2016

Interessant, haha.

Danke euch!!!

1307424

1305890

	Status: nicht eingeloggt	Noch nicht registriert?