\section*{Problem 6B - 151246B}

In mathematical statistics, sums of the following form are often needed:

\[
M=\sum_{k=0}^{n}\binom{2 n-1}{2 k} ; \quad N=\sum_{k=0}^{n}\binom{2 n}{2 k} ; \quad m=\frac{1}{N} \sum_{k=0}^{n}\binom{2 n}{2 k}
\]

where \(n\) is a natural number with \(n \geq 1\).

a) Calculate the sums \(M, N\) and \(m\).

b) Let \(f\) be the function defined for all real \(x\) by

\[
f(x)=\frac{1}{N} \sum_{k=0}^{n}(k-x)^{2}\binom{2 n}{2 k}
\]

Calculate \(f(x)\) and show that \(f\) has a minimum value and that this value is attained exactly for \(x=m\).
}

a) 1. It holds that:

\[
M=\binom{2 n-1}{0}+\binom{2 n-1}{2}+\ldots+\binom{2 n-1}{2 n-2}
\]

Let:

\[
M^{\prime}=\binom{2 n-1}{1}+\binom{2 n-1}{3}+\ldots+\binom{2 n-1}{2 n-1}
\]

Then it holds that:

\[
\begin{gathered}
M+M^{\prime}=\binom{2 n-1}{0}+\binom{2 n-1}{1}+\ldots+\binom{2 n-1}{2 n-1}=(1+1)^{2 n-1}=2^{2 n-1} \\
M-M^{\prime}=(1-1)^{2 n+1}=0
\end{gathered}
\]

From this it follows:

\[
\begin{aligned}
& 2 M=2^{2 n-1}, \quad \text { so } \quad M=\sum_{k=0}^{n-1}\binom{2 n-1}{2 k}=2^{2 n-2} \\
& 2 M^{\prime}=2^{2 n-1}, \quad \text { so } \quad M^{\prime}=\sum_{k=1}^{n}\binom{2 n-1}{2 k-1}=2^{2 n-2}
\end{aligned}
\]

2. Similarly, \(N\) is calculated. With \(N^{\prime}=\sum_{k=1}^{n}\binom{2 n}{2 k-1}\) it holds that:

\[
N+N^{\prime}=(1+1)^{2 n}=2^{2 n} \quad ; \quad N-N^{\prime}=(1-1)^{2 n}=0
\]

From this it follows:

\[
N=\sum_{k=0}^{n}\binom{2 n}{2 k}=2^{2 n-1} \quad \text { (4) } \quad N^{\prime}=\sum_{k=1}^{n}\binom{2 n}{2 k-1}=2^{2 n-1}
\]

3. It holds that:

\[
\begin{aligned}
\sum_{k=0}^{n} k\binom{2 n}{2 k} & =\frac{1}{2} \sum_{k=1}^{n} 2 k \frac{2 n(2 n-1) \cdot \ldots \cdot(2 n-2 k+1)}{1 \cdot 2 \cdot \ldots \cdot 2 k} \\
& =\frac{1}{2} \sum_{k=1}^{n} 2 n \frac{(2 n-1) \cdot \ldots \cdot(2 n-2 k+1)}{1 \cdot 2 \cdot \ldots \cdot(2 k-1)}=n \sum_{k=1}^{n}\binom{2 n-1}{2 k-1}
\end{aligned}
\]

and thus, due to (3):

\[
\sum_{k=0}^{n} k\binom{2 n}{2 k}=n \cdot 2^{2 n-2}
\]

From this it follows:

\[
m=\frac{1}{N} \cdot \sum_{k=0}^{n} k\binom{2 n}{2 k}=\frac{n \cdot 2^{2 n-2}}{2^{2 n-1}}=\frac{n}{2}
\]

b) We obtain:

\[
\begin{aligned}
f(x) & =\frac{1}{N} \cdot \sum_{k=0}^{n}(k-x)^{2}\binom{2 n}{2 k}=\frac{1}{4 N} \sum_{k=0}^{n}(2 k-2 x)^{2}\binom{2 n}{2 k} \\
& =\frac{1}{4 N} \sum_{k=0}^{n}\left(4 k^{2}-8 k x+4 x^{2}\right)\binom{2 n}{2 k} \\
& =\frac{1}{4 N} \sum_{k=0}^{n}\left[2 k(2 k-1)+2 k(1-4 x)+4 x^{2}\right]\binom{2 n}{2 k} \\
& =\frac{1}{4 N}\left[\sum_{k=0}^{n} 2 k(2 k-1)\binom{2 n}{2 k}+2(1-4 x) \cdot \sum_{k=0}^{n} k\binom{2 n}{2 k}+4 x^{2} \cdot \sum_{k=0}^{n}\binom{2 n}{2 k}\right]
\end{aligned}
\]

Now it holds that:

\[
\begin{aligned}
\sum_{k=0}^{n} 2 k(2 k-1)\binom{2 n}{2 k} & =\sum_{k=1}^{n} 2 k(2 k-1) \frac{2 n(2 n-1) \cdot \ldots \cdot(2 n-2 k+1)}{1 \cdot 2 \cdot 3 \cdot \ldots \cdot 2 k} \\
& =\sum_{k=1}^{n} 2 n(2 n-1)\binom{2 n-2}{2 k-2}=2 n(2 n-1) 2^{2 n-3}
\end{aligned}
\]

From (9), (6), (4), and (8) it follows further:

\[
f(x)=\frac{1}{4 N}\left[2 n(2 n-1) 2^{2 n-3}+2(1-4 x) n \cdot 2^{2 n-2}+4 x^{2} \cdot 2^{2 n-1}\right]
\]

and from this, because \(N=2^{2 n-1}\), so \(4 N=2^{2 n+1}\):

\[
\begin{gathered}
f(x)=\frac{1}{2^{2 n+1}}\left(n^{2} \cdot 2^{2 n-2}-n \cdot 2^{2 n-2}+2 n \cdot 2^{2 n-2}-n x \cdot 2^{2 n+1}+x^{2} \cdot 2^{2 n+1}\right)= \\
=x^{2}-n x+\frac{n}{8}+\frac{n^{2}}{4}=\left(x-\frac{n}{2}\right)^{2}+\frac{n}{8} \geq \frac{n}{8}
\end{gathered}
\]

where the equality sign holds for \(x=\frac{n}{2}=m\). Therefore, \(f\) has the smallest function value \(\frac{n}{8}\) at the point \(x=m\).

Adapted from [3]

\subsection*{9.18 XVI. Olympiad 1976}

\subsection*{9.18.1 First Round 1976, Class 12}