How to recursively define functions of more than one variable

discrete mathematicsinductionrecursion

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!

Best Answer

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.

Related Question