Asgard
Jungspund
Dabei seit: 09.12.2006
Beiträge: 12
 |
|
| Verständnisfragen zu Aufgabe zur primitiven Rekursion |
     |
Leider kann ich einen Schritt in einer Übungsaufgabe nicht nachvollziehen:
Sei ![[latex]f: \mathbb N ^2 \to \mathbb N [/latex]](http://www.matheboard.de/latex2png/latex2png.php?f: \mathbb N ^2 \to \mathbb N ) definiert durch ![[latex]f(x,y) := \sum_{i=o}^y~x^i [/latex]](http://www.matheboard.de/latex2png/latex2png.php?f(x,y) := \sum_{i=o}^y~x^i ) für alle ![[latex]x,y \in \mathbb N [/latex]](http://www.matheboard.de/latex2png/latex2png.php?x,y \in \mathbb N )
Zeigen Sie, dass f primitiv rekursiv ist, indem Sie angeben, wie sich f aus
den primitiv rekursiven Grundfunktionen und der Multiplikationsfunktion mul
mittels der Operatoren Sub und Prim erzeugen lässt.
Nun soll laut Lösung die folgende zweistellige Funktion f die Rekursionsgleichung erfüllen:
![[latex]f(x,0)=1[/latex]](http://www.matheboard.de/latex2png/latex2png.php?f(x,0)=1)
![[latex]f(x,y+1)=(x\cdot \sum_{j=0}^y~x^j)+1=(x\cdot f(x,y))+1[/latex]](http://www.matheboard.de/latex2png/latex2png.php?f(x,y+1)=(x\cdot \sum_{j=0}^y~x^j)+1=(x\cdot f(x,y))+1)
1. Warum findet die Rekursion über y statt? Intuitiv würde ich zwar ebenfalls y nehmen, aber mir ist nicht wirklich klar warum.
2. Was für mich viel wichtiger ist: Wie kommt man auf die Umformung zu f(x,y+1)? Meines Erachtens kann man zwar das letzte Glied der Summe, also ![[latex]x^{y+1}[/latex]](http://www.matheboard.de/latex2png/latex2png.php?x^{y+1}) von der Summe abtrennen, aber die weiteren Umformungen sind mir leider schleierhaft und so fällt es mir leider schwer den Rest der Lösung zu verstehen.
|
|
