courseofvalues recursion
In defining a function by primitive recursion, the value of the next argument $f(n+1)$ depends only on the value of the current argument $f(n)$. Definition of functions by courseofvalues recursion, $f(n+1)$ depends on value(s) of some or all of the preceding arguments $f(n),\mathrm{\dots},f(0)$. Two very basic examples of definition by courseofvalues recursion are

1.
(Fibonacci numbers^{}). $F(0)=F(1)=1$, and $F(n+1)=F(n)+F(n1)$.

2.
$f(0)=1$, and $f(n+1)=f(n)+f(n1)+\mathrm{\cdots}+f(0)$.
In the first example, we may write $F(n+1)=g(F(n),F(n1))$, where $g$ is the familiar addition^{} function, a function of two arguments. In other words, value of the current argument of $F$ depends on the values of a fixed number of preceding arguments (in this case, $2$). In the second example, value of the current argument of $f$ depends on the values of all of the values of the preceding arguments. Suppose we write $f(n+1)=h(f(n),\mathrm{\dots},f(0))$, where $h$ is the $(n+1)$ary addition function. This $h$ is different from $g$ in the sense that $g$ has a fixed arity, whereas the arity of $h$ depends on the argument of $f$. In other words, as $n$ varies, a “different” $h$ is required! Is it possible to define $f$ via a fixed function as in the first example? Moreover, what is the relation^{} between courseofvalues recursion and primitive recursion?
The answer to the first question is yes. To get around the difficulty of “varying arity”, we employ the technique of encoding the entire sequence^{} of values of the preceding arguments of $f$ by a “code number”, and come up with a function $h$ that depends on the this code number. $h$ then can be used to define $f$.
Pick an encoding of finite sequences of nonnegative integers, preferably a primitive recursive encoding. As usual, we set
$$\u27e8{a}_{1},\mathrm{\dots},{a}_{m}\u27e9$$ 
as the code, or sequence number of the sequence ${a}_{1},\mathrm{\dots},{a}_{m}$, and if $x=\u27e8{a}_{1},\mathrm{\dots},{a}_{m}\u27e9$, we set ${(x)}_{i}:={a}_{i}$ if $i\le m$, and $0$ otherwise.
For this entry, we choose the multiplicative encoding of Gödel (see this entry (http://planetmath.org/ExamplesOfPrimitiveRecursiveEncoding) for more detail) because of its convenience. Then
$$\u27e8{a}_{1},\mathrm{\dots},{a}_{m}\u27e9:={p}_{1}^{s({a}_{1})}\mathrm{\cdots}{p}_{m}^{s({a}_{m})},$$ 
where ${p}_{i}$ is the $i$th prime number^{}, and $\u27e8\u27e9:=1$.
Definition. For any function $f:{\mathbb{N}}^{k+1}\to \mathbb{N}$, define the courseofvalues function $\overline{f}$ of $f$ as follows: $\overline{f}$ has the same arity as $f$, and for any $\bm{x}\in {\mathbb{N}}^{k}$,

1.
$\overline{f}(\bm{x},0):=\u27e8\u27e9$, and

2.
$\overline{f}(\bm{x},y+1):=\u27e8f(\bm{x},0),\mathrm{\dots},f(\bm{x},y)\u27e9$.
For example, if $F(n)$ is the $n$th Fibonacci number, then $\overline{F}(0)=1$, $\overline{F}(1)=\u27e81\u27e9=4$, and $\overline{F}(2)=\u27e84,1\u27e9={2}^{5}\cdot {3}^{2}=288$, etc… It is evident that $\overline{F}$ grows very rapidly.
Definition. A function $f:{\mathbb{N}}^{k+1}\to \mathbb{N}$ is said to be defined by courseofvalues recursion via function $h:{\mathbb{N}}^{k+2}\to \mathbb{N}$ if, for any $\bm{x}\in {\mathbb{N}}^{k}$:
$$f(\bm{x},y)=h(\bm{x},y,\overline{f}(\bm{x},y)).$$ 
The two examples above are defined by courseofvalues recursion:

•
$F(n)=h(n,\overline{F}(n))$, where $h(x,y):={(y)}_{x}+{(y)}_{x\dot{}1}$.

•
$f(n)=h(n,\overline{f}(n))$, where $h(x,y)={\sum}_{i=0}^{x\dot{}1}{(y)}_{i}$.
The second question posed at the beginning can now be answered:
Proposition 1.
$f$ is primitive recursive iff $\overline{f}$ is.
Proof.
By definition, and using multiplicative encoding, we have $\overline{f}(\bm{x},0):=\u27e8\u27e9=1$, and
$$\overline{f}(\bm{x},y+1):={p}_{1}^{f(\bm{x},0)}\mathrm{\cdots}{p}_{y+1}^{f(\bm{x},y)}=\overline{f}(\bm{x},y){p}_{y+1}^{f(\bm{x},y)}$$ 
Thus, if $f$ is primitive recursive, so is $\overline{f}$ by primitive recursion. Conversely, if $\overline{f}$ is primitive recursive, so is $f(\bm{x},y)={(\overline{f}(\bm{x},y+1))}_{y+1}$. ∎
Proposition 2.
If $h\mathrm{:}{\mathrm{N}}^{k\mathrm{+}\mathrm{1}}\mathrm{\to}\mathrm{N}$ is primitive recursive, so is $f$ defined by courseofvalues recursion via $h$.
Proof.
From the proof of the proposition^{} above, we see that
$$\overline{f}(\bm{x},y+1)=\overline{f}(\bm{x},y){p}_{y+1}^{f(\bm{x},y)}=\overline{f}(\bm{x},y){p}_{y+1}^{h(\bm{x},y,\overline{f}(\bm{x},y))}.$$ 
Thus, as $h$ is primitive recursive, so is $\overline{f}$ by primitive recursion, and hence $f$ is primitive recursive by the previous proposition. ∎
Remark. If the value of the next argument of $f$ depends on values of a fixed set of prior arguments, then the primitive recursiveness of $f$ can be proved via mutual recursion. For example, suppose $f(k+1)=h(f(k1),f(k3),f(k4))$. By setting ${f}_{i}(n):=f(n+i)$ for $i=0,1,2,3$, we see that
$${f}_{i}(n+1)=f(n+i+1)={f}_{i+1}(n)\mathit{\hspace{1em}}\text{for}i=0,1,2.$$ 
Furthermore,
${f}_{3}(n+1)$  $=$  ${f}_{0}(n+4)=f(n+4)=h(f(n+2),f(n+1),f(n))$  
$=$  $h({f}_{0}(n+2),{f}_{0}(n+1),{f}_{0}(n))=h({f}_{2}(n),{f}_{1}(n),{f}_{0}(n)).$ 
So the ${f}_{i}$ are defined by mutual recursion, and if $h$ is primitive recursive, so is each ${f}_{i}$.
Title  courseofvalues recursion 

Canonical name  CourseofvaluesRecursion 
Date of creation  20130322 19:06:13 
Last modified on  20130322 19:06:13 
Owner  CWoo (3771) 
Last modified by  CWoo (3771) 
Numerical id  11 
Author  CWoo (3771) 
Entry type  Definition 
Classification  msc 03D20 
Synonym  courseofvalue 
Synonym  courseofvalues 