Vollständige Induktion - Ackermannfunktion |
| 27.01.2011, 15:08 | Esto | Auf diesen Beitrag antworten » |
| Vollständige Induktion - Ackermannfunktion A(m,n) = I) n+1 für m= 0 II) A(m-1,1) für m>0 und n=0 III)A(m-1,A(m,n-1)) für m>0 und n > 0 Zeige mit Hilfe von Induktion: A(2,n) = 2n+3 Meine Lösung: Induktionsanfang: n = 0 A(2,0) = A(1,1) = (A(0, A(1,0)) = A(0,2) = 3 und 2 * 0 +3 = 3 // Stimmt also! Voraussetzung A(2,n) = 2n +3 gelte für alle natürlichen Zahlen! Induktionschritt / -behauptung Gilt auch für n + 1 d.h.: Zu zeigen: A(2,n+1) = 2(n+1) + 3 Beweis A(2,n+1) = A(1,A(2,n)) // Gleichung III) angewendet = A(1, 2n+3) // nach Induktionsvoraussetzung =A(0,A(1,2n+3-1)) // Gleichung III) angewendet = A(0.A(0,A(0, .... ,A(1,(2n+3) - 2n+3))) ....) // Gleichung III) mehrmals angewendet = A(0.A(0,A(0, .... ,A(1,0))) ....) = A(0.A(0,A(0, .... ,A(0,1))) ....) // Gleichung II) angewendet = A(0,2n+4) = 2n +5 //Gleichung I) mehrmals angwendet q.e.d. Kann man das so schreiben?? Ist mir irgendwie nicht ganz geheuer |
||
| 27.01.2011, 15:18 | Esto | Auf diesen Beitrag antworten » |
Ah sorry, ins falsche Themengebiet gepostet.... |
||
| 27.01.2011, 15:50 | wisili | Auf diesen Beitrag antworten » |
Um dein Unwohlsein zu beseitigen müsstest du wohl die Passage mit «....» mit einem separaten Induktionsbeweis ersetzen: Zeige A(1,n) = n+2. |
||
| 28.01.2011, 17:32 | Esto | Auf diesen Beitrag antworten » |
Jop, danke, da bin ich später auch drauf gekommen. Nun sieht der Beweis wieder anständig aus 
|
||
|
|
Verwandte Themen
| Die Beliebtesten » |
|
| Die Größten » |
|
| Die Neuesten » |
|
