Htykuut

I was hoping to find a more "mathematical" proof, instead of proving logically $displaystyle sum_{k = 0}^n {n choose k}^2= {2n choose n}$.

I already know the logical Proof:

$${n choose k}^2 = {n choose k}{ n choose n-k}$$

Hence summation can be expressed as:

$$binom{n}{0}binom{n}{n} + binom{n}{1}binom{n}{n-1} + cdots + binom{n}{n}binom{n}{0}$$

One can think of it as choosing $n$ people from a group of $2n$
(imagine dividing a group of $2n$ into $2$ groups of $n$ people each. I can get $k$ people from group $1$ and another $n-k$ people from group $2$. We do this from $k = 0$ to $n$.

The combinatorial explanation is straightforward. There's also a roundabout approach through what are called "generating functions." The binomial theorem tells us that

$$(1+x)^n(x+1)^n=left(sum_{a=0}^nbinom{n}{a}x^aright)left(sum_{b=0}^nbinom{n}{b}x^{n-b}right)=sum_{c=0}^{2n}left(sum_{a+n-b=c}binom{n}{a}binom{n}{b}right)x^c$$

The $x^n$ coefficient of the above occurs with $c=n$, wherein the coefficient is

$$sum_{a+n-b=n}binom{n}{a}binom{n}{b}=sum_{a=0}^nbinom{n}{a}^2.$$

However, the $x^n$ coefficient of $(1+x)^n(x+1)^n=(1+x)^{2n}$, again by the binomial theorem, is

$$binom{2n}{n}. $$

Equating the two gives the result.

Since $dbinom n k= dbinom n {n-k}$, the identity
$$
sum_{k=0}^n binom n k ^2 = binom {2n} n
$$
is the same as
$$
sum_{k=0}^n binom n k binom n {n-k} = binom {2n} n.
$$
So say a committee consists of $n$ Democrats and $n$ Republicans, and one will choose a subcommittee of $n$ members. One may choose $k$ Democrats and $n-k$ Republicans in $dbinom n k cdot dbinom n {n-k}$ ways. The number of Democrats is in the set ${0,1,2,ldots,n}$, thus ranging from all Republicans to all Democrats. The sum then gives the total number of ways to choose $n$ out of $2n$.

Consider the graph underlying Pascal's triangle:

In this graph, the number at each node is a binomial coefficient and can also be thought of as the number of downward paths from the apex to that node.

The left side of the identity is the number of paths that start at the apex, go down to the $n$th row and return to the apex (let's call them round trips to $n$). By reflecting the return path about the $n$th row, we get a bijective correspondence between return trips to $n$ and paths from the apex to the central node of the $2n$th row. This is nothing but the central binomial coefficient $binom{2n}n$.

$newcommand{angles}[1]{leftlangle, #1 ,rightrangle}
newcommand{braces}[1]{leftlbrace, #1 ,rightrbrace}
newcommand{bracks}[1]{leftlbrack, #1 ,rightrbrack}
newcommand{ceil}[1]{,leftlceil, #1 ,rightrceil,}
newcommand{dd}{{rm d}}
newcommand{ds}[1]{displaystyle{#1}}
newcommand{expo}[1]{,{rm e}^{#1},}
newcommand{fermi}{,{rm f}}
newcommand{floor}[1]{,leftlfloor #1 rightrfloor,}
newcommand{half}{{1 over 2}}
newcommand{ic}{{rm i}}
newcommand{iff}{Longleftrightarrow}
newcommand{imp}{Longrightarrow}
newcommand{pars}[1]{left(, #1 ,right)}
newcommand{partiald}[3]{frac{partial^{#1} #2}{partial #3^{#1}}}
newcommand{pp}{{cal P}}
newcommand{root}[2]{,sqrt[#1]{vphantom{large A},#2,},}
newcommand{sech}{,{rm sech}}
newcommand{sgn}{,{rm sgn}}
newcommand{totald}[3]{frac{{rm d}^{#1} #2}{{rm d} #3^{#1}}}
newcommand{ul}[1]{underline{#1}}
newcommand{verts}[1]{leftvert, #1 ,rightvert}$
begin{align}
color{#66f}{largesum_{k = 0}^{n}{n choose k}^{2}}&=
sum_{k = 0}^{n}{n choose k}
oint_{verts{z} = 1}{pars{1 + z}^{n} over z^{k + 1}},{dd z over 2piic}
=oint_{verts{z} = 1}{pars{1 + z}^{n} over z}
sum_{k = 0}^{n}{n choose k}pars{1 over z}^{k},{dd z over 2piic}
\[5mm]&=oint_{verts{z} = 1}{pars{1 + z}^{n} over z}
pars{1 + {1 over z}}^{n},{dd z over 2piic}
=oint_{verts{z} = 1}{pars{1 + z}^{2n} over z^{n + 1}},{dd z over 2piic}
=color{#66f}{large{2n choose n}}
end{align}

Okey this one is easy(if you seen this one once)
We have to show:
$${n choose 0}^2+{n choose 1}^2+cdots+{n choose n}^2={2n choose n} $$
Define a set A, $$A={a_1,ldots,a_n,a_{n+1},ldots,a_{2n}}$$ consisting of $2n$ - Elements. Now we declare $V$, is a set of $n$-sets of $A$. Obviously the cardinality of $V,$ $$|V|={2n choose n}.$$ Since one can choose $n$ Elements from $2n$ Elements in $${2n choose n}$$ ways.

Okey now we have the right side.
The for the left side you have give a disjunctive partition of the $V$ set. This should be done in the following way:
$V_i$ has exactly $i$-Elements from ${a_1,ldots,a_n}$, then the cardinality
$|V_i|={n choose i}{n choose n-i}={n choose i}{n choose i}={n choose i}^2$. Then with the Rule of Sum we have the left side. And we are done.
The Tricky Part ist to create the Partition to use the rule of sum.

Imagine that we are distributing $n$ indistinguishable candies to $k$ distinguishable children. By a direct application of Balls and Urns, there are $${n+k-1choose k-1}$$ ways to do this. Alternatively, we can first give $0le ile n$ candies to the oldest child so that we are essentially giving $n-i$ candies to $k-1$ kids and again, with Balls and Urns, $${n+k-1choose k-1}=sum_{i=0}^n{n+k-2-ichoose k-2}$$, which simplifies to the desired result.