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 wefirst 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,thenth of which, denoted by tn,isdefinedasthesumofthefirstncounting numbers. Its value, in terms of n, can be found by the following trick. We write tn as the sum just mentioned and then again as the same sum but in the reverse order. Adding the two versions of tn together:
tn=1+2+3+···+(n-2)+(n-1)+n
tn=n+(n-1)+(n-2)+···+3+2+1;
Forexample,bytakinga=1andb=2, we see that the sum of the first nodd numbers is n+n(n-1)=n+n2-n=n2,thenth 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 asthefirsttermand move from one term to the next by multiplying by afixed number,called the common ratio, denoted by the symbol r.Thatistosay,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 thefirst 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=1andr=2 gives us the sum of powers of 2: