Square of Integer: Showing Integer's Square

[anemone]

Show that $\displaystyle \sum_{k=0}^{2013} \dfrac{4026!}{(k!(2013-k)!)^2}$ is the square of an integer.

 

[Opalg]

[sp]Expand $(1+x)^{2n} = (1+x)^n(1+x)^n$ binomially: $$\sum_{i=0}^{2n}{2n\choose i}x^i = \sum_{j=0}^n{n\choose j}x^j\sum_{k=0}^n{n\choose k}x^k.$$ Compare coefficients of $x^n$ on both sides: $${2n\choose n} = \sum_{k=0}^n{n\choose k}{n\choose n-k} = \sum_{k=0}^n\frac{(n!)^2}{\bigl(k!(n-k)!\bigr)^2}.$$ Now multiply both sides by $${2n\choose n} = \frac{(2n)!}{(n!)^2}$$ to get $${2n\choose n}^2 = \sum_{k=0}^n \frac{(2n)!}{\bigl(k!(n-k)!\bigr)^2}.$$ Then put $n=2013$ to get $$\sum_{k=0}^{2013} \dfrac{4026!}{(k!(2013-k)!)^2} = {4026\choose 2013}^2.$$[/sp]

 

[anemone]

Awesome, Opalg...and thanks for participating! :)

A method that is different than you and is also the proof by other:

Spoiler

We prove the more general statement:

$\displaystyle \sum_{k=0}^{n} \dfrac{(2n)!}{(k!(n-k)!)^2}={2n \choose n}^2$---(1)

Note that we have

$\displaystyle\dfrac{(2n)!}{(k!(n-k)!)^2}=\dfrac{(n)!}{(k!(n-k)!)^2}\cdot \dfrac{(2n)!}{(n!)^2}={n \choose k}^2\cdot{2n \choose n}$

Hence it suffices t show that

$\displaystyle \sum_{k=0}^{n} {n \choose k}^2={2n \choose n}$

We will do this combinatorially. Consider $2n$ balls, numbered from 1 up to $2n$. Balls 1 up to $n$ are colored green, and balls $n+1$ up to $2n$ are colored yellow. We can choose $n$ balls from these $2n$ balls in $\displaystyle {2n \choose n}$ ways.

On the other hand, we can also first choose $k$ green balls, with $0 \le k \le n$, and then choose $n-k$ yellow balls. Equivalently, we can chose $k$ green balls to include and $k$ yellow balls to not include. Hence the number of ways in which one can choose $n$ balls is also equal to $\displaystyle \sum_{k=0}^n {n \choose k}^2$.

Hence this sum is equal to ${2n \choose k}$. This proves (1) and we are done.