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.
- Log in to post comments
I've been reading your Sunday Function for several months now and it's been good to look at advanced mathematics again, even if only as a pastime. I really enjoy your style of writing (slightly annoying!). Thanks.
I don't suppose you'd be willing to go into the "technical reason" that the gamma is defined with that 1 offset? I've always wondered why it isn't defined as the integral of x^n e^{-x}, rather than x^{n-1}.
For a lot of purposes (mostly in pure math, it usually doesn't matter in physics), two other definitions due to Euler and Weierstrass are more fundamental. They're the infinite product representations, which allow the gamma function to be easily extended to the complex numbers. The integral definition isn't nearly as useful for that process. It unfortunately happens that things work out in such a way so that you're going to get that n+1 offset in either the products or the integral, and so mathematicians decided to define gamma so that the product expressions were the clean ones.
And gamma of 1/2 is the square root of Pi. This is one of the coolest things. Tell someone that (1/2)! is Pi and they'll give you really weird looks.
If you tell people that (1/2)! is Pi they SHOULD give you weird looks, especially after checking up on you. My TI-89, Maple, and MATLAB all agree its ~0.785398 which isn't anywhere near Pi.
Er, sorry (3/2)!, not (1/2)!.