Sunday Function

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.

i-d4bb9fe09d6b78eb832985821d8a307f-1.png

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:

i-88516ca505d84f969b7ab15a965c3fb3-2.png

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.

i-8d7070ce28f0af28047c7a5fb8246d53-4.png
i-7b7142f1efa09b47c3b8242f89bcb9f4-graph.png

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.

i-bb5c2c6b0452df43a61e3974bd9b473f-5.png

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

i-80f9713f6d11461837a9f9b540684e36-6.png

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:

i-9ef27a331268eac0961c3fd4d1a55446-7.png

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.

More like this

Math-averse readers! Do not be scared off! You can enjoy this entry even if as far as you're concerned the equations are pretty pictures of Cypriot syllabary. Not long ago we looked at adding up lots of consecutive integers. Multiplying consecutive integers is also interesting, and not only that…
Again, apologies for the hideously scanty posting. Been in the lab doing some really interesting research which will with some luck get me in a really nice journal, as well as doing the various rounds of revision on the paper for some previous research. Also putting two talks together for a…
So in the last few posts, I've been building up the bits and pieces that turn lambda calculus into a useful system. We've got numbers, booleans, and choice operators. The only thing we're lacking is some kind of repetition or iteration. In lambda calculus, all iteration is done by recursion. In…
Time for another sort-of advanced basic. I used some recursive definitions in my explanation of natural numbers and integers. Recursion is a very fundamental concept, but one which many people have a very hard time wrapping their head around. So it's worth taking the time to look at it, and see…

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.

By Michael Luvaul (not verified) on 10 Apr 2009 #permalink