Emanuel Keith

2022-06-24

How can I recursively define functions of more than one variable?
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\ge 0$, define $f\left(n+1\right)$ 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}×\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!

humbast2

Step 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\left(0\right)=a$ and such that for all n, $f\left(n+1\right)=g\left(f\left(n\right)\right)$.
In other words, if we define f(0) and then define $f\left(n+1\right)$ 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.
Step 2
Let $A={\mathbb{N}}^{\mathbb{N}}$. Let $a\in A$ be defined by $a\left(0\right)=1$ and $a\left(n+1\right)=0$. Given $x\in A$, define g(x) by $g\left(x\right)\left(0\right)=1$ and $g\left(x\right)\left(n+1\right)=x\left(n\right)+x\left(n+1\right)$. Then $g:A\to A$.
Take $f:\mathbb{N}\to A$ such that $f\left(0\right)=a$ and $f\left(n+1\right)=g\left(f\left(n\right)\right)$. Then it turns out that $\left(\genfrac{}{}{0}{}{n}{m}\right)=f\left(n\right)\left(m\right)$. For we see that $\left(\genfrac{}{}{0}{}{n}{k}\right)=\left(\genfrac{}{}{0}{}{n-1}{k-1}\right)+\left(\genfrac{}{}{0}{}{n}{k}\right)$ whenever $n,k>0$, and the base cases also match up.

Llubanipo

Step 1
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\left(n,n\right)=1$ for all n
- $b\left(n,0\right)=1$ for all n
- $b\left(n,k\right)=b\left(n-1,k-1\right)+b\left(n-1,k\right)$ for $0.
Step 2
Another scheme that works is:
- $b\left(0,0\right)=1$
- $b\left(0,k\right)=0$ for $k\ne 0$
- $b\left(n,k\right)=b\left(n-1,k-1\right)+b\left(n-1,k\right)$ for all $n>0$.

Do you have a similar question?