Combinatorial sum II

Algebra Level 2

The sum ( n 0 ) 2 + ( n 1 ) 2 + ( n 2 ) 2 + + ( n n ) 2 \left( \begin{array}{c} n\\ 0\\ \end{array} \right)^2 + \left( \begin{array}{c} n\\ 1\\ \end{array} \right)^2 + \left( \begin{array}{c} n\\ 2\\ \end{array} \right)^2 +\cdots + \left( \begin{array}{c} n\\ n\\ \end{array} \right)^2 can be written as the combinatorial number ( a b ) \left( \begin{array}{c} a\\ b\\ \end{array} \right) . Find a b \dfrac{a}{b} .


The answer is 2.

This section requires Javascript.
You are seeing this because something didn't load right. We suggest you, (a) try refreshing the page, (b) enabling javascript if it is disabled on your browser and, finally, (c) loading the non-javascript version of this page . We're sorry about the hassle.

2 solutions

Raymond Chan
Sep 3, 2018

This is a very standard proof exercise through binomial expansion. Consider ( 1 + x ) 2 n = ( 1 + x ) n ( 1 + x ) n (1+x)^{2n}=(1+x)^n(1+x)^n k = 0 2 n ( 2 n k ) x k = [ ( n 0 ) + ( n 1 ) x + . . . + ( n n ) x n ] [ ( n 0 ) + ( n 1 ) x + . . . + ( n n ) x n ] \sum_{k=0}^{2n}\dbinom{2n}{k}x^k=[\dbinom{n}{0}+\dbinom{n}{1}x+...+\dbinom{n}{n}x^n][\dbinom{n}{0}+\dbinom{n}{1}x+...+\dbinom{n}{n}x^n]

Consider the coefficient of x n x^n on both sides, we have ( 2 n n ) = ( n 0 ) ( n n ) + ( n 1 ) ( n n 1 ) + . . . + ( n n ) ( n 0 ) \dbinom{2n}{n}=\dbinom{n}{0}\dbinom{n}{n}+\dbinom{n}{1}\dbinom{n}{n-1}+...+\dbinom{n}{n}\dbinom{n}{0}

Since ( n r ) = ( n n r ) 0 r n \dbinom{n}{r}=\dbinom{n}{n-r} \,\forall\, 0\le r \le n , we have ( n 0 ) 2 + ( n 1 ) 2 + . . . + ( n n ) 2 = ( 2 n n ) \dbinom{n}{0}^2+\dbinom{n}{1}^2+...+\dbinom{n}{n}^2=\dbinom{2n}{n}

Therefore a = 2 n a=2n , b = n b=n , and a b = 2 n n = 2 \frac{a}{b}=\frac{2n}{n}=\boxed{2}

Gonzalo Píngaro
Sep 3, 2018

Notice that ( n k ) = ( n n k ) \left( \begin{array}{c} n\\ k\\ \end{array} \right) = \left( \begin{array}{c} n\\ n-k\\ \end{array} \right) . So ( n k ) 2 = ( n k ) ( n n k ) \left( \begin{array}{c} n\\ k\\ \end{array} \right)^2 = \left( \begin{array}{c} n\\ k\\ \end{array} \right) \cdot \left( \begin{array}{c} n\\ n-k\\ \end{array} \right) . The sum of all those terms gives the number of way or extract n n balls of a set of 2 n 2n balls separated in two subsets of n n balls each.

0 pending reports

×

Problem Loading...

Note Loading...

Set Loading...