Main







Applications
Identities





History
FAQ
Algorithms

Terms, symbols and FAQ
                                                               
1. What is an identity?
2. What is summation notation?  (the symbol  , the capital Greek letter sigma)
3. What is a factorial? (the symbol !)
4. What is a falling factorial, such as 64?
5. What is a binomial coefficient?
6. What is a bitstring?
7. What is modular arithmetic, as in 5 (mod 7)?
8. What is calculus?
9. What is mathematical induction?
10. What is a recursive definition?
11. What is an algorithm?
12. What is a one-to-one correspondence?
13. What are the Fibonacci numbers?
14. What is a dot product?
15. What is a difference triangle?
16. Can we define “n choose k” for values of n and k that aren’t non-negative integers where n >= k?







1. What is an identity?
In math, when two different formulas are always equal to one another, or some formula is always equal to some constant, this is known as an identity.  For instance, (a+b)2 = a2 + 2ab + b2 and (a+b)(a-b) = a2 - b2.
Among the best known are the Pythagorean Theorem stated as a2+b2=c2, or opp2 + adj2 = hyp2, where the three sides of a right triangle are called the opposite, adjacent and hypotenuse; when we have the equations for sine and cosine as and  , respectively.  These equations would be better termed definitions than identities; the main trigonometric identity    is derived directly from the Pythagorean Theorem and the definitions of sine and cosine.  In Pascal’s Triangle, there are many relationships between the numbers, and almost all of them are represented as identities.

2. What is summation notation?  (the symbol  , the capital Greek letter sigma)
Here is the Cardinal Rule of Math:  Less Writing Is Better.  
We can think of multiplication as a way to reduce the amount of writing when adding the same thing to itself some number of times; for example, 3+3+3+3+3 = 5×3 = 5+5+5.  Likewise, exponents are a shorthand way to do several multiplications by the same number, so 35 = 3×3×3×3×3.
What if the things we are adding together aren’t the same thing every time?  For example, what about 1+2+3+4+5+6?  For this, we use the summation notation  , which can be read as “the summation from i equals 1 to 6 of the term i”; in this simple summation, i is the index variable and the lines “i=1” and “6” that are written above and below the  tells us where to start and stop.  Unless specifically told otherwise, we assume that when we go from the starting value to the stopping value, we increase the value by 1 each time.

Okay, what if instead we want to add up the consecutive odd numbers, like 1+3+5+7+9?  Here, we have five separate terms, so the standard way to do this is to change the summation to ; here, we now have a slightly more complicated formula into which we will plug the index variable i as i=1, i=2, … up to i=5.
Sometimes, there is no direct formula for each entry; for example, if we want to find the average score on twenty tests we add them all up and divide by twenty; to do this as a summation, we could give the scores the names s1, s2,s3…s20; now the average could be written as , where the index variable now points to elements in a list.  In general, we can say the average of n test scores would be for any positive integer n, which again is much less writing than (s1+s2+…+sn)/n.

3. What is a factorial? (the symbol !)
For any positive integer n, n! = n×(n-1)×(n-2)×…×2×1, the product of the first n positive integers; n! is pronounced “n factorial”, though some people call it “n bang”. For example 5!=5×4×3×2×1=120 and 7!=7×6×5×4×3×2×1=5040.  0! = 1 by definition; the mathematical argument is that 0! should be defined as “the empty product” and “the empty product” multiplied by any other product p should be equal to p, so it acts like 1, hence the definition.  It also gets used in the denominator of fractions that define the entries of Pascal’s Triangle, so we can’t possibly let it be equal to 0.

Similarly, the capital Greek letter pi  is the symbol for product, just as we use capital sigma  for sum; using this notation    for any positive integer n.

4. What is a falling factorial, such as 64?
The idea of falling factorial is to start at some value x, which for our purposes can be any real (or even any complex) number and take the product  .  So for our example, 64 = 6×5×4×3 = 360.  Using this definition for n and j positive integers, nn+j = 0, since if we fall farther than n from n, 0 will enter the product and the product will be 0.  On the other hand,  2½3 = (2½ )(1½)(½) = 15/8 and  2½4 = (2½ )(1½)(½)(-½)  = -15/16, so falling past zero is not going to bring 0 into the product, so it will not vanish.  The same is true for a complex number with a non-zero imaginary part, such as i+1; (i+1)3 = (i+1)i(i-1) = i(i2-1) = -2i.

The symbology used here is from Concrete Mathematics and is by no means universally accepted; Stanley in Enumerative Combinatorics writes the same idea as (6)4.

Note:  The imaginary number i and the summation index i are not the same thing.  They are both in standard usage and it is unlikely that one will change any time soon.  To make matters worse, some writers use j and their standard summation index and electrical engineers use J as the square root of -1.  In computer science, this is called overloading of symbols; there is very little we can do about it.  Like in English where we have words spelled exactly the same, context will often make things clear.

5. What is a binomial coefficient?
A binomial (Latin for "two names") is an algebraic expression with two terms, like x+y, or 3x2z – 2siny; it means there is either one addition sign or one subtraction sign.  A coefficient is a constant that multiplies a term; in x+y the coefficients are 1 and 1, in 3x2z – 2siny the coefficients are 3 and –2, respectively.

The entries of Pascal’s Triangle are called binomial coefficients because if we expand the nth power of the binomial x+y, we get (x+y)n = 1xn + nxn-1y + ½(n2-n)xn-2y2 + … + ½(n2-n)x2yn-2  +  nxyn-1 + 1yn.

The polynomials in n in front of the x’s and y’s are the binomial coefficients; they are always non-negative integers.

6. What is a bitstring?
Consider an alphabet with only two symbols.  We will call the alphabet B = {0,1}; the symbols could be any two symbols, but 0 and 1 are the standard choice and these are the called binary digits or bits for short, a word first coined by the 20th Century American mathematician John Tukey, who is also given credit for coining the word software.  A list of bits in order is called a bitstring.  The set of all possible bitstrings of length n is denoted as Bn; for example, B3 = {000, 001, 010, 011, 100, 101, 110, 111}.  The number of elements in Bn is always 2n; the word in math for the number of elements in a set is the cardinality of a set, sometimes denoted as | Bn |.  You may be used to the straight line brackets as meaning absolute value of a number; this is another example of a math symbol overloaded with meanings, and the correct meaning has to be deciphered from the context in which it is used.

7. What is modular arithmetic, as in 5 (mod 7)?
When you first learn to divide, we would say “6 goes into 27 4 times with remainder 3” which is another way to say 27=6×4+3.  Then we start learning fractions and the remainder becomes the numerator of the mixed fraction 27/6= 43/6 before we reduce the fraction to lowest terms as 4½.  In some parts of higher math, we go back to taking remainders when dividing; in fact, we split up all the integers into separate sets (known as disjoint sets) based on what the remainder is when we divide by some integer n > 1.  This would be written as 27 3 (mod 6) or in some books it is written as 27 = 3 (mod 6).  When we write a b (mod c), this means that the positive number c divides (a-b), written as c|(a-b) or c = k(a-b) where k is an integer.  In our example above, 27 = 3 (mod 6) because 6|(27-3), which means 27-3 = 24 = 4×6.  By splitting all the integers into six disjoint sets, we can say that a (mod 6) represents an infinite set as follows.

0 (mod 6) = {…,-12, -6, 0, 6, 12, …}
1 (mod 6) = {…,-11, -5, 1, 7, 13, …}
2 (mod 6) = {…,-10, -4, 2, 8, 14, …}
3 (mod 6) = {…,-9, -3, 3, 9, 15, …}
4 (mod 6) = {…,-8, -2, 4, 10, 16, …}
5 (mod 6) = {…,-7, -1, 5, 11, 17, …}

While it is common to write k (mod n) with the number k in the interval 0 >= k >= n-1, sometimes in books they will talk about -1 (mod n); in our example, -1 (mod 6) would be the same set as 5 (mod 6); we just chose a different representative to be the official spokesnumber for the set.

8. What is calculus?
Okay, this is obviously a big question, and to give an answer in two paragraphs means we are giving the extreme shorthand version, but here goes.  We know that algebraic equations like y = x2 – 6x + 7 can be expressed as a graph on the xy-plane or as it is sometimes called, the Cartesian plane.  This was a huge revolution in math and science, because now algebraic equations could have geometric representation, and smart people could start asking the same questions they would ask about things in geometry, like “What is the area of this shape defined by our algebraic equation?” or “Can we draw a tangent line to this shape at a particular point, and if so, what is the algebraic equation that defines this line and especially its slope?”

To make a long story very, very short, the questions about area are answered by integral calculus, and the questions about the slopes of tangent lines are answered by differential calculus, methods where we create new equations, called the antiderivative and the derivative, that are matched up to the original equation to give us these answers to area and tangent, respectively.  Since there are libraries full of calculus books, you would be correct to assume there is a lot more to the story than this.

9. What is mathematical induction?
What separates math from every other human endeavor is the idea of proof; a proof is supposed to be a way to persuade people that something is true, but in math that persuasion has to follow very precise rules, and we should replace the word “persuade” with “convince”.  There are several methods of proof, and the one that causes beginning students the most trouble is mathematical induction, which is used to prove a statement that must be true for an infinite number of examples.

One way to think of mathematical induction is a template with only two tasks.

    Task 1:  Prove the first case.
    Task 2:  Prove that if we can assume case n is true, then that is enough to prove case n+1 is also true.  (Sometimes Task 2 needs to assume that cases 1, 2, … through n are true to prove case n+1.  This is called weak induction, while the first Task 2 definition is called strong induction.)

Notice that Task 2 uses n and n+1; it won’t do to say, “Case 99 is true, and we can use that to prove case 100.”  You can think of Task 2 in an induction proof as a kind of quality assurance test to knock down an infinite number of dominoes. Task 1 becomes “Knock down the first domino” and Task 2 becomes “Prove that at every step along the way, if we known some domino is knocked over, the next domino must also fall.”  Instead of testing every link one by one, we somehow find something all the links have in common, and use that fact to do the quality assurance.

10. What is a recursive definition?
A recursive definition of a sequence means that the (n+1)st element of the sequence can be found by performing some function that relies on the first n elements of the sequence.  We will see that the many of the interesting properties of Pascal’s Triangle rely on the fact that there are two different recursive definitions of the binomial coefficients, one involving adding two neighbors in row n together to get an element in row n+1, the other to take element k in row n and multiply by a certain fraction based on n and k to get the next neighboring element k+1 in row n.

11. What is an algorithm?
The simplest definition is that an algorithm is another word for method.  But in the 20th Century, there was a great push to make definitions more precise, and so now an algorithm is a method that follows a great many rules, some of which are as follows.
a. An algorithm has to solve a general problem.  (A recipe is not an algorithm.)
b. An algorithm has to give a correct solution for all legal inputs.  (Newton’s method for finding approximate roots of a function isn’t an algorithm, because for some initial values, you won’t get “the nearest root.”)
c. An algorithm has to come up with a solution in a finite number of steps.  (For some functions and some initial values, Newton’s method can end up in an infinite loop where the successive answers aren't getting any closer to a root.)
d. An algorithm has to come up with a correct solution.  (Again, Newton’s method comes up with an approximate answer, so it isn’t a “correct” solution unless we specify that we are willing to take an answer that comes within some reasonable neighborhood of the actual correct answer.)

The word algorithm is most often used in computer science, and any good algorithm will be a way to tell a computer to do a task.

12. What is a one-to-one correspondence?
Let’s say we have two sets, A and B.  Let’s also say that the definition of set A is very complicated, but the definition of set B is simpler, and we already know the number of elements (cardinality) of B.  If we can prove that we can match up every element in set B to a unique element in set A, and by doing this match-up, every element in set A has a corresponding element in set B, then we have a one-to-one correspondence between sets A and B, and we know that the two sets have the same cardinality.  Another word for one-to-one correspondence in math is a bijection; as you might guess, the prefix bi means “two”, and  the two things referred to are being “one-to-one” and “onto”.

13. What are the Fibonacci numbers?
Named for the Italian mathematician Leonardo of Pisa (nicknamed “Fibonacci”, which translated means “the handsome son” or “the fortunate son”), the Fibonacci numbers fn are a sequence that follows the recursive rule that fk=fk-1+fk-2, so we get the next Fibonacci number by adding together the two most recent Fibonacci numbers.

Mathematicians don’t always agree how to start the sequence; some say

f1 = 1, f2 = 2, f3 = 1+2 = 3, f4 = 3+2 = 5, etc.

while others prefer

f0 = 0, f1 = 1, f2 = 0+1 = 1, f3 = 1+1 = 2, etc.

On this website, we will use the second convention for two reasons.  One is Binet’s Formula, which can be written very nicely as    by using the second convention, so the n in the subscript is the same as the powers of n in the formula; the other is a cute little identity: g.c.d.(fa, fb) = fg.c.d(a,b) for all positive integers a and b.  (g.c.d. is short for Greatest Common Divisor).



14. What is a dot product?
A vector is a collection of numbers in a particular order; the cardinality of the collection is called the dimension of the vector; for instance (2, -1, 7) would be a 3-dimensional vector, which corresponds exactly to our idea of this being a point in 3-dimensional space.  If we have two vectors u = (u1,u2, …, un) and v = (v1, v2, …, vn) that have the same dimension (in this case, they are n-dimensional), then we can define the dot product  ; this means we multiply corresponding entries in the two vectors together, then add up all the products.  For example, (1, 2, 1).(6,4,1) = 1×6 + 2×4 + 1×1 = 6+8+1 = 15.

15. What is a difference triangle?
Consider a sequence S = s0, s1,s2, …; we can create a new sequence S* easily enough by taking the differences of consecutive entries in S, so s*0 = s1-s0, s*1 = s2-s1, etc.  You can think of this as being the sequence equivalent of take the derivative of a function to create a new function, and this same idea can be used to create S**, S***, etc.; this array of sequences is called a difference triangle.  As an example, let’s take the sequence Sn = n3, for non-negative integers n.

S    0   1   8  27  64  125  216 …
 S*     1   7  19  37  61   91 …
  S**     6  12  18  24  30 …
   S***     6   6   6   6 …
    S****     0   0   0 …

    It is not a coincidence that the 3rd difference sequence of this 3rd degree polynomial is the last non-zero sequence or that S*** is a constant sequence; recall from calculus that if f(x) = x3, f’’’(x) = 6 and f’’’’(x) = 0.  For our purposes, the numbers along the left side of the difference triangle are useful in an identity involving the binomial coefficients as follows:

    

    This dot product method of a row of Pascal’s Triangle with some sequence is the source of many identities; when an identity on our list can be proved using this method, we will have “difference triangle” listed under the hints.  Some of the difference triangles do not terminate with a row of all zeros; these can be seen in the power series and harmonic sum identities, as well as others.

16. Can we define “n choose k” for values of n and k that aren’t non-negative integers where n >= k?
Yes, we can if we use the idea of the falling factorial fractional representation; the upper index n can be replaced with any complex number z, but the lower index k will have to remain a non-negative integer.
If we use integers where n < k , since in the falling factorial if we fall farther than n from n, 0 will be part of the product.  So for example  ; using the symmetric rule,  in our example,  and so for any negative value of k, we will define  ; we don’t define the falling factorial rk for any values of k except non-negative integers, but it is perfectly okay to use rk when r is any real number, or even zk for any complex number z; note that when we do this, some of our simplest identities, including most importantly the symmetric identity, are no longer true.  For example, we can define  , but =0, because the lower index is no longer a positive integer.  Likewise    has meaning but  =0 both because the lower index is negative and not an integer.

Historical note:  The idea of extending the binomial coefficients to include negative numbers and non-integers in the upper index was first put forward by Isaac Newton in 1666, extending work done by John Wallis a decade earlier.  Wallis was a student of William Oughtred, whose 1631 book Clavis Mathematicae had the binomial coefficients written down in triangular form; Newton is also known to have owned a copy of this text.


Main







Applications
Identities





History
FAQ
Algorithms