SaltyGrandma

avatar
UsernameSaltyGrandma
Score83
Membership
Stats
Questions 13
Answers 8

 #1
avatar+83 
+3

(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}\)

.
Oct 14, 2018