Show that the function is primitive recursive

Question

I have the function $F(n) = F(n-1) + F(n-2) + F(n-3) + F(n-4)$ where $F(0) = 0, F(1) = 1, F(2) = 1$ and $F(3) = 2$. How can I show that it is a primitive function?

Answer 1

If you prove some encodings and decodings are primitive recursive, then you can define $F$ using primitive recursion with $f(x, \langle a, b, c, d\rangle) = \langle b,c,d,a+b+c+d \rangle$ and $g(x) = \langle 0,1,1,2\rangle$. Then this does the recursion, as \begin{align*} h(0) &= g(0) = \langle F(0),F(1),F(2),F(3)\rangle\\ h(s(x)) &= f(x, \langle F(x), F(x+1), F(x+2), F(x+3)\rangle) \\ &=\langle F(x+1),F(x+2),F(x+3),\sum_{i=0}^3 F(x+i))\rangle \end{align*} Then we can define $F$ as the composition $\#4(h(x))$.