Numbers that arise of their own accord in counting problems are important and so have been extensively investigated. Here I will describe the binomial coefficients, and the numbers of Catalan,Fibonacci, and Stirling because they enumerate certain natural collections. But we first begin with some very fundamental number sequences.
Triangular numbers, arithmetic and geometric progressions
Since they will reappear when we look at binomial coefficients,I will take a moment to revisit the triangular numbers, the nth of which, denoted by tn, is defined as the sum of the first n counting numbers. Its value, in terms ofn, can be found by the following trick. We write tn as the sumjust mentioned and then again as the same sum but in the reverse order. Adding the two versions of tntogether:
tn=1+2+3+…+(n-2)+(n-1)+n
tn=n+(n-1)+(n-2)+…+3+2+1;
For example, by taking a=1 and b=2, we see that the sum of the first nodd numbers is n+n(n-1)=n+n2-n=n2, the nth square.
If we replace addition by multiplication as the operation, we move from arithmetic series to geometric series. In an arithmetic series,each pair of successive terms is separated by a common difference,the number b in our notation. In other words, to move from one term to the next, we simply add b. In a geometric series, we once again begin with some arbitrary number, a as the first term and move from one term to the next by multiplyingby afixed number,called the common ratio, denoted by the symbolr. That is to say,the typical geometric series has the form a, ar, ar2,…with the nth term being arn-1. As with arithmetic series, there is a formula for the sum of the first nterms of a geometric series:
The quick way of seeing that this formula is right is to take the equivalent form that we obtain when we multiply both sides of this equation by(r-1)and multiply out the brackets. On the left-hand side we obtain:
(ar+ar2+ar3+…+arn)-(a+ar+ar2+…+arn-1)
and the whole expression telescopes, meaning that nearly every term is cancelled by one in the other bracket:the only exceptions are arn-a=a(rn-1), showing that our formula for the sum is correct. For example, putting a=1 and r=2 gives us the sum of powers of 2: