0 Daumen
341 Aufrufe
ich habe folgende Frage:
Begründen Sie, warum die Funktion Q : ℕ0 x ℕ → ℕ0 durch die folgende rekursive Definition eindeutig bestimmt ist.
Q((a,b)) = { 0                              für a < bQ(a - b, b) + 1          für a ≥ b
Ich hab hier leider nicht mal einen Ansatz an dem ich mich orientieren könnte.
Avatar von

1 Antwort

+1 Daumen
 
Beste Antwort
ich habe folgende Frage:
Begründen Sie, warum die Funktion Q : ℕ0 x ℕ → ℕ0 durch die folgende rekursive Definition eindeutig bestimmt ist.
Q((a,b)) = { 0                              für a < b                    Q(a - b, b) + 1          für a ≥ b
Ich hab hier leider nicht mal einen Ansatz an dem ich mich orientieren könnte.

versuch mal Induktion über a:  Für a=0 hast du also Q (0 ; b) mit b aus IN zu
betrachten,  also den Fall   a<b  also ist das 0

Wenn nun für alle Paare (a,b) bis zu einem festen a aus INo alles eindeutig bestimmtist,
musst du den Fall    (a+1,b) betrachten .
Fall   a+1 < b ist Q(a+1 ; b) = 0 also alles klar.
falls    a+1 >= b ist,  ist  Q(a+1,b)  =  Q ( a+1-b, b )+1 und
                                                a+1-b < a+1 also  <=a 
Für diese Fälle ist lt. Ind.annahme alles eindeutig bestimmt, also
auch  Q(a+1, b).   q.e.d.
Avatar von 289 k 🚀

Super

Macht Sinn und ist auch gut zu verstehen ^^

Ein anderes Problem?

Stell deine Frage

Willkommen bei der Mathelounge! Stell deine Frage einfach und kostenlos

x
Made by a lovely community