I'm asked to find a primitive recursive formula the function: $$ f: N × N → N, f(n, k) = {n \choose k} $$
My attempt: I know that $$ {n \choose k} = \frac{n!}{k! (n-k)!} $$ and so a primitive recursive function $$ g(n, k) $$ would be: $$g(n, k) = div(fact(n), mul(fact(k), fact(sub(n - k))) $$ where div, fact, mul and sub are primitive recursive functions for integer division, factorial, multiplication and subtraction, so g would be, as a composition of primitive recursive functions, also primitive recursive. The problem is I cannot prove that f and g are actually equivalent. How can I do this? Any help would be much appreciated.
Your formula is definitely correct, and at some point in recursion theory, arguments like this are often handwaved. But if you want to be as rigorous as possible, you proceed by induction on $n$.
Base case: Trivial.
Inductive Step: For $n+1$, note that for $k \geq 1$, we have \begin{align*} g(n+1, k) &=\frac{fact(n+1)}{fact(k) \cdot fact(n+1-k))}=\frac{(n+1)fact(n)}{fact(k) \cdot (n+1-k)fact(n-k))} \\ &=\frac{(n+1-k)fact(n)}{fact(k) \cdot (n+1-k)fact(n-k))}+\frac{kfact(n)}{fact(k) \cdot (n+1-k)fact(n-k))}, \end{align*} and from there, you should be able to finish the argument.