Informatiker Board | Theoretische Informatik | Verständnisfragen zu Aufgabe zur primitiven Rekursion

Informatiker Board » Themengebiete » Theoretische Informatik » Verständnisfragen zu Aufgabe zur primitiven Rekursion » Antwort erstellen

» Hallo Gast [Anmelden|Registrieren]

Antwort erstellen

Benutzername:

(du bist nicht eingeloggt!)

Thema:

Nachricht:

HTML ist nicht erlaubt
BBCode ist erlaubt
Smilies sind erlaubt
Bilder sind erlaubt

einfacher Modus erweiterter Modus

aktuellen Tag schließen

alle Tags schließen

Spamschutz:
Text aus Bild eingeben

URLs automatisch umwandeln: fügt automatisch [url] und [/url] in Internet-Adressen ein.
Smilies in diesem Beitrag deaktivieren.
BBCode in diesem Beitrag deaktivieren.
Bilder in diesem Beitrag deaktivieren.
Signatur anzeigen: Soll die im Profil eingestellte Signatur an den Beitrag angehangen werden?
Nachrichtenlänge überprüfen

Die letzten 2 Beiträge
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]$
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.