Beweis der Ackermannfunktion < Induktion < eindimensional < reell < Analysis < Hochschule < Mathe < Vorhilfe
|
| Status: |
(Frage) beantwortet  | | Datum: | 17:36 Di 10.04.2012 | | Autor: | bandchef |
| Aufgabe | | Zeigen sie mittles vollständiger Induktion, dass $ack(n,m)$ für alle $n, m [mm] \in \mathbb N_0$ [/mm] definiert ist. |
Hi Leute!
Ich bräuchte zu obiger Aufgabe Hilfe von euch! Soweit bin ich schon mal:
$ack(n,m) = [mm] \begin{cases} m+1, & \mbox{für } n=0 \\ ack(n-1,1), & \mbox{für } m=0 \mbox{ und } n\geq 1 \\ ack(n-1,ack(n,m-1) &\mbox{sonst }\end{cases}$
[/mm]
Induktionsanfang:
...
Da weiß ich nun schon mal nicht mehr weiter, da mich die zwei Variablen n,m doch recht irritieren... Könnt ihr mir helfen?
|
|
| |
|
| Status: |
(Frage) beantwortet | | Datum: | 17:59 Di 10.04.2012 | | Autor: | bandchef |
$ ack(n,m) = [mm] \begin{cases} m+1, & \mbox{für } n=0 \\ ack(n-1,1), & \mbox{für } m=0 \mbox{ und } n\geq 1 \\ ack(n-1,ack(n,m-1)) &\mbox{sonst }\end{cases} [/mm] $
Behauptung: $ack(n,m) [mm] \text{ ist definiert } \forall [/mm] n,m [mm] \in \mathbb N_0$
[/mm]
Induktionsanfang:
n=0 und m=0: ack(0,0)=ack(0,1)=?
n=1 und m=0: ack(1,0)=ack(1-1,1)=ack(0,1)=?
Stimmt das soweit?
|
|
|
| |
|
Hallo,
> Behauptung: [mm]ack(n,m) \text{ ist definiert } \forall n,m \in \mathbb N_0[/mm]
>
> Induktionsanfang:
>
> n=0 und m=0: ack(0,0)=ack(0,1)=?
Meinst du: ack(0,0) = 1 ?
(Guck dir nochmal die Funktionsvorschrift an, da steht im Falle n = 0, dass der Wert m+1 ist, nicht eine weitere Ackermannfunktion.)
Grüße,
Stefan
|
|
|
| |
|
| Status: |
(Antwort) fertig  | | Datum: | 22:00 Di 10.04.2012 | | Autor: | Marcel |
Hallo,
> Zeigen sie mittles vollständiger Induktion, dass [mm]ack(n,m)[/mm]
> für alle [mm]n, m \in \mathbb N_0[/mm] definiert ist.
> Hi Leute!
>
> Ich bräuchte zu obiger Aufgabe Hilfe von euch! Soweit bin
> ich schon mal:
>
> [mm]ack(n,m) = \begin{cases} m+1, & \mbox{für } n=0 \\ ack(n-1,1), & \mbox{für } m=0 \mbox{ und } n\geq 1 \\ ack(n-1,ack(n,m-1) &\mbox{sonst }\end{cases}[/mm]
>
> Induktionsanfang:
>
> ...
>
>
> Da weiß ich nun schon mal nicht mehr weiter, da mich die
> zwei Variablen n,m doch recht irritieren... Könnt ihr mir
> helfen?
es gibt hier sozusagen eine spezielle Induktion:
Eine Variante ist etwa, zu zeigen:
Zeige, dass [mm] $ack(0,0)\,$ [/mm] existiert. (Induktionsanfang!)
Dann zeige:
Wenn es $(n,m) [mm] \in \IN_0^2$ [/mm] so gibt, dass gilt:
Sind die [mm] $ack(k,\ell)$-Werte [/mm] alle für $k [mm] \le [/mm] n$ und [mm] $\ell \le [/mm] m$ definiert und wenn gelten sowohl
1.) Damit folgt die Existenz von $ack(n+1,m)$
und auch
2.) Damit folgt die Existenz von $ack(n,m+1)$
dann hast Du die Behauptung gezeigt.
(Mach' Dir das mal etwa an einem Matrizenschema klar, wobei die doppelt unendliche quadratische Matrix mit den Zahlen aus [mm] $\IN_0^2$ [/mm] "indiziert ist":
D.h. wenn [mm] $A\,$ [/mm] diese Matrix ist mit Einträgen aus [mm] $\IR$, [/mm] dann ist $A [mm] \in \IR^{{\IN_0}^2}\,,$ [/mm] d.h. es gilt [mm] $A=(a_{(p,q)})_{(p,q) \in \IN_0^2}=(a_{p,q})_{\substack{p \in \IN_0 \\ q \in \IN_0}}$!)
[/mm]
Das Verfahren hat einen speziellen Namen - glaube ich - der fällt mir aber gerade nicht ein. Generell kann man das sicher auch mit einer "verallgemeinerten Version der Induktion" angehen. Aber hier reicht's sicher auch, die von mir vorgeschlagene Induktionsvorgehensweise zu benutzen.
Beachte: Beim Schnritt $A(n,m) [mm] \to [/mm] A(n+1,m)$ kann es sein, dass man "nicht alle Vorgänger" benötigt. Ebenso beim Schritt $A(n,m) [mm] \to A(n,m+1)\,.$
[/mm]
Gruß,
Marcel
|
|
|
|
