Skip to page content Home     Posts     CV     Contact     People

Pascal's Triangle

2017 May 6

Whew! I need a break from iterated functions.

Prove that the sum of the entries of the nth row of Pascal's Triangle is $2^n$. Prove that the alternating sum of the entries of the nth row of Pascal's Triangle is $0$. Find a formula for $$\sum_{n_{k-1}=1}^{n_k} \sum_{n_{k-2}=1}^{n_{k-1}} ... \sum_{n_0=1}^{n_1} 1$$

The mathematical phenomenon known as "Pascal's Triangle" recently caught my eye. Pascal's Triangle is a triangular arrangement of numbers stretching on to infinity with each row of numbers containing one number more than the previous row. Furthermore, each number is the sum of the two numbers above it, with the topmost number a one. Here are the first $7$ rows of pascal's triangle:

This mathematical entity has some interesting properties. For example, if we denote the combinations formula for "n choose r" by $$_nC_r=\frac{n!}{r!(n-r)!}$$

and we call the topmost row of Pascal's triangle row 0 and the first entry in each row the 0th entry in that row, then the rth item in the nth row is given by $_nC_r$. This can be proven easily, because since each entry in the triangle is the sum of the entries above it, and since $_0C_0$ is trivially $1$, also the topmost entry of the pyramid, we need only prove that this summing property holds for $_nC_r$, or that $$_nC_r=_{n-1}C_{r-1}+_{n-1}C_r$$

Here is a quick algebraic proof of that identity. We start with the expression $$_{n-1}C_{r-1}+_{n-1}C_r$$ and expand it out using our formula: $$\frac{(n-1)!}{(r-1)!(n-r)!}+\frac{(n-1)!}{r!(n-r-1)!}$$ $$\frac{(n-1)!r}{r!(n-r)!}+\frac{(n-1)!(n-r)}{r!(n-r)!}$$ $$\frac{(n-1)!r+(n-1)!(n-r)}{r!(n-r)!}$$ $$\frac{(n-1)!(r+n-r)}{r!(n-r)!}$$ $$\frac{(n-1)!n}{r!(n-r)!}$$ $$\frac{n!)}{r!(n-r)!}$$

We can now see that this is clearly equal to $_nC_r$. This can be useful in proving some conjectures about patterns found in Pascal's triangle. For example, observe what happens when one alternates addition and subtraction for each entry in some row (other than the 0th row): $$1-1=0$$ $$1-2+1=0$$ $$1-3+3-1=0$$ $$1-4+6-4+1=0$$

We can obviously conjecture that this will always be $0$, but how can we prove it? Well, we can do so using what we now know about the connection between Pascal's Triangle and the combinations formula. Such an alternation of addition and subtraction will take the form $$_nC_0-_nC_1+_nC_2-...+_nC_{n-1}(-1)^{n-1}+_nC_n(-1)^n$$

Using our identity $nC_r={n-1}C_{r-1}+_{n-1}C_r$, we can expand this out to get $$_nC_0-(_{n-1}C_1+_{n-1}C_0)+(_{n-1}C_2+_{n-1}C_1)-...+(_{n-1}C_{n-1}+_{n-1}C_{n-2})(-1)^{n-1}+_nC_n(-1)^n$$

and we can rearrange this to get $$_nC_0-_{n-1}C_0+_{n-1}C_1-_{n-1}C_1+_{n-1}C_2-_{n-1}C_2+...+_{n-1}C_{n-2}-_{n-1}C_{n-2}+_{n-1}C_{n-1}(-1)^{n-1}+_nC_n(-1)^n$$

This is, of course, a telescoping sum, and we are left only with $$_nC_0-_{n-1}C_0+_{n-1}C_{n-1}(-1)^{n-1}+_nC_n(-1)^n$$

Of cource, any $_kC_k$ or $_kC_0$ is equal to $1$, so we now have $$1-1+(-1)^{n-1}+(-1)^n$$ $$(-1)^{n-1}+(-1)^n$$

Those two terms will be of opposite signs, and we get $0$ as a final result, proving our conjecture.

Now notice what happens when you sum the entries of each row: $$1+1=2$$ $$1+2+1=4$$ $$1+3+3+1=8$$ $$1+4+6+4+1=16$$

We can make yet another conjecture: that the sum of the entries of the nth row is equal to $2^n$. We can prove this using a similar technique, but first we must modify our identity a little bit. Right now we know that $$_nC_r=_{n-1}C_{r-1}+_{n-1}C_r$$

and so $$_{n+1}C_r=_nC_{r-1}+_nC_r$$

Simply by subtracting, we get that $$_nC_r=_{n+1}C_r-_nC_{r-1}$$

This identity will prove useful in this proof. Let us denote the sum of the entries of the nth row by $S(n)$. Then $$S(n)=_nC_0+_nC_1+...+_nC_n$$

By substitution from our identitu, we get $$S(n)=(_{n+1}C_0-0)+(_{n+1}C_1-_nC_0)+...+(_{n+1}C_n-_nC_{n-1})$$

We can rearrange this to get $$S(n)=(_{n+1}C_0+_{n+1}C_1+...+_{n+1}C_n)-(_nC_0+_nC_1+...+_nC_{n-1})$$ or $$S(n)=(_{n+1}C_0+_{n+1}C_1+...+_{n+1}C_n+_{n+1}C_{n+1}-1)-(_nC_0+_nC_1+...+_nC_{n-1}+_nC_n-1)$$

This is where the trick comes in. Notice that the sum $$_nC_0+_nC_1+...+_nC_{n-1}+_nC_n$$

Is the same as $S(n)$, and the sum $$_{n+1}C_0+_{n+1}C_1+...+_{n+1}C_n+_{n+1}C_{n+1}$$

Is the same as $S(n+1)$, so we have now that $$S(n)=(S(n+1)-1)-(S(n)-1)$$

and this crunches down to $$S(n)=S(n+1)-S(n)$$ $$S(n+1)=2S(n)$$

Great! Now we've defined the sum in terms of itself recursively, and since $S(0)=1$, we can say that $S(n)=2^n$, since the sum of each row is twice the sum of the previous row.

Alright, there's one more interesting problem to do, and it doesn't at first seem like it will have anything to do with the combinations operator. The problem comes from @Ryan on Math StackExchange. The problem is to find a general formula for the iterated summation $$Z^k(n_k)=\sum_{n_{k-1}=1}^{n_k} \sum_{n_{k-2}=1}^{n_{k-1}} ... \sum_{n_0=1}^{n_1} 1$$

For this problem, it isn't hard to make a conjecture. Here are the first couple iterates: $$Z^0(n_0)=1$$ $$Z^1(n_1)=n$$ $$Z^2(n_2)=\frac{n_2(n_2+1)}{2}$$ $$Z^3(n_3)=\frac{n_3(n_3+1)(n_3+2)}{6}$$ $$Z^4(n_4)=\frac{n_4(n_4+1)(n_4+2)(n_4+3)}{24}$$

It is easy to see just by observing the pattern that $$Z^k(n_k)=\frac{1}{k!}\prod_{i=0}^{k-1} (n_k+i)$$

Here is the proof that I posted on Math Stackexchange:

I have already shown that the conjecture holds for the first two, so that part is out of the way. Our conjecture is that

$$\sum_{n_{k-1}=1}^{n_k} \sum_{n_{k-2}=1}^{n_{k-1}} ... \sum_{n_0=1}^{n_1} 1=\frac{1}{k!}\prod_{i=0}^{k-1} (n_k+i)$$

Assume that this statement is true for some $n_k$. Then we must prove that its truth for some $n_k$ implies its truth for $n_{k+1}$, or that if the above is true, then

$$\sum_{n_k=1}^{n_{k+1}} \sum_{n_{k-1}=1}^{n_k} ... \sum_{n_0=1}^{n_1} 1=\frac{1}{(k+1)!}\prod_{i=0}^{k} (n_{k+1}+i)$$

Must also be true. This may at first seem like a scary problem to attack until we remember that we assumed that

$$\sum_{n_{k-1}=1}^{n_k} \sum_{n_{k-2}=1}^{n_{k-1}} ... \sum_{n_0=1}^{n_1} 1=\frac{1}{k!}\prod_{i=0}^{k-1} (n_k+i)$$

was true, allowing us to substitute and instead have the task of proving

$$\sum_{n_k=1}^{n_{k+1}} \frac{1}{k!}\prod_{i=0}^{k-1} (n_k+i)=\frac{1}{(k+1)!}\prod_{i=0}^{k} (n_{k+1}+i)$$

Which is less intimidating. First one must notice that the quantity

$$\prod_{i=0}^{k-1} (n_k+i)$$

is equal to

$$\frac{(n_k+k-1)!}{(n_k-1)!}$$

and we can substitute this into our equation to get

$$\sum_{n_k=1}^{n_{k+1}} \frac{1}{k!}\frac{(n_k+k-1)!}{(n_k-1)!}=\frac{1}{(k+1)!}\frac{(n_{k+1}+k)!}{(n_{k+1}-1)!}$$

We can now notice that

$$\frac{1}{k!}\frac{(n_k+k-1)!}{(n_k-1)!}$$

is the same as

$$_{n_k+k-1}C_{n_k-1}$$

and so now we have

$$\sum_{n_k=1}^{n_{k+1}} {_{n_k+k-1}C_{n_k-1}}=\frac{1}{(k+1)!}\frac{(n_{k+1}+k)!}{(n_{k+1}-1)!}$$

Now we can attack the sum

$$\sum_{n_k=1}^{n_{k+1}} {_{n_k+k-1}C_{n_k-1}}$$

Which expands out to form

$$_kC_0+_{k+1}C_1+_{k+2}C_2+...+_{n_{k+1}+k-1}C_{n_{k+1}-1}$$

Now we can use the identity of the combinations formula

$$_nC_r=_{n+1}C_r-_nC_{r-1}$$

to expand out our infinite sum:

$$_kC_0+(_{k+2}C_1-_{k+1}C_0)+(_{k+3}C_2-_{k+2}C_3)+...+(_{n_{k+1}+k}C_{n_{k+1}-1}-_{n_{k+1}+k-1}C_{n_{k+1}-2})$$

We can see now that this is a telescoping sum that condenses down to

$$_kC_0-_{k+1}C_0+_{n_{k+1}+k}C_{n_{k+1}-1}$$ $$=1-1+_{n_{k+1}+k}C_{n_{k+1}-1}$$ $$=_{n_{k+1}+k}C_{n_{k+1}-1}$$

When we substitute this into our equation, we get this:

$$_{n_{k+1}+k}C_{n_{k+1}-1}=\frac{1}{(k+1)!}\frac{(n_{k+1}+k)!}{(n_{k+1}-1)!}$$ $$\frac{(n_{k+1}+k)!}{(k+1)!(n_{k+1}-1)!}=\frac{(n_{k+1}+k)!}{(k+1)!(n_{k+1}-1)!}$$

Which is a truth statement. This proves that if our statement is true for some $k$, then is must be true for $k+1$, and since it is true for $k=1$, it is true for all natural numbers $k$. QED.

That was sure a pain to type up.

Anyways, the combination formula's interesting identity seems useful in turning normally difficult summations into telescoping sums.