3

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.

Monika
  • 585
  • Excuse my ignorance but aren‘t they the same just by definition? – Maximilian Janisch Dec 26 '19 at 00:37
  • Your formula is correct, but I'm not sure that's what the question might be looking for. It seems you've just restated the formula by definition. I believe the question is looking for you to express $g(n,k)$ recursively i.e. by $g(n,k)$ for different inputs. – layabout Dec 26 '19 at 00:39
  • 1
    Is the problem to show that $\binom{n}{k}=\frac{n!}{k!(n-k)!}$? Or is the problem to come up with a recursive formula for binomial coefficients? In the later case, you could use the fact that for $n,k\ge1$, $\binom{n}{k}=\binom{n-1}{k}+\binom{n-1}{k-1}$. – user729424 Dec 26 '19 at 01:02
  • 1
    Please don't vandalize your question after receiving answers. – Martin R Dec 30 '19 at 02:04

1 Answers1

2

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.

Dark Logician
  • 366