In Which Our Hero (You) Discovers Several Methods of Proving a Combinatorial Identity Involving Pascal’s Triangle
(Read Challenge #9 first if you haven’t already…)
As described by tang and Jonathan, respectively:
- Because of the way Pascal’s triangle is defined, each entry “contributes” to the entries below, and below to the right. Since each entry contributes to two other entries, it follows that the sum of all the entries in each row will always be twice the sum of the entries in the previous row. The sum of the entries in the first row is obviously 1, so the subsequent row sums will be 2, 4, 8, 16… powers of two.
- Since the binomial coefficient
tells us the number of ways to pick exactly k things out of n, the sum of all the binomial coefficients from
to
tells us the total number of ways to pick any number of things out of n. That is, someone shows you n things, and says you can take as many or as few as you want (including all, or none). How many choices do you have? You have two choices for each individual item: you can either take it, or not. So the total number of choices is
.
Next time I’ll talk more about the enigmatic method of proof suggested by Anonymous*: “Simply expand (1+1)^n, and you’ve got it.” This refers to the Binomial Theorem, an important generalization of what we’ve been talking about — so important, in fact, that it’s where binomial coefficients get their name. Fortunately for us, it’s also totally sweet.
(*Name changed to protect identity)
The Math Less Traveled 
I appreciate the thought, but you needn’t have worried. Pseudonym isn’t my real name.
The first proof method presented can also be used to prove my second identity, that for n>0:
The details are left as an exercise. (Note that if you assume the binomial theorem, just expand
.)
Hehe, I know, it was a joke. =)
By the way, did you know LaTeX includes a \binom command to typeset binomial coefficients? So you can type \binom{n}{k} instead of doing all that stuff with arrays. Actually, it may be in one of the AMS packages, I’m not sure, but if so they get included by default on this blog.
If, in preparing a binomial expansion, you were to arbitrarily decide not to commute multiplication…. Then, for example,
(x+y)^4
= (x+y)(x+y)(x+y)(x+y)
= xxxx + xxxy + xxyx + xxyy + xyxx + xyxy + xyyx + xyyy + yxxx + yxxy + yxyx + yxyy + yyxx + yyxy + yyyx + yyyy
Once again, we can consider these the rearrangments of xxxx, xxxy, xxyy, xyyy and yyyy, iow 4!/(4!0!) + 4!/(3!1!) + 4!/(2!2!) + 4!/(1!3!) + 4!/(0!4!)
or as (x or y)*(x or y)*(x or y)*(x or y) = 2^4
So can anyone help me? I need to know how you can prove that the fibonacci number or Square numbers, or any of the identities for the Pascal Triangle actually works. As in i need to know proofs prooving why the fibonacci number exist in the triangle, i need to state WHY these properties work and exist. Thank you!