# How to show that certain summations are primitive recursive?

If we have a function $g\colon \mathbb{N}^{k+1} \to \mathbb{N}$ which is primitive-recursive. How to show that the function $f\colon \mathbb{N}^{k+1} \to \mathbb{N}$ with

$$f(x_1, \dots, x_k , x_{k+1})= \sum_{i=0}^{x_{k+1}}g(x_1,\dots, x_k,i)$$

is also primitive recursive?

• You show how to implement it using the operations allowed in primitive recursion. Think of it as a kind of programming exercise. – David Richerby Jun 14 '16 at 21:02
• So wouldn't it be possible to show it with some kind of induction? – fragant Jun 14 '16 at 21:04
• Induction on what? – David Richerby Jun 14 '16 at 21:05
• So we have a primitve recursive function $f$ and the composition and additon of primitive recursive function is also primitive recursive and with these operations would it be possible to define the rhs inductive? – fragant Jun 14 '16 at 21:08
• What have you tried? Where did you get stuck? We do not want to just hand you the solution; we want you to gain understanding. However, as it is we do not know what your underlying problem is, so we can not begin to help. See here for a relevant discussion. If you are uncertain how to improve your question, why not ask around in Computer Science Chat? You may also want to check out our reference questions. – Raphael Aug 14 '16 at 22:47