The function of the Ackermann function is defined as $$ A_{0}(y)= y+1$$ $$ A_{x+1}(0)= A_{x}(1)$$ $$ A_{x+1}(y +1)= A_{x}(A_{x+1}(y))$$
I want to show that the function of ackermann is primitive recursive, showing that for all function primitive recursive $f$ exist a number m such that $f(x_{1}, \dots , x_{k}) < A_{m}(x_{1} + \dots + x_{k})$ for the basic functions (successor, zero, projections) and the composition I did not have problem but for recursion scheme i could not show.
Suppose that $g$ is a $k$-ary function and $h$ a $k+2$- ary and let a function $f$ which is $k +1$- ary obtained by the recursion scheme applied to $f$ and $h$. Supposing that one exists $r$ such that $g(x_{1}, \dots , x_{k})<A_{r}(x_{1}+ \dots + x_{k})$ and exist $s$ such that $h(y_{1}, \dots , y_{k +2})<A_{r}(y_{1}+ \dots + y_{k+2})$ we should find a $q$ such that $f(x_{1}, \dots , x_{k}, n)<A_{q}(x_{1}+ \dots + x_{k} +n)$. I take $q= 1 + max\{r,s\}$ and I try to show by induction on n, for the base case we have $f(x_{1}, \dots , x_{k}, 0)=g(x_{1}, \dots x_{k})< A_{r}(x_{1}+ \dots + x_{k})<A_{q}(x_{1}+ \dots + x_{k})$ Now assuming that $f(x_{1}, \dots , x_{k}, n)<A_{q}(x_{1}+ \dots + x_{k} +n)$ want to show that$f(x_{1}, \dots , x_{k}, n+1)=h(x_{1}, \dots x_{k}, f(x_{1} \dots , x_{k}, n),n)<A_{q}(x_{1}+ \dots + x_{k} +(n+1))$ but I could not show it.
Any hint is welcome. Thanks
