Day 6: CM, Page vi

But what exactly is Concrete Mathematics? It is a blend of CONtinuous and disCRETE mathematics. More concretely, it is the controlled manipulation of mathematical formulas, using a collection of techniques for solving problems.
- Concrete Mathematics, page vi

Day 6: The second page of the preface. The authors explain that although Concrete Mathematics was partially a negative reaction to the new math movement, "the main reasons for its existence were positive instead of negative" (CM p.vi). One of the main goals of Concrete Mathematics is to give students a set of tools for solving real world problems.

So what do we have to look forward to? "The major topics treated in this book include sums, recurences, elementary number theory, binomial coefficients, generating functions, discrete probability, and asymptotic methods" (CM p.vi). Hey, that sounds good! But... what does it mean?

Summation

Summation is adding numbers together. Summation uses everybody's favorite mathematical symbol, the symbol on the cover of CM:


For the programmers out there, you can think of this roughly as a for loop summing numbers in an array:

for (int i = m; i <= n; i++) {            
    sum += x[i];     
} 

Here's a "concrete" example:


Often summation is more similar to summing over a function than a pre-calculated sequence of numbers in an array. This example is similar to a for loop like:

for (int k = 2; k <= 6; k++) {              
    sum += square(k);      
} 

And of course, there are many variations on the syntax above. For example, the loop boundaries may be omitted if they are clear from the context, or the loop may be over a set rather than a sequence.

Recurrences

Recurrences are recursive functions. Recursive functions include themself in their own definition.The Fibonacci Sequence is probably the most famous example:
With seeds values of 1 and 1 for n=0 and n=1, the Fibonacci Sequence is 1, 1, 2, 3, 5, 8, 13, 21, 34,... Fractals are also often based on recurrences. The Mandlebrot fractal is one of the most famous examples.

Elementary Number Theory

According to wikipedia:

In elementary number theory, integers are studied without use of techniques from other mathematical fields. Questions of divisibility, use of the Euclidean algorithm to compute greatest common divisors, integer factorizations into prime numbers, investigation of perfect numbers and congruences belong here. Several important discoveries of this field are Fermat's little theorem, Euler's theorem, the Chinese remainder theorem and the law of quadratic reciprocity. The properties of multiplicative functions such as the Möbius function and Euler's φ function, integer sequences, factorials, and Fibonacci numbers all also fall into this area.

That all sounds familiar... but it's been a while.

Binomial Coefficients

Binomial Coefficients are so named for the binomial theorem (which we will probably return to later). They are read as "n choose k" and intuitively denote the number of ways k subsets can be chosen from a set of size n. Binomial coefficients are defined as:

To understand this formula, first start my imagining how to build unique k-sized sequences from a set of size n. You have n choices for the first element, n-1 choices for the second element, and so on down to (n - k + 1). So the probability of choosing a particular k-sized sequence is n * (n - 1) * ... * (n - k + 1). However, we are actually interested in distinct sets of elements. The same k elements in our particular sequence could also be picked in a different order and still form the same set. So how many different sequences could those k elements be picked in? k! - the number of permutations of a sequence of size k. Each of those k! sequences has an equal probability of being picked. So that particular set has a probability of being selected of k!/(n * (n - 1) * ... (n - k + 1)). Since each set has an equal opportunity of being selected, the total number of sets is the inverse of the probability of selecting a particular set, or (n * (n - 1) * (n - k + 1))/k!.

Binomial Coefficients produce many interesting patterns. For example, Pascal's Triangle is a way to calculate the binomial coefficient for any combination of n and k.

0:									1
1:								1		1
2:							1		2		1
3:						1		3		3		1
4:					1		4		6		4		1
5:				1		5		10		10		5		1
6:			1		6		15		20		15		6		1
7:		1		7		21		35		35		21		7		1
8:	1		8		28		56		70		56		28		8		1

"Row number n contains the numbers for k = 0,…,n. It is constructed by starting with ones at the outside and then always adding two adjacent numbers and writing the sum directly underneath" (wikipedia).

Within Pascal's Triangle there are also interesting patterns. For k=2, the numbers are triangular. In other words they can be drawn as a triangle. For example:

* = 1

** = 3
*

*** = 6
**
*

**** = 10
***
**
*

In the example above, the first four triangular numbers are shown: 1, 3, 6, 10. The triangular numbers can be calculated with the formula n * (n + 1) / 2. In fact, there is famous story about the mathematician, Gauss, who discovered this as a young child:

... Gauss, mathematician extrodanaire, had a lazy teacher. The “educator” wanted to keep the kids busy so he could take a nap — he asked the class to add the numbers 1 to 100 - no small feat when most kids are still learning how to carry.

Gauss walked up and showed the answer on his blackboard: 5050. The teacher thought he had cheated, but no, Gauss had figured it out by sidestepping the problem. Manual addition is for suckers, Gauss had a better way:

Sum from 1 to n =

You can understand the formula intuitively by thinking of it as a rectangle of size n and n+1 cut in half to form a triangle. This triangle, in turn, is formed of rows of size 1, 2, 3, ... n. Adding up the rows of the triangle is the same as summing from 1 to n which is the same as n(n+1)/2.

Interestingly, there is also a Triangular pattern within Pascal's Triangle for k=3. It is the sum of triangular numbers from 1 to n-2. For example, consider n=6, k=3. The binomial coefficient is 6!/3!(6-3)! = 6!/3!*3! = 6 * 5 * 4 / 3 * 2 * 1 = 120 / 6 = 20. This is also the same as the sum of the first four triangular numbers: 1 + 3 + 6 + 10 = 20. So the list of numbers in Pascal's Trinalge for k=3 and n>2 can be defined as:

Similarly, for k=4 and n>3, we have a nested summation of triangular numbers:

And for k=5 and n>4:

A pattern is starting to emerge. I'm not going to generalize on k or try to prove it for now. It's amazing that such a complicated summation can be represented by such a compact function. The results aren't something you would guess immediately, but it makes some sense if you imagine building k sized sets by iterating over an array. For k=2, you hold one pointer constant (point it at the first position) and iterate a second pointer over the rest of the elements. This forms the first row in the triangle. Next you move your first pointer to the second position. Then you iterate your second pointer over the remaining elements. This forms the second row of the triangle - it will be one element smaller than the previous row. If you repeat, it will form an entire triangle. For k=3, the pattern is similar. You hold two pointers constant and iterate a third pointer. That forms one row of a triangle. You increment your second pointer and iterate your third pointer again. This forms a second row of a triangle. You repeat until both the second and third pointers hit the end of the array. At this point, you've formed one triangle. You bump the first pointer and repeat. This begins forming a new triangle that will be one unit smaller than the previous triangle. A similar triangular pattern will be true for k=4, k=5, and so on. As you form sets by iterating over the array, each iteration creates a triangle. So all Binary Coefficients with k > 1 and k < onblur="try {parent.deselectBloggerImageGracefully();} catch(e) {}" href="http://mathforum.org/dr.math/faq/pascalfib.gif">
You can even create a Sierpinski Gasket by removing odd numbers from Pascal's Triangle. For more information about Sierpinski Gaskets and Cantor Dust, check out this link.



That's all I have time for today. We'll have to save generating functions, discrete probability, and asymptotic methods for later.