Informatiker Board | Druckvorschau: Verständnisfragen zu Aufgabe zur primitiven Rekursion

Geschrieben von Asgard am 14.02.2007 um 21:22:

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]$ definiert durch $[latex]f(x,y) := \sum_{i=o}^y~x^i [/latex]$ für alle $[latex]x,y \in \mathbb N [/latex]$
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]

$[latex]f(x,y+1)=(x\cdot \sum_{j=0}^y~x^j)+1=(x\cdot f(x,y))+1[/latex]$

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]$ 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.

Geschrieben von Tobias am 14.02.2007 um 21:51:

Man macht wohl die Rekursion über y, weil das y entscheidend ist für die äußere Funktion. Das sind die Summen.

$[latex]\sum_{i=0}^{y+1}x^i = 1 + \sum_{i=1}^{y+1}x^i = 1 + \sum_{i=0}^{y}x^{i+1} = 1 + \sum_{i=0}^{y}x^ix = 1 + x \sum_{i=0}^{y}x^i = 1 + x f(x, y)[/latex]$