Built on Facts

First, a very quick and simple introduction to recursion. Here's an example. Pick a positive whole number n. The factorial function in the product of all the integers between 1 and n. For some reason it's denoted by an exclamation point.

Now if you compute 5!, you don't need to repeat the whole process if you want to compute 6!. You can just take the answer to 5! and multiply that by 6. Explicitly, because 5! = 1x2x3x4x5, that means 6! = 1x2x3x4x5x6 = (1x2x3x4x5)x6 = (5!)x6. Let me write this generally:

Now just keep that in the back of your mind for a moment and let me show you a slightly snazzier-looking function. The constant n can be anything, here I've plotted it for n=3.

Now let's find the area under that curve, by the calculus method of integration. And for the heck of it, we'll give the integral a name: the Gamma Function.

For slightly annoying technical reasons I'm actually going to integrate the gamma function at the argument n + 1.

Now if you know enough calculus to have followed so far, you can tell that the middle term is going to evaluate to zero. And you'll recognize that the last term is just the gamma function itself evaluated at n. Which means that this is true:

And hey! That's a recursion relationship! It's almost the same one as the one for the factorial function. In fact, it is the same one if you cleverly recognize that in fact n! is just gamma(n + 1).

Now that only proves that they have the same recursion relationship. We'd also need to prove that they start off at the same place, ie, that gamma(2) = 1 or something equivalent. That turns out to be true, and very easy to prove. I'll leave it as an exercise for the interested reader.

What's nice about this is that now we have a way to define the factorial for numbers other than the positive integers. While earlier we could say that 5! = 120, now we can also say that 5.5! = 287.885 by evaluating the integral. This has considerable usefulness in physics and pure mathematics.

In fact with a little more cleverness we can further extend the factorial function to all complex numbers except the negative integers (long story). But that's a task for another day.