Verständnisfragen zu Aufgabe zur primitiven Rekursion

14.02.2007, 21:22	Auf diesen Beitrag antworten »
Asgard	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,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.


14.02.2007, 21:51	Auf diesen Beitrag antworten »
Tobias	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]$

Verwandte Themen

Die Beliebtesten »

Die Größten »

Die Neuesten »