How can I recursively define functions of more than one variable?

Question

If I want to recursively define a function $f:\mathbb{N} \to \mathbb{N}$, I can follow the following simple schema:

1. Define $f(0)$ explicitly.
2. For each $n \geq 0$, define $f(n+1)$ in terms of $f(n)$.

This ensures that each natural number has a unique image under $f$. Now suppose I want to recursively define a two-variable function $g : \mathbb{N} \times \mathbb{N} \to \mathbb{N}$. For example, maybe I want to define binomial coefficients, or stirling numbers, or something. Is there an analogous schema I can use?

Note: I'm very new to math, so if you could be as explicit as possible, I would really appreciate it!

Answer 1

You’ve discussed the most basic recursion principle, which states, in more formal terms,

Suppose $a \in A$, and suppose $g : A \to A$. There is a unique function $f : \mathbb{N} \to A$ such that $f(0) = a$ and such that for all $n$, $f(n + 1) = g(f(n))$.

In other words, if we define $f(0)$ and then define $f(n + 1)$ in terms of $f(n)$, we’ve defined $f$.

We can define more general functions in many ways, all derived from this schema. Here’s an illustrative example.

Let $A = \mathbb{N} ^ \mathbb{N}$. Let $a \in A$ be defined by $a(0) = 1$ and $a(n + 1) = 0$. Given $x \in A$, define $g(x)$ by $g(x)(0) = 1$ and $g(x)(n + 1) = x(n) + x(n + 1)$. Then $g : A \to A$.

Take $f : \mathbb{N} \to A$ such that $f(0) = a$ and $f(n + 1) = g(f(n))$. Then it turns out that $\binom{n}{m} = f(n)(m)$. For we see that $\binom{n}{k} = \binom{n - 1}{k - 1} + \binom{n}{k}$ whenever $n, k > 0$, and the base cases also match up.

Answer 2

Yes. Again, you need

• one or more "recurrence relation", connecting some term to other terms,
• one or more "initial values", giving explicitly values for certain terms.

For example, the binomial coefficients can be defined by:

• $b(n,n)=1$ for all $n$
• $b(n,0)=1$ for all $n$
• $b(n,k) = b(n-1,k-1) + b(n-1,k)$ for $0<k<n$.

Another scheme that works is:

• $b(0,0)=1$
• $b(0,k)=0$ for $k\neq 0$
• $b(n,k) = b(n-1,k-1) + b(n-1,k)$ for all $n>0$.

Here's another fun example, call'ed "Ackerman's Function":

• $A(0,n) = n+1$
• $A(m+1,0) = A(m,1)$
• $A(m+1,n+1) = A(m,A(m+1,n))$

So,

• $A(1,1)$, with $m=0$ and $n=0$, is $A(0,A(1,0))$.
• To find that, we have to find $A(1,0)$, but that's $A(0,1)$, by the second rule.
• $A(0,1)$ is $1+1$ (by the first rule), so $A(1,0)=A(0,1)=2$.
• So $A(1,1)=A(0,2)$, which is $2+1=3$.

See if you can work out $A(2,2)$. It's fun to try to prove that $A(3,3)$ is $61$, and working out $A(4,4)$ and $A(5,5)$ is even more fun.