The work here is actual assigned homework from Dr. Mary Flagg’s Number Theory, Math 4383 – Section 19842, going on now at the University of Houston this Spring 2012 semester. This is from homework assignment 1. The problems are taken from Elementary Number Theory, Seventh Edition, by David. M. Burton.

However, I will be going beyond much of this homework by adding additional material as it strikes me as being relevant to the topic at hand.

The theorems of importance in Chapter One are the following: Well-Ordering Principle, Archimedean property, the Principle of Mathematical Induction (PMI), and the Binomial Theorem. All of these were introduced to me last semester by Professor Garret Etgen in his Analysis course, and again, by Professor Siemion Fajtlowicz in his abstract algebra course, and here they are yet again in Dr. Mary Flagg’s number theory — that is how utterly important and basic these concepts are that they deserve repeated introduction. For analysis, the well-ordering and Archimedean property are appealed to time and again when working with proofs.

Well-Ordering Principle Every nonempty set S of nonnegative integers contains a least element.

[proof pending, time permitting]

This principle is the key to proving the Archimedean property, which in turn is the key needed to prove the principle of mathematical induction. Therefore, these three are all conjoined concepts.

Theorem 1.1 Archimedean Property. If a and b are any positive integers, then there exists a positive integer n such that $\displaystyle na\ge b$.

[proof pending, time permitting]

Essentially, this is saying that if we have n of something, then there is always n+1 of them, a successor, if you will. Intuitively, this allows us to define infinity without ever really having to deal with it philosophically: that which is finite stops while that which is infinite continues beyond any one of its members, especially, there is no “last” one in an infinite set. Yet we never have to actually talk about “infinity” to mean infinite.

Theorem 1.2 First Principle of Mathematical Induction (PMI) Let S be a set of positive integers with the following properties:

(a) The integer 1 belongs to S.
(b) Whenever the integer k is in S, the next integer k+1 must also be in S.

Then S is the set of all positive integers.

[proof pending, time permitting]

As a technique with which to prove theorems, Mathematical induction was first demonstrated by Francesco Maurolyeus (1494-1575). It was heavily relied upon by Blaise Pascal (1623-1662) when he undertook his research into the binomial coefficients.

But there are actually three version of the PMI: the Principle of Mathematical Induction (PMI), the General Principle of Mathematical Induction (GPMI), and the Strong or Complete Principle of Mathematical Induction (SPMI). And there is also Transfinite Induction, just to be somewhat thorough. Most texts suffice with the PMI and SPMI. Are these divisions of the PMI necessary? Yes, for each serves its purpose when working with particular types of induction problems.

Perhaps many people, upon first seeing induction used, are shown rather trivial problems, and so feel that this is a trivial technique. Nothing could be further from the truth. But one must be shown non-trivial problems to appreciate why one would never consider leaving induction out of one’s mathematical toolkit. A small hint of its power glimmers in problem 1.2 #5(a) below, where the PMI is combined with other ideas in an effort to prove a statement. And it is in conjunction with other techniques that the utility and power of the PMI will be felt when going about proofs.

The Binomial Theorem

$\displaystyle {{(a+b)}^{n}}=\left( \begin{matrix}n \\o \\\end{matrix} \right){{a}^{n}}+\left( \begin{matrix}n \\1 \\\end{matrix} \right){{a}^{n-1}}b+\left( \begin{matrix}n \\2 \\\end{matrix} \right){{a}^{n-2}}{{b}^{2}}+...+\left( \begin{matrix}n \\n \\\end{matrix} \right){{b}^{n}}$

This is one of the main concepts of chapter 1, without a doubt. Taking Pascal’s Triangle, and going down the center, these coefficients are very important, and accordingly given the name Centeral Binomial Coefficients, because they appear everywhere in mathematics, but especially in combinatorics and number theory.

$\displaystyle {2n \choose n} = \frac{(2n)!}{(n!)^2}\text{ for all }n \geq 0$

where the first few values of this coefficient are:

$\displaystyle 1, 2, 6, 20, 70, 252, 924, 3432, 12870, 48620, ...$

Worked Problems

1.1 #2. If $\displaystyle r\ne 1$, show that for any positive integer n,

$\displaystyle a+ar+a{{r}^{2}}+a{{r}^{3}}+a{{r}^{4}}+...+a{{r}^{n-1}}+a{{r}^{n}}=\frac{a\left( {{r}^{n+1}}-1 \right)}{r-1}$

Proof. Using the PMI, Step 1. Let $\displaystyle n=1\in \mathbb{S}$. Then we have:

$\displaystyle a+ar=\frac{a\left( {{r}^{1+1}}-1 \right)}{r-1}=\frac{a\left( {{r}^{2}}-1 \right)}{r-1}=\frac{a\left( r+1 \right)\left( r-1 \right)}{r-1}=a\left( r+1 \right)=a+ar$

so that the formula is true for $\displaystyle 1\in \mathbb{S}$.

Step 2. Now, assume that the formula holds for $\displaystyle k\in \mathbb{S}$ so that:

$\displaystyle a+ar+a{{r}^{2}}+a{{r}^{3}}+a{{r}^{4}}+...+a{{r}^{k-1}}+a{{r}^{k}}=\frac{a\left( {{r}^{k+1}}-1 \right)}{r-1}$

Step 3. Then, for k+1 we have:

$\displaystyle a+ar+a{{r}^{2}}+a{{r}^{3}}+a{{r}^{4}}+...+a{{r}^{k-1}}+a{{r}^{k}}+a{{r}^{k+1}}=\frac{a\left( {{r}^{(k+1)+1}}-1 \right)}{r-1}$

and simplifying yields:

$\displaystyle a+ar+a{{r}^{2}}+a{{r}^{3}}+a{{r}^{4}}+...+a{{r}^{k-1}}+a{{r}^{k}}+a{{r}^{k+1}}=\frac{a\left( {{r}^{k+2}}-1 \right)}{r-1}$

but the LHS may be further simplified as:

$\displaystyle (a+ar+a{{r}^{2}}+a{{r}^{3}}+a{{r}^{4}}+...+a{{r}^{k-1}}+a{{r}^{k}})+a{{r}^{k+1}}$

$\displaystyle =\frac{a\left( {{r}^{k+1}}-1 \right)}{r-1}+\frac{a{{r}^{k+1}}(r-1)}{r-1}$

$\displaystyle =\frac{a\left( {{r}^{k+1}}-1 \right)+a{{r}^{k+1}}(r-1)}{r-1}=\frac{a{{r}^{k+1}}-a+a{{r}^{k+2}}-a{{r}^{k+1}}}{r-1}$

$\displaystyle =\frac{a(-1+{{r}^{k+2}})}{r-1}=\frac{-a+a{{r}^{k+2}}}{r-1}=\frac{a{{r}^{k+2}}-a}{r-1}$

$\displaystyle =\frac{a({{r}^{k+2}}-1)}{r-1}$

but this is the original RHS when we let n=k+2 . Therefore, by the PMI, we have that for all $\displaystyle n\in {{\mathbb{Z}}^{+}}$,

$\displaystyle a+ar+a{{r}^{2}}+a{{r}^{3}}+a{{r}^{4}}+...+a{{r}^{n-1}}+a{{r}^{n}}=\frac{a\left( {{r}^{n+1}}-1 \right)}{r-1}$

holds true. QED

1.1 #9. Establish the Bernoulli inequality: if $\displaystyle 1+a>0$, then

$\displaystyle {{\left( 1+a \right)}^{n}}\ge 1+na$

Proof. Using the PMI, we proceed as follows.

Step 1. Let n=1. Then we have:

$\displaystyle {{\left( 1+a \right)}^{1}}\ge 1+(1)a\Rightarrow {{(1+a)}^{{}}}\ge 1+a$

therefore it is true for n=1. Next,

Step 2. Assume it to be true for k.

$\displaystyle {{\left( 1+a \right)}^{k}}\ge 1+ka$

Step 3. For k+1, we have:

$\displaystyle {{\left( 1+a \right)}^{k+1}}\ge 1+(k+1)a$

or, since $\displaystyle 1+a>0$, we have that

$\displaystyle (1+a){{\left( 1+a \right)}^{k}}\ge (1+a)(1+ka)$

or

$\displaystyle {{\left( 1+a \right)}^{k+1}}\ge 1+a+ka+k{{a}^{2}}$

or

$\displaystyle {{\left( 1+a \right)}^{k+1}}\ge 1+(1+k)a+k{{a}^{2}}$

but

$\displaystyle 1+(1+k)a+k{{a}^{2}}\ge 1+(k+1)a$

because $\displaystyle k{{a}^{2}}>0$, we therefore also that

$\displaystyle {{\left( 1+a \right)}^{k+1}}\ge 1+(k+1)a$

but this is simply n=k+1. Therefore, by the PMI, we have that, when $\displaystyle 1+a>0$:

$\displaystyle {{\left( 1+a \right)}^{n}}\ge 1+na$

holds true for all $\displaystyle n\in {{\mathbb{Z}}^{+}}$. QED

Another interesting way to see this, without using induction, is to simply expand the LHS via the Binomial Theorem, and we get:

$\displaystyle {{(1+a)}^{n}}=\left( \begin{matrix}n \\n \\\end{matrix} \right)+\left( \begin{matrix}n \\n-1 \\\end{matrix} \right)a+\left( \begin{matrix}n \\n-2 \\\end{matrix} \right){{a}^{2}}+...+\left( \begin{matrix}n \ \\\end{matrix} \right){{a}^{n}}$

and from this it follows that:

$\displaystyle {{(1+a)}^{n}}=1+na+\frac{n(n-1){{a}^{2}}}{2}+...+{{a}^{n}}\ge 1+na$

and so the expanded LHS is certainly larger than the sum of its first two terms. Therefore,

$\displaystyle {{(1+a)}^{n}}\ge 1+na$

follows immediately. QED

1.2 #3(d). Derive the following identity:

$\displaystyle \left( \begin{matrix}n \\n \\\end{matrix}\right)+\left( \begin{matrix}n \\n-1 \\\end{matrix} \right)2+\left( \begin{matrix}n \\n-2 \\\end{matrix} \right){{2}^{2}}+...+\left( \begin{matrix}n \ \\\end{matrix} \right){{2}^{n}}={{3}^{n}}$

Proof. We may derive this directly from the binomial theorem:

$\displaystyle {{(a+b)}^{n}}=\left( \begin{matrix}n \\o \\\end{matrix} \right){{a}^{n}}+\left( \begin{matrix}n \\1 \\\end{matrix} \right){{a}^{n-1}}b+\left( \begin{matrix}n \\2 \\\end{matrix} \right){{a}^{n-2}}{{b}^{2}}+...+\left( \begin{matrix}n \\n \\\end{matrix} \right){{b}^{n}}$

by setting a=2, b=1 and reversing the order of terms, we get:

$\displaystyle {{(2+1)}^{n}}=\left( \begin{matrix}n \\n \\\end{matrix}\right)+\left( \begin{matrix}n \\n-1 \\\end{matrix} \right)2+\left( \begin{matrix}n \\n-2 \\\end{matrix} \right){{2}^{2}}+...+\left( \begin{matrix}n \ \\\end{matrix} \right){{2}^{n}}$

and combing terms and rearranging, the result immediately follows:

$\displaystyle {{3}^{n}}=\left( \begin{matrix}n \\n \\\end{matrix}\right)+\left( \begin{matrix}n \\n-1 \\\end{matrix} \right)2+\left( \begin{matrix}n \\n-2 \\\end{matrix} \right){{2}^{2}}+...+\left( \begin{matrix}n \ \\\end{matrix} \right){{2}^{n}}$

QED

1.2 #5(a) For $\displaystyle n\ge 2$ , prove that:

$\displaystyle \left(\begin{matrix}2 \\2 \\\end{matrix}\right)+\left(\begin{matrix}3 \\2 \\\end{matrix}\right)+\left( \begin{matrix}4 \\2 \\\end{matrix}\right)+...+\left(\begin{matrix}n \\2 \\\end{matrix}\right)=\left(\begin{matrix}n+1 \\3 \\\end{matrix} \right)$

Proof. Using the PMI, we proceed as follows.

Let $\displaystyle n=2\in \mathbb{S}$ (because n cannot be less than 2, by definition). Then we have:

$\displaystyle \left(\begin{matrix}2 \\2 \\\end{matrix}\right)=\left(\begin{matrix}2+1 \\3 \\\end{matrix} \right)$

or

$\displaystyle \left( \begin{matrix}2 \\2 \\\end{matrix}\right)=\left(\begin{matrix}3 \\3 \\\end{matrix} \right)$

which, when expended, gives:

$\displaystyle \frac{2!}{2!(2-2)!}=\frac{3!}{3!(3-3)!}$

which simplifies to:

$\displaystyle \frac{1*2}{1*2(0!)}=\frac{1*2*3}{1*2*3(0!)}$

which reduces to:

$\displaystyle 1=1$

and so the statement is true when n=1.

Now, assume that the statement is true for $\displaystyle k\in \mathbb{S}$

$\displaystyle \left(\begin{matrix}2 \\2 \\\end{matrix}\right)+\left(\begin{matrix}3 \\2 \\\end{matrix}\right)+\left(\begin{matrix}4 \\2 \\\end{matrix}\right)+...+\left(\begin{matrix}k \\2 \\\end{matrix}\right)=\left(\begin{matrix}k+1 \\3 \\\end{matrix} \right)$

Next, for k+1 we have:

$\displaystyle \left(\begin{matrix}2 \\2 \\\end{matrix}\right)+\left(\begin{matrix}3 \\2 \\\end{matrix}\right)+\left(\begin{matrix}4 \\2 \\\end{matrix}\right)+...+\left(\begin{matrix}(k+1) \\2 \\\end{matrix}\right)=\left(\begin{matrix}(k+1)+1 \\3 \\\end{matrix} \right)$

or more expansively:

$\displaystyle \left(\begin{matrix}2 \\2 \\\end{matrix}\right)+\left(\begin{matrix}3 \\2 \\\end{matrix}\right)+\left(\begin{matrix}4 \\2 \\\end{matrix}\right)+...+\left(\begin{matrix}k-1 \\2 \\\end{matrix}\right)+\left(\begin{matrix}k \\2 \\\end{matrix}\right)+\left(\begin{matrix}k+1 \\2 \\\end{matrix}\right)=\left(\begin{matrix}k+2 \\3 \\\end{matrix} \right)$

but, per our assumption that this formula holds for k, the first k terms on the LHS simply add up to:

$\displaystyle \left(\begin{matrix}2 \\2 \\\end{matrix}\right)+\left(\begin{matrix}3 \\2 \\\end{matrix}\right)+\left(\begin{matrix}4 \\2 \\\end{matrix}\right)+...+\left(\begin{matrix}k \\2 \\\end{matrix}\right)=\left(\begin{matrix}k+1 \\3 \\\end{matrix} \right)$

and so, substituting, we have:

$\displaystyle \left(\begin{matrix}k+1 \\3 \\\end{matrix}\right)+\left(\begin{matrix}k+1 \\2 \\\end{matrix}\right)=\left(\begin{matrix}k+2 \\3 \\\end{matrix} \right)$

or, rearranged:

$\displaystyle \left(\begin{matrix}k+1 \\2 \\\end{matrix}\right)+\left(\begin{matrix}k+1 \\3 \\\end{matrix}\right)=\left(\begin{matrix}k+2 \\3 \\\end{matrix} \right)$

But, using Pascal’s Rule that:

$\displaystyle \left(\begin{matrix}a \\b \\\end{matrix}\right)+\left(\begin{matrix}a \\b-1 \\\end{matrix}\right)=\left(\begin{matrix}a+1 \\b \\\end{matrix} \right)$

and letting b=3, a=k+1, we have:

$\displaystyle \left(\begin{matrix}k+1 \\2 \\\end{matrix}\right)+\left(\begin{matrix}k+1 \\3 \\\end{matrix}\right)=\left(\begin{matrix}k+2 \\3 \\\end{matrix} \right)$

but this is the identity we just worked out. Also, this is simply our original identity when k=n-1 or n=k+1.

Therefore, by the PMI, we have that

$\displaystyle \left(\begin{matrix}2 \\2 \\\end{matrix}\right)+\left(\begin{matrix}3 \\2 \\\end{matrix}\right)+\left(\begin{matrix}4 \\2 \\\end{matrix}\right)+...+\left(\begin{matrix}n \\2 \\\end{matrix}\right)=\left(\begin{matrix}n+1 \\3 \\\end{matrix}\right)$

is true of all values of $\displaystyle n\in {{\mathbb{Z}}^{+}}$ . QED

1.3 #7. For $\displaystyle n\ge 1$ , verify that:

$\displaystyle {{1}^{2}}+{{3}^{2}}+{{5}^{2}}+...+{{(2n-1)}^{2}}=\left(\begin{matrix}2n+1 \\3 \\\end{matrix} \right)$

Proof. Using the PMI, we proceed as follows.

Let $\displaystyle n=1\in \mathbb{S}$ . Then we have:

$\displaystyle {{1}^{2}}=\left(\begin{matrix}2(1)+1 \\3 \\\end{matrix} \right)$

or

$\displaystyle {{1}^{2}}=\left(\begin{matrix}3 \\3 \\\end{matrix} \right)$

which expands to:

$\displaystyle 1=\frac{3!}{3!(3-3)!}=\frac{3!}{3!0!}=\frac{3!}{3!}=1$

and so it is true for $\displaystyle n=1\in \mathbb{S}$ .

Assume it true for k so that:

$\displaystyle {{1}^{2}}+{{3}^{2}}+{{5}^{2}}+...+{{(2k-1)}^{2}}=\left(\begin{matrix}2k+1 \\3 \\\end{matrix} \right)$

is true. Now, for k+1 we have

$\displaystyle {{1}^{2}}+{{3}^{2}}+{{5}^{2}}+...+{{(2(k+1)-1)}^{2}}=\left(\begin{matrix}2(k+1)+1 \\3 \\\end{matrix} \right)$

or

$\displaystyle {{1}^{2}}+{{3}^{2}}+{{5}^{2}}+...+{{(2k+2-1)}^{2}}=\left(\begin{matrix}(2k+2+1) \\3 \\\end{matrix} \right)$

or

$\displaystyle {{1}^{2}}+{{3}^{2}}+{{5}^{2}}+...+{{(2k+1)}^{2}}=\left(\begin{matrix}2k+3 \\3 \\\end{matrix} \right)$

but this is simply the same as for k, when we set n=k+1. Therefor, we have that

$\displaystyle {{1}^{2}}+{{3}^{2}}+{{5}^{2}}+...+{{(2n-1)}^{2}}=\left(\begin{matrix}2n+1 \\3 \\\end{matrix}\right)$

is true for all $\displaystyle n\in {{\mathbb{Z}}^{+}}$ . QED

1.2 #10. The Catalan numbers, defined by

$\displaystyle {{C}_{n}}=\frac{1}{n+1}\left( \begin{matrix} 2n\\n\\\end{matrix}\right)=\frac{(2n)!}{n!(n+1)!}$

for $\displaystyle n=1,2,3,...$ so that they form the sequence:

$\displaystyle 1, 1, 2, 5, 14, 42, 132, 429,1 430, 4862, 16796...$ et cetera

For $\displaystyle n\ge 1$, prove that $\displaystyle {{C}_{n}}$, the $\displaystyle {{n}^{th}}$ Catalan number, can be given inductively by

$\displaystyle {{C}_{n}}=\frac{2(2n-1)}{n+1}{{C}_{n-1}}$

Proof. Using the PMI, we proceed as follows:

Step 1. Let n=1. And we have

$\displaystyle {{C}_{1}}=\frac{2(2(1)-1)}{1+1}{{C}_{1-1}}$

therefore, it is true for and

$\displaystyle {{C}_{1}}=\frac{2}{2}{{C}_{0}}={{C}_{0}}$

But $\displaystyle {{C}_{0}}=1$ by definition, and so $\displaystyle {{C}_{1}}=1$

Step 2. Assume the formula is true for k such that:

$\displaystyle {{C}_{k}}=\frac{2(2k-1)}{k+1}{{C}_{k-1}}$

is true.

Step 3. Now, for k+1 we have:

$\displaystyle {{C}_{k+1}}=\frac{2(2(k+1)-1)}{(k+1)+1}{{C}_{(k+1)-1}}$

or

$\displaystyle {{C}_{k+1}}=\frac{2(2k+2-1)}{k+2}{{C}_{k}}$

$\displaystyle {{C}_{k+1}}=\frac{2(2k+1)}{k+2}{{C}_{k}}$

but this is just our first formula when n=k+1. Therefore, for any

$\displaystyle {{C}_{n}}=\frac{2(2n-1)}{n+1}{{C}_{n-1}}$

holds true for any $\displaystyle n\in {{\mathbb{Z}}^{+}}$. QED

Now, we may also establish this result, namely that:

$\displaystyle {{C}_{n}}=\frac{2(2n-1)}{n+1}{{C}_{n-1}}$

directly, because it is a recurrence relation, using a little algebra, like this:

$\displaystyle {{C}_{n}}=\frac{4n-2}{n+1}{{C}_{n-1}}$

$\displaystyle =\frac{(4n-2)(4n-6)}{(n+1)n}{{C}_{n-2}}$

$\displaystyle =\frac{(4n-2)(4n-6)(4n-10)}{(n+1)n(n-1)}{{C}_{n-3}}$
. . . . .
. . . . .

$\displaystyle =\frac{(4n-2)(4n-6)(4n-10)...6\cdot 2}{(n+1)n(n-1)\cdot ...\cdot 3\cdot 2}{{C}_{0}}$

$\displaystyle =\frac{(2n-1)(2n-3)(2n-5)...3\cdot 1}{(n+1)!}\cdot {{2}^{n}}$

$\displaystyle =\frac{{{2}^{n}}(2n)!}{{{2}^{n}}n!(n+1)!}$

$\displaystyle =\frac{(2n)!}{(n+1)!n!}$

$\displaystyle =\frac{1}{n+1}\left(\begin{matrix}2n \\n \\\end{matrix} \right)$

and the result is again established. QED

One question immediately arises from this proof. Notice that from:

$\displaystyle {{C}_{n}}=\frac{2(2n-1)}{n+1}{{C}_{n-1}}$

we have immediately that:

$\displaystyle \frac{{{C}_{n}}}{{{C}_{n-1}}}=\frac{2(2n-1)}{n+1}$

and so it is natural to ask what the value of this ratio might be in the limit, especially, what does:

$\displaystyle \underset{n\to \infty }{\mathop{\lim }}\,\frac{{{C}_{n}}}{{{C}_{n-1}}}=\underset{n\to \infty }{\mathop{\lim }}\,\frac{2(2n-1)}{n+1}$

equal in the limit? Calculating this directly, we have:

$\displaystyle \underset{n\to \infty }{\mathop{\lim }}\,\frac{2(2n-1)}{n+1} \\=\underset{n\to \infty }{\mathop{\lim }}\,\frac{4n-2}{n+1} \\ =\underset{n\to \infty }{\mathop{\lim }}\,\frac{4n}{n+1}-\underset{n\to \infty }{\mathop{\lim }}\,\frac{2}{n+1} \\ =\underset{n\to \infty }{\mathop{\lim }}\,\frac{\frac{4n}{n}}{\frac{n}{n}+\frac{1}{n}}-\underset{n\to \infty }{\mathop{\lim }}\,\frac{\frac{2}{n}}{\frac{n}{n}+\frac{1}{n}} \\=\underset{n\to \infty }{\mathop{\lim }}\,\frac{4}{1+\frac{1}{n}}-\underset{n\to \infty }{\mathop{\lim }}\,\frac{2}{n+1} \\ =\underset{n\to \infty }{\mathop{4\lim }}\,\frac{1}{1+\frac{1}{n}}-2\underset{n\to \infty }{\mathop{\lim }}\,\frac{1}{n+1}$

But this limit further reduces to:

$\displaystyle 4\frac{1}{1+\underset{n\to \infty }{\mathop{\lim }}\,\frac{1}{n}}-2\frac{1}{\underset{n\to \infty }{\mathop{\lim }}\,\left( n+1 \right)}$

and because we have that:

$\displaystyle \underset{n\to \infty }{\mathop{\lim }}\,\frac{1}{n}=0$ and $\displaystyle \underset{n\to \infty }{\mathop{\lim }}\,\left( n+1 \right)=\infty$

therefore:

$\displaystyle 4\frac{1}{1+\underset{n\to \infty }{\mathop{\lim }}\,\frac{1}{n}}-2\frac{1}{\underset{n\to \infty }{\mathop{\lim }}\,\left( n+1 \right)}$

= 4(1) – 2(0) = 4

and so we have, finally, that:

$\displaystyle \underset{n\to \infty }{\mathop{\lim }}\,\frac{2(2n-1)}{n+1}=4$

and therefore, we have established that:

Lemma. The ratio of the nth Catalan number to the (n-1)th Catalan number equals 4 as n approaches infinity.

$\displaystyle \underset{n\to \infty }{\mathop{\lim }}\,\frac{{{C}_{n}}}{{{C}_{n-1}}}=4$

This also means that, for sufficiently large values of n:

$\displaystyle {{C}_{n}}\approx 4{{C}_{n-1}}$

Now, the properties for the Catalan numbers just go on and on, but here is a beautiful identity between the integer sequence of Catalan numbers and functions. This also provides the merest glimpse into the powerful techniques of analytic number theory.

There is an extension of the factorial function, called the gamma function, defined as:

$\displaystyle \Gamma (z)=\int\limits_{0}^{\infty }{{{t}^{z-1}}{{e}^{-t}}dt}$

where z is a complex variable whose real part is positive. Now, integration by parts will yield:

$\displaystyle \Gamma (z)=(z-1)\Gamma (z-1)$

and when z is an integer, we get

$\displaystyle \Gamma (n)=(n-1)!$

But the Gamma function gives values for non-integral n, so that we have, by Euler’s reflection formula that:

$\displaystyle \Gamma (1/2)=\sqrt{\pi }$

Now, treating $\displaystyle \Gamma (z)=(z-1)\Gamma (z-1)$ as a recurrence relation, we can substitute and get:

$\displaystyle \Gamma (n+\frac{1}{2})=(n-\frac{1}{2})\Gamma (n-\frac{1}{2})$

$\displaystyle =(n-\frac{1}{2})(n-\frac{3}{2})\Gamma (n-\frac{3}{2})$

$\displaystyle =(n-\frac{1}{2})(n-\frac{3}{2})...(n-\frac{2n-1}{2})\Gamma (\frac{1}{2})$

$\displaystyle =\frac{1\cdot 3\cdot 5...(2n-1)}{{{2}^{n}}}\sqrt{\pi }$

$\displaystyle =\frac{(2n)!}{{{4}^{n}}n!}\sqrt{\pi }$

this give us:

$\displaystyle \frac{\Gamma (n+\frac{1}{2})}{\Gamma (n+2)}=\frac{(2n)!}{{{4}^{n}}n!(n+1)!}\sqrt{\pi }=\frac{{{C}_{n}}}{{{4}^{n}}}\sqrt{\pi }$

and so, rearranging terms, we have established that:

The nth Catalan number may be expressed in terms of the Gamma function as:

$\displaystyle {{C}_{n}}=\frac{{{4}^{n}}\Gamma (n+\frac{1}{2})}{\sqrt{\pi }\Gamma (n+2)}$

Wednesday 25 January 2012