# 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!

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.