Why is $f(x)=x^{2}+1$ a primitive recursive function?

Question

I'm trying to find out why $f:\mathbb{N}\rightarrow\mathbb{N},f(x)=x^{2}+1$ is a primitive recursive function.

For $f(S(y))$ I can't seem to get it to fit the axioms known to me about primitive recursion.

I would appreciate your input.

Cheers!

Gregor

Answer 1

Instead of given a proof, let me give you a guideline. (See how far you get and if you are stuck, feel free to ask for additional help.)

• Show that $add(m,n)$ is primitive recursive
• Note that $mult(m,0) = 0$, $mult(m,S(n)) = add(mult(m,n),m)$
• Using primitive recursion (and projection) and $add(m,n)$ to show that $mult(m,n)$ is primitive recursive
• Conclude that $f$ is primitive recursive