The Five Thousand Foot View (working draft)

Note: this article is intended for undergraduate math majors, preferably seniors, but freshman will benefit from the look ahead, at what is expected to be known by them when they are seniors, as well as entering graduate students.

I am readying myself for the GRE math subject exam in the late Spring, and therefore reviewing all four years of undergraduate mathematics at this time.

In what follows, I will be summarizing every major area of undergraduate mathematics, as follows:

  1. Geometry: Plane, Elliptic, Hyperbolic, and Affine
  2. Linear Algebra
  3. Vector Analysis
  4. Real Analysis
  5. Complex Analysis
  6. Topology
  7. Ordinary Differential Equations
  8. Fourier Analysis, Lebesgue Integration and General Transform Theory
  9. Probability Theory
  10. Abstract Algebra
  11. Graph Theory
  12. Combinatorics and Algorithmic Complexity
  13. Set Theory and Transfinite Arithmetic
  14. Basic & Analytic Number Theory
  15. Partial Differential Equations
  16. Differential Geometry

If you are a student of any subject, then I hope you have already asked yourself at times the question “What does all of this mean? What is it for?” if you are as I am, a mathematics major, then I believe that this question is particularly important. For one can too often get lost in the forest, standing amid the numberless trees, each one a bit different from its neighbors yet all oddly familiar, somehow similar, like wondering through a waking dream.

This is neither an idle nor a superfluous question. Call it “the big picture.” Call it what you will. It is important to know the gist and the connections between different areas of ones subject, and to know each area for what it really is about.

———————————————————————————————————————————-
Linear Algebra

Let’s look at linear algebra. The matrix is the lingua franca tool of linear algebra, and so linear algebra is the study of vector spaces and their transformations using matrices. After a first course, one should know the axioms that define a vector space, the algebra of matrices, how to express the structure of vector spaces using matrices, and especially how, given the basis of a vector space, to represent any transformation of that vector space using a matrix, and how to use and calculate eigenvalues and eigenvectors. Lastly, the key theorem of linear algebra is to know the 8 distinct conditions that each alone can guarantee a matrix is inevitable. And that is it, the heart of an entire semester of undergraduate linear algebra summarized in one paragraph. Again, in a nutshell: basic linear algebra is the study of the transformation of vector spaces into one another and understanding equivalent conditions under which a matrix is invertible.

What is linear algebra used for? Everything, and almost everywhere, is the short answer. Anytime you seek a first approximation to some problem, it is likely that you will be using linear algebra. In graph theory matrices are used to represent a graph’s structure in a precise and concise manner. In abstract algebra, matrices are used in the representation of groups and other algebraic structures. And linear algebra comes up in both ordinary and partial differential equations, differential geometry, knot theory, number theory, and almost everywhere else. Learn it well, know it well if you are going to be doing research in pure or applied mathematics.

If one takes a fourth year, second semester of linear algebra, often considered “part 2” of linear algebra studies, then one will likely encounter — inner product spaces, direct sums of subspaces, primary decomposition, reduction to triangular and Jordan forms, both rational and classical forms, dual spaces, orthogonal direct sums, bilinear and quadratic forms, and real normality — among the main topics.

Here are some great free full textbooks to download for reference or study:

Linear Algebra by Jim Hefferon. 499 pages. [direct link to whole book.]

Linear Algebra. David Cherney, Tom Denton & Andrew Waldron. 410 pages. [direct link to whole book]

-=KuRt=- © 2013 Kurt Lovelace – All Rights Reserved

The Theorem that Everyone Else Missed – A Short Proof Of Euler’s Formula

Euler’s Characteristic Formula V-E+F = 2

How is it that for thousands of years the best minds in mathematics did not see the fundamental relationship that, in any regular polyhedron, the sum of the vertices and faces minus the edges equals two? Although this question is interesting, no attempt will be made to answer it. Yet the question, merely by being asked, serves to highlight the tremendous stature of Leonard Euler.

Euler worked from first principles, digging into a topic by performing calculations to get a feel for the shape and edges of a problem, then developed conjectures and proofs based on such research. And so, Euler must have tabulated the edges, faces and vertices of shapes such as the platonic solids to thereby notice this relationship. Perhaps it took an almost childlike playfulness to discover this relationship. Yet it is all speculation. The only fact is that Euler did discover that V-E+F=2 where V, E, and F are, respectively, the vertices, edges and faces of a regular polyhedron

I first learned of Euler’s formula in a senior course on graph theory taught by the Polish graph theorist Dr. Siemion Fajtlowicz. Therefore, let me provide a few definitions before offering a compact proof that V-E+F=2 using basic graph theoretical methods.

Definition. A graph consists of a non-empty set of vertices and a set of edges, possibly empty. If an edge E exists, then it will be related to an unordered pair (a,b) of vertices in V. We may write G=(\{V\},\{E\}) to denote the graph.

A graph is finite if both the vertex set and edge set are finite. A graph that is not finite is infinite. The size of a graph is the number of vertices. The order of a graph is the number of edges. All graphs discussed in this article are finite.

Immediately note that if we are given one edge, then there exist two vertices — because an edge must connect to something and that something will always be a vertex. Two vertices are incident if they share a common edge and said to be adjacent. An edge with identical ends is called a loop while an edge with distinct ends is called a link. A graph is simple if it has no loops.

The degree d(v) of a vertex in a graph G is equal to the number of edges in G incident with v where each loop counts as two edges. Thus, a vertex with two edges has degree 2 because the degree of the other two vertices would be one each, and so the sum of the degrees of all the vertices would be 4. From this we have immediately the following two theorems.

Theorem 1. The sum of the degree of the vertices of a graph equals twice the number of edges. That is

\displaystyle \sum\limits_{i/G}{d({{v}_{i}})}=2e

proof. If a graph has no edges, then e=0 and the theorem is true because the sum of the degree of the vertices of a graph with no edges must, by definition, be zero. If a given vertex has an edge, then there must be a second vertex connected to the first vertex by the given edge and so the sum of the degree of the vertexes will be 2, even if the edge were a loop beginning and returning to a single vertex the degree of that vertex due to the loop would still be 2.

Now, each additional edge added to the graph will increase either the degree of the vertex it is connect to and add one additional vertex or else it will add one degree each to two vertices that already exist. Thus, each time an edge is added, the degree count of the vertices increases by 2. Therefore, the sum of the degree of all the vertices will always be simply twice the number of edges present.

Theorem 1.1 The number of vertices in a graph of odd degree is even.

proof. Let {{v}_{1}},{{v}_{2}} be sets of vertices where the {{v}_{1}} is of odd degree and {{v}_{2}} is of even degree. Then, from Theorem 1, we must have that

\sum\limits_{i/G}{d({{v}_{1}})}+\sum\limits_{i/G}{d({{v}_{2}})}=\sum\limits_{i/G}{d(v)}

but we have already established that

\sum\limits_{i/G}{d({{v}_{i}})}=2e

and therefore we must have

\sum\limits_{i/G}{d({{v}_{1}})}+\sum\limits_{i/G}{d({{v}_{2}})}=2e

\sum\limits_{i/G}{d({{v}_{1}})}=2e-\sum\limits_{i/G}{d({{v}_{2}})}

but

\sum\limits_{i/G}{d({{v}_{2}})}=2{{e}_{2}}

so

\sum\limits_{i/G}{d({{v}_{1}})}=2e-2{{e}_{2}}=2(e-{{e}_{2}})=2{{e}_{1}}

is even. Thus, we have that the sum of the vertices in a graph of odd degree is even. Now, we will need the following definitions to proceed.

Definition. A cycle is a closed chain of edges. A connected graph that contains no cycles is a tree.

Definition. A spanning tree of a graph G is one that uses every vertex of G but not all of the edges of G.

Every connected graph G contains a spanning tree T as a subgraph of G.

Definition. A planer graph is one that can be drawn in the plane without crossing any edges.

Definition. A face in the plane consists of both unbounded and bounded regions.

The last definition allows us to say that the number of “faces” of a finite line segment in the plane is 1, but that the number of faces of an infinite line is 2, one for each side that the line divides the plane into, and that the number of faces of a circle in the plane is 2, one corresponding to the inside and the other to the outside of the circle one being the unbounded and the other the bounded region.

Now we are ready to prove Euler’s formula as it may be stated in graph theory.

Theorem 2. If G is a connected planer graph with vertices v, edges e, and faces f, then

\displaystyle v-e+f=2

proof. Let T be a spanning tree of a graph G. Then the number of faces f=1 and the number of edges e= v – 1 is true for the spanning tree T of G and so we have v-(v+1)+(1)=2 and our formula is true. Now, G may be constructed from T by adding edges to T, but each time we do so we are adding a new face to T. Therefore, with the addition of each new edge, e will increase by 1 and f will increase by 1. Therefore, all of these additions cancel out and we have our formula.

Now, a homomorphism exists between polyhedron and graphs in that a connected plane graph can be uniquely associated with a polyhedron by making any face the flat unbounded part of the plane. Therefore, Euler’s formula is true for polyhedron. We can therefore immediately prove:

Theorem 3. Exactly five platonic solids exist.

proof. Let the number of edges and faces be n and the number of edges each vertex is incident to be d. If we multiply nf, we get twice as many edges because each edge belongs to two faces, so nf is the number of faces multiplied by the number of edges on each face. Likewise, with dv each edge is incident to two faces so that we have dv=2e so that we have the equality

nf=2e=dv

or

e=\frac{dv}{2} and f=\frac{dv}{n}

Now, placing these into Euler’s formula, we get

v+\frac{dv}{n}-\frac{dv}{2}=2

or

(2n+2d-dn)v=4n

But both v and n are positive integers and for (2n+2d-dn)v=4n to be true, we must have that

2n+2d-dn>0

or

(n-2)(d-2)<4

and so there are just five possibilities for the values of n and d and each of these corresponds to one of the five platonic solids, so that we have

n=3,d=3 is a tetrahedron
n=3,d=4 is a hexahedron also known as a cube
n=4,d=3 is a octahedron
n=3,d=5 is a dodecahedron
n=5,d=3 is a icosahedron

the 5 Platonic Solids

QED.

© 2012 Kurt Lovelace – All Rights Reserved

Graph Isomorpshism and Coloring

This week, Professor Siemion Fajtlowicz assigned two home work problems:

1. How many graphs with vertices 1 … n are there?

2. Up to isomorphism, how many graphs are there with n vertices?

3. If you invite 6 random people to a party, show that 3 of them will know each other or 3 of them will be mutual strangers — and show that this is guaranteed to always be the case — but only if you invite a minimum of 6 random people to the party. It will not be the case if we only invite 5 random people or 4 random people, et cetera.

____________________________________________________________________________________________________________________________
Question 1 and 2 may appear to be identical questions, but they are not at all identical though they are related.

Question 1 is asking for the number of elements of S. Question 2 is asking for the number of elements of the quotient G\S, a very different and much more difficult question.

Theorem. There are

\displaystyle {{2}^{\left( \begin{matrix} n \\ 2 \\ \end{matrix} \right)}}

graphs with vertex set \displaystyle \{1,2,3,...,n-1,n\} .

Proof. The question is easily answered. Given n vertexes, if we start from vertex 1 and connect an edge to each of the remaining vertexes, so that 1 goes to 2, 1 goes to 3, and so on until 1 goes to (n-1) , and 1 goes finally to n. Now, including the null edge or simply 1 itself connected to nothing, which is a legitimate graph, we have that there are n graphs. Repeating this for each additional vertex, and taking into account that the edge may originate at either one of the vertexes making for two graphs — if allowing full duplicates — then we will have that there are exactly,

\displaystyle ^{1+2+3+...+(n-1)+n}

possible graphs raised to the power of 2 to account for starting at either vertex, which gives us:

\displaystyle {{2}^{1+2+3+...+(n-1)+n}}={{2}^{\sum\limits_{i/{{\mathbb{Z}}_{+}}}{i}}}={{2}^{\frac{n(n+1)}{2}}}

Therfore, the number of graphs with vertices 1 to n are:

\displaystyle {{2}^{\left( \begin{matrix} n \\ 2 \\ \end{matrix} \right)}}

and this is simply a more compact way of writing the RHS of the previous result using binomial coefficients. QED

____________________________________________________________________________________________________________________________

Theorem. Up to isomorphism, there are

\displaystyle \frac{1}{n!}\sum\limits_{n\in \sum\nolimits_{n}{{}}}{{{2}^{o\left( \sigma \right)}}}

graphs with n vertices.

The answer to the question is much more difficult, because the answer involves some hefty but basic machinery from Group Theory and Combinatorics involving Burnside’s Lemma and Polya’s Enumeration Theorem such that this question may be reworded in those terms, so that it becomes:

How large is the set \displaystyle \sum\nolimits_{n}{{}}\backslash S where \displaystyle \sum\nolimits_{n}{{}} denotes the symmetric group on n letters and \displaystyle S is the set of graphs with vertex set \displaystyle {1,2,3,...,n-1,n} ?

The answer is

\displaystyle \frac{1}{n!}\sum\limits_{n\in \sum\nolimits_{n}{{}}}{{{2}^{o\left( \sigma \right)}}}

where \displaystyle o\left( \sigma \right) denotes the number of \displaystyle \sigma orbits on the set.

____________________________________________________________________________________________________________________________

At any party with 6 guests, either 3 are mutual friends or else 3 are mutual strangers. That is, the symmetric Ramsey Number R(3,3) = 6

If we consider just one person, then the other five must fall into one of the two classes of being either a friend or a stranger. This follows immediately from the pigeonhole principle, namely that, if m pigeons occupy n holes where \displaystyle n<m , then at least one hole contains:

\displaystyle \left\lfloor \frac{m-1}{n} \right\rfloor +1

pigeons, where \displaystyle \left\lfloor {} \right\rfloor is the greatest integer function. The proof of this follows from the fact that the largest multiple of n that divides into m is the fractional part left over after n divides m-1 or

\displaystyle \left\lfloor \frac{m-1}{n} \right\rfloor

and so for n pigeons, we get

\displaystyle n\left\lfloor \frac{m-1}{n} \right\rfloor

pigeons that could be put into \displaystyle \left\lfloor \frac{m-1}{n} \right\rfloor holes. But we have m pigeons, and so there must be more than this many pigeons in the holes.

Now, for our problem, we have two classes, friends and strangers. If we choose one person, then that leaves 5 people with whom that person is either a friend or a stranger. And so, by the pigeonhole principle, for five objects going into two classes we must have at least:

\displaystyle \left\lfloor \frac{5-1}{2} \right\rfloor +1=3

members in one of the classes. In terms of a graph theoretical viewpoint, we have, starting with one vertex extended out to the other five “people” vertexes, that:

where the red edges represent friends and the blue edges represent strangers. We easily see that, regardless of how we choose one of our 2 colors, 3 of them must be blue or else 3 of them must be red, for if we have five red, then we have met the required condition that at least 3 be red, and likewise if 4 are red, we again fulfill the requirement that at least 3 be red; and so, this whole sequence of argument applies if we swap blur for red. Therefore, we are always guaranteed that there are 3 mutual friends or else that there are 3 mutual strangers in any group of 6 people. QED

In terms of Ramsey Numbers, the statement would be written \displaystyle R(3,3)=6 .

This is utterly fascinating, because what this is really telling us it that there is a type of structure built into any random finite set. In this case, for any binary operation or else any question or property that has two values, we have it that any finite set of 6 is sufficient to support there being 3 of one or 3 of the other of that property, and that one of the two sets of 3 always exists inside of the 6 items.

This is a glimpse into a type of “deep structure” embedded within the fabric of finite sets. This is more than merely surprising, as one should not really be expecting to find any such structure whatsoever in a random set.
____________________________________________________________________________________________________________________________

Going somewhat beyond this homework problem, from experimental math studies using Mathematica, I conjecture that:

\displaystyle R(n,n)=\frac{1}{12}(3{{n}^{4}}-20{{n}^{3}}+63{{n}^{2}}-82n+48)

holds for n<=20 in a completely trivial and weak algebraic sense that the Ramsey Numbers in this range do indeed appear in this formula.

However, there is no natural or reasonable theoretical connection whatsoever between this formula and Ramsey Numbers other than the search for generating functions and sequence matching studies that I conducted. So, for n = 3 to 20 this formula yields:

\displaystyle \text{R(3,3) = 6}
\displaystyle \text{R(4,4) = 18}
\displaystyle \text{R(5,5) = }49
\displaystyle \text{R(6,6) = }116
\displaystyle \text{R(7,7) = }242
\displaystyle \text{R(8,8) = }456
\displaystyle \text{R(9,9) = }793
\displaystyle \text{R(10,10) = }1,294
\displaystyle \text{R(11,11) = }2,006
\displaystyle \text{R(12,12) = }2,982
\displaystyle \text{R(13,13) = }4,281
\displaystyle \text{R(14,14) = }5,968
\displaystyle \text{R(15,15) = }8,114
\displaystyle \text{R(16,16) = }10,796
\displaystyle \text{R(17,17) = }14,097
\displaystyle \text{R(18,18) = }18,106
\displaystyle \text{R(19,19) = }22,918
\displaystyle \text{R(20,20) = }28,634

which all fall nicely into current best-known intervals for these numbers. But these values are essentially nonsense. However, it is currently believed that \displaystyle \text{R(5,5) = }43 rather than 49. But there is no polynomial expression that yields 43 and the other lower already known numbers in the sequence of Ramsey Numbers evident from running long and large searches for such. Therefore, I believe that any meaningful approximate or asymptotic formula must be non-polynomial.

Therefore, my intuition says that there may well exist an exponential, non-polynomial expression for the Ramsey Numbers — perhaps similar to the P(n) function of Rademacher such as

\displaystyle p(n)=\frac{1}{\pi \sqrt{2}}\sum\limits_{k=1}^{\infty }{\sqrt{k}}{{A}_{k}}(n)\frac{d}{dn}\left( \frac{1}{\sqrt{n-\frac{1}{24}}}\sinh \left[ \frac{\pi }{k}\sqrt{\frac{2}{3}\left( n-\frac{1}{24} \right)} \right] \right)

where

\displaystyle {{A}_{k}}(n)=\sum\limits_{0\le m<k;\ (m,k)=1}{{{e}^{\pi i\left[ s(m,k)\ -\ \frac{1}{k}2nm \right]}}}.

But then I may be dreaming here because there need be no sequential connection between one of these numbers and the other — if each is a unique value in it’s own problem space.

What I find frustrating with papers on Ramsey Numbers that I have read is their lack of a more probing approach. We know that calculating Ramsey Numbers is NP-hard. One paper even suggested that this is Hyper-NP hard — but did not specify in what manner they meant this to be true. Most likely they were referring to the absurdly rapid exponential growth of the possible solution space. But where are the more basic insights into the nature of these numbers? Most of what we have now is not much beyond Paul Erdős work in the 1930’s!

In a recent paper on Ramsey Numbers, the physicist Kunjun Song, said: “Roughly speaking, Ramsey theory is the precise mathematical formulation of the statement: Complete disorder is impossible. or Every large enough structure will inevitably contain some regular substructures. The Ramsey number measures how large on earth does the structure need to be so that the speci ed (sic.) substructures are guaranteed to emerge.”

I think that we have yet to ask ourselves the deeper questions to get further along here. I am now researching the different ways in which the same questions may be asked, such as via Shannon limits of graphs and quantum algorithms to see what pure mathematical insight might be gleamed from these approaches. I am looking for good questions that, if properly phrased, should provide a road-map for further fruitful research.

© 2012 Kurt Lovelace – All Rights Reserved

Introduction to Graph Theory

This was the first week of my senior-level class with Professor Siemion Fajtlowicz, MATH 4315 – Graph Theory, and it was a blast!

The central question put to the class is when are two graphs isomorphic. There is nothing easy nor trivial about this question. It can be challenging to even distinguish that two simple graph representations are of different graphs, let alone of the same graph.

Also, we have been assigned the task of showing how one is to interpret the historically notable problem, first presented to and solved by Leonhard Euler in 1735, of the Seven Bridges of Königsberg in a graph theoretic manner. Euler resolved this question in the negative, but there is a lot more to it than that, as we will see in this article.

Along with this problem, we have also been assigned the Knight’s Tour problem which we are also to interpret in a graph theoretic fashion.

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