Pascal’s identity

pascal triangleTheorem. (Pascal’s Identity) Let n and k be positive integers. Then, 

{n \choose k} = {{n-1}\choose k}+{{n-1} \choose {k-1}}.

Proof.

Let X be an n-set and fix an element x of X, and let Y denote the set X-{x}. For any k-combination (i.e., a k-subset) A of X, either x is in A or x is not in A. In the first case, if B is the set A-{x}, then B is a {k-1} -subset of Y and hence, can be chosen in {n-1} \choose {k-1} ways, while in the second case, A is itself a k-subset of Y and hence, can be chosen in {n-1} \choose k ways. The proof is complete by invoking the addition principle. QED.

It is also easy to see that Pascal’s identity follows from the binomial theorem. (if we have proved the latter without using the former as ,we did). Pascal’s identity gives rise to the famous Pascal’s triangle, initial portion of which is drawn below. Each entry is obtained from the two entries directly above it as given in Pascal’s identity. This obtains all the binomial coefficients where n runs from 1 to 6 and the horizontal lines correspond to a fixed value of n. Note that Pascal triangle is an infinite triangle, only a finite portion of this triangle (from 1 to 6) is shown in the figure below/attached. A more familiar form of the binomial theorem is as follows:

(1+x)^{n}=\sum_{k=0}^{n}{n \choose k}x^{k}

which is obtained by letting y=1 in the binomial theorem. By making the substitution x=1 in the above expression, we obtain:

\sum_{k=0}^{n}{n \choose k}=2^{n}

Stated in other words, the above identity tells us that a set of order n has 2^{n} subsets in all. Again, the susbstitution x=-1 yields

\sum_{k} {n \choose {2k}}=\sum_{k}{n \choose {2k+1}}.

Thus, in any set the number of subsets of odd order is the same as the number of subsets of even order.

A large number of identities involving binomial coefficients are actually proved either using a combinatorial identity or a known polynomial expression such as the binomial theorem and manipulating it. For example, to prove that

{n \choose 1}-2{n \choose 2}+3{n \choose 3}- \ldots +(-1)^{n-1}n {n \choose k}=0,

we observe that each summand on the left hand side (ignoring the sign) has the form :

k {n \choose k}= n {{n-1}\choose {k-1}}.

Hence, the LHS reduces to the alternating sum

n \times \sum_{i=0}^{n-1}(-1)^{i}{{n-1} \choose i}=0

using the binomial theorem. Sim1ilarly, to find n \sum \frac {1}{k+1}{n \choose k}, we take the familiar form of the binomial theorem and integrate both sides (as polynomials in x) w.r.t. x from 0 to 1.

More later…

Nalin Pithwa

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

%d bloggers like this: