Divisiblity and the GCD

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 2. 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.

Basic Divisibility Theory of the Integers

2.2 – 5. For \displaystyle n\ge 1 , prove that \displaystyle n(n+1)(2n+1)/6 is an integer.

Proof. By the division algorithm, if \displaystyle 6|n(n+1)(2n+1) , we may write

\displaystyle n(n+1)(2n+1)=6q+r where \displaystyle 0\le r\le 6 . Therefore, since r may only assume integer values, we have that \displaystyle n(n+1)(2n+1) may only assume any one of the following six forms, corresponding to each value of the remainder \displaystyle r=0,1,2,3,4,5 so that n must be in one of the following forms:

\displaystyle n=6q , \displaystyle n=6q+1 , \displaystyle n=6q+2 , \displaystyle n=6q+3 , \displaystyle n=6q+4, \displaystyle n=6q+5

Therefore, we need only substitute each of these in our expression \displaystyle n(n+1)(2n+1)/6 and simplify to see what results. So, proceeding on a case by case basis, we have, for the first case:

\displaystyle n(n+1)(2n+1)/6 for \displaystyle n=6q we get

\displaystyle \frac{6q(6q+1)(2(6q)+1)}{6}=\frac{432{{q}^{3}}+108{{q}^{2}}+6q}{6}

\displaystyle =72{{q}^{3}}+18{{q}^{2}}+q

which is an integer, as there are no fractions left on the RHS. Now, in the second case:

\displaystyle n(n+1)(2n+1)/6 for \displaystyle n=6q+1 we get

\displaystyle \frac{(6q+1)((6q+1)+1)(2(6q+1)+1)}{6}=\frac{432{{q}^{3}}+324{{q}^{2}}+78q+6}{6}

\displaystyle =72{{q}^{3}}+54{{q}^{2}}+13q+1

which is also clearly an integer. And, in the third case:

\displaystyle n(n+1)(2n+1)/6 for \displaystyle n=6q+2 we get

\displaystyle \frac{(6q+2)((6q+2)+1)(2(6q+2)+1)}{6}=\frac{432{{q}^{3}}+540{{q}^{2}}+222q+30}{6}

\displaystyle =72{{q}^{3}}+90{{q}^{2}}+37q+5

which is also clearly an integer. And, in the fourth case:

\displaystyle n(n+1)(2n+1)/6 for \displaystyle n=6q+3 we get

\displaystyle \frac{(6q+3)((6q+3)+1)(2(6q+3)+1)}{6}=\frac{432{{q}^{3}}+756{{q}^{2}}+438q+84}{6}

\displaystyle =72{{q}^{3}}+126{{q}^{2}}+73q+14

which is also clearly an integer. And, in the fifth case:

\displaystyle n(n+1)(2n+1)/6 for \displaystyle n=6q+4 we get

\displaystyle \frac{(6q+4)((6q+4)+1)(2(6q+4)+1)}{6}=\frac{432{{q}^{3}}+972{{q}^{2}}+726q+180}{6}

\displaystyle =72{{q}^{3}}+162{{q}^{2}}+121q+30

which is also clearly an integer. And, in the sixth case:

\displaystyle n(n+1)(2n+1)/6 for \displaystyle n=6q+5 we get

\displaystyle \frac{(6q+5)((6q+5)+1)(2(6q+5)+1)}{6}=\frac{432{{q}^{3}}+1188{{q}^{2}}+1086q+330}{6}

\displaystyle =72{{q}^{3}}+198{{q}^{2}}+181q+55

and this too is an integer. Therefore, for all values of \displaystyle n\ge 1 , we have established that

\displaystyle \frac{n(n+1)(2n+1)}{6}

is an integer for all \displaystyle n\ge 1 . QED

Note. Of course, this expression is also the sum of the squares of the first n integers, or

\displaystyle {{1}^{2}}+{{2}^{2}}+{{3}^{2}}+...+{{n}^{2}}=\frac{n(n+1)(2n+1)}{6}

for all \displaystyle n\ge 1 and so, because the square of an integer is an integer, so would be a sum of squares of integers, and so this may be developed out into another proof, as a corollary, by obtaining and proving the summation formula itself it would follow that it is an integer.


2.2 – 11. If n is an odd integer, show that \displaystyle {{n}^{4}}+4{{n}^{2}}+11 is of the form 16k.

Proof. Assume that n has the form \displaystyle n=2k+1 so that n is odd. Then, by direct substitution and upon simplification, we have

\displaystyle {{(2n+1)}^{4}}+4{{(2k+1)}^{2}}+11

\displaystyle =(16{{k}^{4}}+16{{k}^{3}}+16{{k}^{2}}+8k+1)+(8k+4)+11

\displaystyle =16{{k}^{4}}+16{{k}^{3}}+16{{k}^{2}}+(8+8)k+(1+4+11)

\displaystyle =16{{k}^{4}}+16{{k}^{3}}+16{{k}^{2}}+16k+16

\displaystyle =16({{k}^{4}}+{{k}^{3}}+{{k}^{2}}+k+1)=16K

where

\displaystyle K={{k}^{4}}+{{k}^{3}}+{{k}^{2}}+k+1 .

Therefore, \displaystyle {{n}^{4}}+4{{n}^{2}}+11 is of the form 16K for all odd positive integers. QED


2.3 – 3. Prove or disprove: if \displaystyle a|(b+c) , then either \displaystyle a|b or \displaystyle a|c .

Proof. By counterexample, we have

\displaystyle 18|7+11 but \displaystyle 18|7 false and \displaystyle 18|11 is false.

So, without loss of generality, we may say that,

if \displaystyle b<a and \displaystyle c<a but \displaystyle b+c=a , then it is true that:

\displaystyle a|(b+c) or more fully, that \displaystyle \frac{b+c}{a}=\frac{a}{a}=1 and we see that \displaystyle a|b and \displaystyle a|c are both false. QED.


2.3 – 4. For \displaystyle n\ge 1 , use mathematical induction to establish the following divisibility statement that

\displaystyle 15|{{2}^{4n}}-1 .

Proof. Using the PMI, we have for \displaystyle n=1 ,

\displaystyle \frac{{{2}^{4(1)}}-1}{15}=\frac{{{2}^{4}}-1}{15}=\frac{16-1}{15}=\frac{15}{15}=1

or

\displaystyle ({{2}^{4}}-1)=1\cdot 15+0

and therefore it is true that

\displaystyle 15|{{2}^{4n}}-1

when n=1. Assume that for some positive integer k that

\displaystyle 15|{{2}^{4k}}-1

is true and note that this also means that:

\displaystyle 3\cdot 5|{{2}^{4k}}-1

or that

\displaystyle {{2}^{4k}}-1=15q

or

\displaystyle {{2}^{4k}}-1=3\cdot 5\cdot q

for some multiple q of 15. But the LHS factors into:

\displaystyle {{2}^{4k}}-1=({{2}^{k}}+1)({{2}^{2k}}+1)({{2}^{k}}-1)

which implies that:

\displaystyle 3\cdot 5|({{2}^{k}}+1)({{2}^{2k}}+1)({{2}^{k}}-1)

or

\displaystyle ({{2}^{k}}+1)({{2}^{2k}}+1)({{2}^{k}}-1)=3\cdot 5\cdot q

and now this implies that, either:

\displaystyle 3|{{2}^{k}}+1

or else

\displaystyle 3|{{2}^{2k}}+1

or else

\displaystyle 3|{{2}^{k}}-1

and likewise for 5, that either:

\displaystyle 5|{{2}^{k}}+1

or else

\displaystyle 5|{{2}^{2k}}+1

or else

\displaystyle 5|{{2}^{k}}-1

one of which must be true and for each of the integers 3 and 5. Now, for (k+1) we have that:

\displaystyle \frac{{{2}^{4(k+1)}}-1}{15}=\frac{{{2}^{4k+4}}-1}{15}=q+r

or

\displaystyle {{2}^{4k+4}}-1=15q

or

\displaystyle {{2}^{4k+4}}-1=3\cdot 5\cdot q

where q is the quotient and r must equal 0 if 15 is to divide exactly into \displaystyle {{2}^{4k+4}}-1 . Now, by factoring, we have that:

\displaystyle {{2}^{4k+4}}-1=({{2}^{k+1}}+1)({{2}^{2k+2}}+1)({{2}^{k+1}}-1)

so that we have also:

\displaystyle ({{2}^{k+1}}+1)({{2}^{2k+2}}+1)({{2}^{k+1}}-1)=15q

or

\displaystyle ({{2}^{k+1}}+1)({{2}^{2k+2}}+1)({{2}^{k+1}}-1)=3\cdot 5\cdot q

but each of these factors is simply the same as the assumed case n=k when n=k+1. And it is already true, by assumption, that

\displaystyle 3\cdot 5|({{2}^{k}}+1)({{2}^{2k}}+1)({{2}^{k}}-1)

or

\displaystyle 3\cdot 5|{{2}^{4k}}-1

Therefore, by the PMI, we have that,

\displaystyle 15|{{2}^{4n}}-1

for all

\displaystyle n\ge 1 , \displaystyle n\in {{\mathbb{Z}}^{+}}. QED


2.3 – 13 Given two integers a and b, prove the following: there exists integers x and y for which \displaystyle c=ax+by if and only if \displaystyle \gcd (a,b)|c.

Proof. This is almost the converse of theorem 2.4 on page 23, namely that, if a and b are both integers not equal to zero, then a and b are relatively prime if and only if there exist integers x and y such that \displaystyle 1=ax+by . From this we have that, if \displaystyle \gcd (a,b)=1 , then:

\displaystyle 1=ax+by but from corollary 1 to the theorem 2.4, both on page 23, we have that if \displaystyle \gcd (a,b)=d then \displaystyle gdc(a/d,b/d)=1 and this implies that:

\displaystyle 1=\left( \frac{a}{d} \right)x+\left( \frac{b}{d} \right)y

but multiplying both sides of this by d and setting d=c yields:

\displaystyle c=ax+by

but this means that \displaystyle \gcd (a,b)=c but c|a and c|b and therefore \displaystyle \gcd (a,b)|c because \displaystyle \frac{\gcd (a,b)}{c}=\frac{c}{c}=1 . QED


2.3 – 13(b) If there exist integers x and y for which \displaystyle ax+by=\gcd (a,b), then \displaystyle \gcd (x,y)=1 .

Proof. This is theorem 2.4 where the terms are inverted. We have, by theorem 2.4, that a and b are relatively prime if and only if there exists integers x and you such that \displaystyle 1=ax+by . Now, suppose that \displaystyle 1=ax+by for some choice of x and y, such that \displaystyle =\gcd (a,b). Because \displaystyle |a and \displaystyle |b , by theorm 2.2 we get that \displaystyle |(ax+by)or \displaystyle =0 but this last condition forces d to be 1. Therefore, \displaystyle \gcd (x,y)=1 must be true. QED


2.3 – 20(e). Confirm the following properties of the greatest common divisor. If \displaystyle \gcd (a,b)=1 and \displaystyle |ac and \displaystyle |bc , then \displaystyle |c .

Proof. We are given that a and b are relatively prime, which means that:

\displaystyle 1=ax+by for some linear combination of a and b their exist such integers x and y that this is true. Now, if \displaystyle |ac and \displaystyle |bc means that \displaystyle ac=qd+r and \displaystyle bc={{q}^{'}}d+{{r}^{'}} for some q, q’, r, r’. Therefore, we must have that d divides either a or c, given that \displaystyle d|ac , and likewise, d must divide either b or c, given that \displaystyle d|bc .

Assume, in the first case, that d divides a but not c. And assume that, in the second case, that d divides b but not c also. Then we would have \displaystyle a={{q}_{1}}d+{{r}_{1}}and \displaystyle b={{q}_{1}}^{'}d+{{r}^{'}}_{1} or subtracting these from the other set, that:

\displaystyle ac-a=q-{{q}_{1}}d+(r-{{r}_{1}})

or

\displaystyle a(c-1)=(q-{{q}_{1}})d+(r-{{r}_{1}})

and

\displaystyle c-b={{q}^{'}}-{{q}_{1}}^{'}d+({{r}^{'}}-{{r}_{1}}^{'})

or

\displaystyle (c-1)=({{q}^{'}}-{{q}_{1}}^{'})d+({{r}^{'}}-{{r}_{1}}^{'})

but a and b are relatively prime implies, if d dives both a and b, then:

\displaystyle 1=\left( \frac{a}{d} \right)x+\left( \frac{b}{d} \right)y

or

\displaystyle d=ax+by

but since it is also true that \displaystyle d|ac and that \displaystyle d|bc each implies that \displaystyle \gcd (d,a)=1 and that the \displaystyle \gcd (d,b)=1 respectably, which is a contradiction. Therefore, d must divide c if \displaystyle d|ac and \displaystyle d|bc . QED

2.3 – 21.
(a) Prove that if \displaystyle d|n , then \displaystyle {{2}^{d}}-1|{{2}^{n}}-1 .

Proof. First off, if \displaystyle d|n , then there exists a q and r such that:

\displaystyle n=qd+r where \displaystyle 0\le r\le d and so, we are being asked to prove that:

\displaystyle ({{2}^{n}}-1)=q({{2}^{d}}-1)+r where \displaystyle 0\le r\le ({{2}^{d}}-1)

Now, from first principles, because \displaystyle d|n , we must have that:

\displaystyle d<n

or else there could be no division by d into n in integer terms, and so therefore, we also have:

\displaystyle {{a}^{d}}<{{a}^{n}} for some positive integer \displaystyle a\ge 1 because \displaystyle d<n . Note that this implies that \displaystyle 1<\frac{{{a}^{n}}}{{{a}^{d}}}={{a}^{n-d}} . Now, subtracting one from both sides yields:

\displaystyle {{a}^{d}}-1<{{a}^{n}}-1

And, because \displaystyle d<n implies that \displaystyle {{a}^{d}}<{{a}^{n}} , and this implies that \displaystyle {{a}^{d}}-1<{{a}^{n}}-1 , upon division of the RHS by the LHS, yields:

\displaystyle 1b>0 , then \displaystyle a+b\le ab , and so, if the \displaystyle \gcd (a,b)=1 , then

\displaystyle a=k\cdot b+0 for some \displaystyle k>0 . Now, without loss of generally, taking \displaystyle a=k\cdot b and

substituting, we have:

\displaystyle \gcd (a+b,ab)=\gcd (kb,(kb)b)=\gcd (kb,k{{b}^{2}})

but this implies that

\displaystyle kb=kb\cdot b+0

or

\displaystyle kb=k{{b}^{2}}+0

or dividing both sides by b

\displaystyle k=kb+0

which implies that

\displaystyle \gcd (k,b)=1 and likewise argument if we go substituting \displaystyle a=k\cdot b but this is just \displaystyle \gcd (k,b)=\gcd (kb,k{{b}^{2}})=\gcd (kb,(kb)b)=\gcd (a+b,ab)=1 and therefore, if \displaystyle \gcd (a,b)=1 , then \displaystyle \gcd (a+b,ab)=1 . QED


2.4 – 9. Prove that the greatest common divisor of two positive numbers a and b divides their least common multiple, especially that \displaystyle \frac{lcm(a,b)}{\gcd (a,b)} .

Proof. By merging the definitions of the gcd and lcm of two integers, a and b, we have that the gcd of a and b is the positive integer d satisfying the following:

(a) \displaystyle d|a and \displaystyle d|b
(b) if \displaystyle c|a and \displaystyle c|a , then \displaystyle c\le d

and the lcm of two positive integers a and b is the positive integer m satisfying:

(a) \displaystyle a|m and \displaystyle b|m
(b) If \displaystyle a|c and \displaystyle b|c , with \displaystyle c>0 , then \displaystyle m\le c

but \displaystyle d|a and \displaystyle a|m , therefore \displaystyle d|m and \displaystyle m\le c\le d because \displaystyle c\le d and \displaystyle m\le c . Again, we have that \displaystyle d|b and \displaystyle b|m , therefore \displaystyle d|m and \displaystyle m\le c\le d because \displaystyle c\le d and \displaystyle m\le c . Therefore, we see that the gcd does indeed divide the lcm, and we have established that

\displaystyle \gcd (a,b)|lcm(a,b) .

QED


Saturday 28 January 2012
© Kurt Lovelace all right reserved

Elementary Binomial Proofs and Catalan Numbers

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
© Kurt Lovelace all rights reserved

Human Pitch Perception Follows a GCD Formula

Given two integers n and m, their Greatest Common Divisor or GCD is defined as the largest number that divides into both n and m. So, given 6 and 35, for example, we have that the GCD(6,35) = (2·3,5·7) = 1, and likewise, the GCD of 121 and 44, or GCD(121,44) = GCD(11·11,4·11)= 11 because 11 is the largest number that divides into both 121 and 44.

But there is a very unexpected application of the GCD going on every second inside our own heads, as Manfred Schroder* goes on to say:

“An interesting and most surprising application of the GCD occurs in human perception of pitch: the brain, upon being presented with a set of harmonically related frequencies, will perceive the GCD of these frequencies as the pitch. Thus, the subjective pitch of the two-tone chord (320 Hz and 560 Hz) is (320,560) = 80Hz, and not the difference frequency (240 Hz).

Upon a frequency shift of +5Hz applied to both frequencies, the GCD drops to 5 Hz; and for an irrational frequency shift, the GCD even drops to 0 Hz. But that is not what the ear perceives as the pitch. Rather it tries to find a close match in the range of pitches above 50 Hz. For the frequencies 325 Hz and 565 Hz such a match is given by 81 Hz, which is the GCD of 324 Hz and 567 Hz – close to the two given frequencies.

Note that the concept that pitch is given by the difference frequency or “beat” frequency has been beaten: if both frequencies are shifted by the same amount, their difference remains unchanged. Yet psycho-acoustic experiments clearly show that the perceived pitch is increased, from 80 Hz to about 81 Hz in our example, just as the amplified GCD model predicts.

What this tells us is that the human brain switches on something like a GCD spectral matching computer program when listening to tone complexes. Fascinating? Indeed. Unbelievable? Well, the brain has been caught doing much trickier things than that.”

[ Technical Notes ]


The GCD appears in the solution to many, seemingly unrelated, problems. For example, take n jugs with capacities of L1, L2, . . . , Ln liters. What amounts k of water (or wine) can be dispensed by these n/1 jugs?

Answer: k must be a multiple of the GCD. Now, to better understand the GCD and its counterpart, the LCM, we will need more math.

Fundamental theorem of arithmetic. Each natural number n > 1 is either a prime or can be uniquely factored into primes

n=p_{1}^{{{e}_{1}}}p_{2}^{{{e}_{2}}}p_{3}^{{{e}_{3}}}...p_{k}^{{{e}_{k}}}...p_{r}^{{{e}_{r}}}=\prod\limits_{i}{p_{i}^{{{e}_{i}}}}

where the order of the prime factors makes no difference.

Proof. There are only two cases to consider. Either n is prime or n is composite. If n is prime, then the theorem is obviously true, by definition. Therefore, the only case we need to consider is when n is composite.

If n is composite, then there exists an integer p where p divides into n so that and 1 < p < n must be true because n is, by definition, greater than 1, and so if p divides into n, then p must be smaller than n, hence 1 < p < n as just stated. [this proof is still being written, and will be completed by the Jan 25 weekend]

It is extremely relevant to note that because there is no corresponding theorem for the additive decomposition of natural numbers into primes, this lack explains why additive number theory, when dealing with things like partitions, is so difficult.

Now, two integers n and m have a least common multiple (LCM) [n,m], and we need this every time we want to add two fractions, because we then need to find the LCM to combine two fractions with denominators n and m into a single fraction, and that is where the expression least common denominator comes from.

So, the LCM of 6 and 9 is LCM[6,9] = 18 so that:

\frac{1}{6}+\frac{2}{9}=\frac{3}{18}+\frac{4}{18}=\frac{7}{18}

So that we have, in general:

Definition. The Lowest Common Multiple or LCM of two integers n and m is defined as:

{}[n,m]=\prod\limits_{i}{p_{i}^{\max ({{e}_{i}},{{f}_{i}})}}

and likewise, given two integers, we have:

Definition. the Greatest Common Divisor or GDC is defined as:

{}(n,m)=\prod\limits_{i}{p_{i}^{\min ({{e}_{i}},{{f}_{i}})}}

and there are interesting properties between the GDC and LCM, such as that, for any two numbers n and m, the product of the GCD and the LCM equals the
product of n and m.

(n,m)[n,m]=nm

because whenever the GCD picks the exponent e of i for p of i, the LCM picks the exponent f of i, and vice versa and so:

(n,m)[n,m]=\prod\limits_{i}{p_{i}^{{{e}_{i}}+{{f}_{i}}}=nm}

and this works for three or more integers as well

(n,m,k)[n,m,k]=nmk

(n,m,k,j)[n,m,k,j]=nmkj

(n,m,k,j,l)[n,m,k,j,l]=nmkjl

Also, the direct result of the Min and Max functions in the definition of the GCD and LCD yields a “distributive law”

(k[n,m])=[(k,n),(k,m)]

[k(n,m)]=([k,n],[k,m])

And a beautiful “self-duel” relationship

([k,n],[k,m],[n,m])=[(k,n),(k,m),(n,m)]


Tuesday 17 January 2012
© Kurt Lovelace all rights reserved

*pages 25-26 of Manfred Schroder’s Number Theory in Science and Communication