In class we saw that the sum of the entries of row of Pascal's Triangle is . In this problem we investigate the sums of the squares of the entries of row of Pascal's Triangle.

(a) Compute the sums of the squares of Rows 1-4 of Pascal's Triangle. That is, compute:

Do these sums appear anywhere else in Pascal's Triangle?

(b) Guess at an identity based on your observations from part (a).

(c) Prove your identity using a committee-forming argument.

(d) Prove your identity using a block-walking argument.

SaltyGrandma
Oct 15, 2018

#1**+2 **

(a) The sum of the squares in row 1 of Pascal's Triangle is \(1^2+1^2=1+1=2\)

The sum of the squares in row 2 of Pascal's Triangle is \(1^2+2^2+1^2=1+4+1=6\)

The sum of the squares in row 3 of Pascal's Triangle is \(1^2+3^2+3^2+1^2=1+9+9+1=20\)

The sum of the squares in row 4 of Pascal's Triangle is \(1^2+4^2+6^2+4^2+1^2=1+16+36+16+1=70\)

These numbers appear in Pascal's triangle. The sum of the squares in row n is the same as the middle term in row 2n. For example, 2 is the sum of the squares in row 1 and is also the middle term in row 2. In addition, 70 is the sum of the squares in row 4 and is also the middle term in row 8.

(b) I think that \(\binom{n}{0}^2 + \binom{n}{1}^2 + \cdots + \binom{n}{n}^2 = \binom{2n}{n}\). As seen in problem (a) the sum of the squares in row 1 of Pascal's Triangle is \($\binom10^2+\binom11^2=1^2+1^2=1+1=2$\), and 2 is \(\binom{2}{1}\). In another instance, the sum of the squares in row 3 of Pascal's Triangle is \(\binom{3}{0}^2 + \binom{3}{1}^2 + \binom{3}{2}^2 + \binom{3}{3}^2=1^2+3^2+3^2+1^2=1+9+9+1=20\), and 20 is also \(\binom{6}{3}\). The sum of the squares in row 2 of Pascal's Triangle is \(1^2+2^2+1^2=1+4+1=6\), and 6 is \(\binom{4}{2}\); and the sum of the squares in row 4 of Pascal's Triangle is \(1^2+4^2+6^2+4^2+1^2=1+16+36+16+1=70\), and 70 is also \(\binom84\).

Another way to look at it is to look back at problem (a). As seen in this problem, the sum of the squares in row n is the same as the middle term in row 2n. The middle term in row 2n is the nth term, which is \(\binom{2n}{n}\)

(c) Let's say we have to choose n people to be on a commitee from a group of 2n people. This is \(\binom{2n}{n}\) of course. But we can also think about this in a different way. We can take the group of 2n people and split it into two groups of n each. Then, we can choose one person from one group and n-1 from the other. There are \(\binom{n}{1}\cdot \binom{n}{n-1}\) ways to do this, but since \(\binom{n}{n-1} = \binom{n}{1}\), we can simplify this to \(\binom{n}{1}^2\). We can choose any number of people from one group and that number subtracted from n in the other. So we get \(\binom{n}{1}^2+\binom{n}{2}^2+\cdots+\binom{n}{n}^2\) ways to choose n people to be on a commitee from a group of 2n people. But since we already finished this another way, we can equate our two answers to get \(\binom{n}{1}^2+\binom{n}{2}^2+\cdots+\binom{n}{n}^2=\binom{2n}{n}\)

(d) We can also prove this identity using a block-walking argument. We need to find how many ways there are to go from the top number to the nth term on row 2n through the 1st term on row n. In class, we showed that there are \(\binom{n}{1}\) ways to go from the top number to the 1st term on row n. Now, we can define the 1st term on row n to be the top point. That would make the nth term on row 2n to be the (n-1)th term on row n. So there are \(\binom{n}{n-1} = \binom{n}{1}\) ways to go from the 1st term on row n to the nth term on row 2n. Since the way we choose to go to the 1st term on row n does not influence how we go to the nth term on row 2n, we can multiply the two quantities to get\( \binom{n}{1}^2\) ways to go from the top number to the nth term on row 2n through the 1st term on row n. This holds for any term on row n we need to go through to get to the nth term on row 2n. For example, the number of ways to go from the top number to the nth term on row 2n through the 4th term on row n is \(\binom{n}{4}^2\). But, without any restrictions, we can go to the nth term on row 2n \(\binom{2n}{n}\) ways. Since going to the nth term on row 2n requires going through row n, we can say that \(\binom{n}{1}^2+\binom{n}{2}^2+\cdots+\binom{n}{n}^2=\binom{2n}{n}\)

SaltyGrandma
Oct 15, 2018

#2**+1 **

I know that this question has already been posted, but there was no answer to (c) and (d) and there was an inadequate answer to (b).

SaltyGrandma
Oct 15, 2018