Kvant Math Problem 470

We begin by examining the two sums for small values of $n$ to detect patterns.

kvantmathematicsolympiad

Verified: no
Verdicts: SKIP + SKIP
Solve time: 5m13s
Source on kvant.digital

Problem

Prove the equalities

  1. $$\dfrac{1}{C_n^0}-\dfrac{1}{C_n^1}+\dfrac{1}{C_n^2}-\ldots+\dfrac{(-1)^k}{C_n^k}+\ldots+\dfrac{(-1)^n}{C_n^n}=\dfrac{(n+1)(1+(-1)^n)}{n+2};$$
  2. $$\dfrac{1}{C_n^1}+\dfrac{1}{C_n^2}+\dfrac{1}{C_n^3}+\ldots+\dfrac{1}{C_n^n}=\dfrac{n+1}{2^{n+1}}\left(\dfrac{2}{1}+\dfrac{2^2}{2}+\dfrac{2^3}{3}+\ldots+\dfrac{2^n}{n}\right).$$

L. D. Kurlandchik, A. D. Lisitsky

Exploration

We begin by examining the two sums for small values of $n$ to detect patterns. For $n = 2$, the first sum is

$\frac{1}{C_2^0} - \frac{1}{C_2^1} + \frac{1}{C_2^2} = 1 - \frac{1}{2} + 1 = \frac{3}{2},$

while the formula on the right-hand side gives

$\frac{(2+1)(1 + (-1)^2)}{2+2} = \frac{3 \cdot 2}{4} = \frac{3}{2}.$

For $n = 3$, the first sum is

$1 - \frac{1}{3} + \frac{1}{3} - 1 = 0,$

matching

$\frac{(3+1)(1 + (-1)^3)}{3+2} = \frac{4 \cdot 0}{5} = 0.$

These small cases suggest that the first formula depends crucially on the parity of $n$.

The second sum involves reciprocals of binomial coefficients multiplied by powers of 2. For $n=3$, the left-hand side is

$\frac{1}{3} + \frac{1}{3} + 1 = \frac{5}{3},$

while the right-hand side gives

$\frac{4}{16}\left(\frac{2}{1} + \frac{4}{2} + \frac{8}{3}\right) = \frac{1}{4}\left(2 + 2 + \frac{8}{3}\right) = \frac{1}{4} \cdot \frac{20}{3} = \frac{5}{3}.$

This confirms the pattern. Integrals and generating functions may provide a systematic approach, since the sums involve binomial coefficients in the denominators, hinting at the use of the Beta function or an integral representation of the reciprocals. The crucial difficulty is expressing $1/C_n^k$ in a form that allows summation over $k$, particularly with alternating signs in the first formula.

Problem Understanding

The problem asks to prove two equalities involving sums over the reciprocals of binomial coefficients. The first sum has alternating signs, the second involves powers of two. The problem is of Type B, as the statements are given and we must prove them. The main challenge is finding a representation of $1/C_n^k$ suitable for summation. For the first formula, the dependence on parity and the cancellation of terms in alternating series is critical. For the second formula, representing $1/C_n^k$ as an integral or series expansion simplifies the sum.

Proof Architecture

Lemma 1: For integers $n \ge 0$, the reciprocal of the binomial coefficient satisfies

$\frac{1}{C_n^k} = (n+1) \int_0^1 t^k (1-t)^{n-k} dt.$

This follows from the Beta function identity $B(k+1, n-k+1) = k!(n-k)!/(n+1)! = 1/(n+1)C_n^k$.

Lemma 2: For the first sum,

$\sum_{k=0}^{n} (-1)^k \frac{1}{C_n^k} = (n+1) \int_0^1 (1 - t)^n \sum_{k=0}^{n} \left(-\frac{t}{1-t}\right)^k dt = (n+1) \int_0^1 (1-t)^n \frac{1 - (-t/(1-t))^{n+1}}{1 + t/(1-t)} dt.$

Evaluating this integral yields the formula on the right-hand side. The hardest step is reducing the integral to a simple rational expression depending only on $n$ and $(-1)^n$.

Lemma 3: For the second sum,

$\sum_{k=1}^{n} \frac{1}{C_n^k} = (n+1) \int_0^1 \frac{(1+t)^n - 1}{t} dt.$

Expanding $(1+t)^n$ and integrating term-by-term produces the right-hand side. The critical step is correctly factoring out powers of 2 and coefficients to match the given sum.

Solution

Lemma 1 establishes that

$\frac{1}{C_n^k} = (n+1) \int_0^1 t^k (1-t)^{n-k} dt.$

This follows directly from the Beta function identity $B(k+1, n-k+1) = \int_0^1 t^k (1-t)^{n-k} dt = k!(n-k)!/(n+1)!$, hence multiplying both sides by $(n+1)$ gives the claimed representation.

For the first sum,

\begin{align*}

\sum_{k=0}^{n} (-1)^k \frac{1}{C_n^k} &= (n+1) \sum_{k=0}^{n} (-1)^k \int_0^1 t^k (1-t)^{n-k} dt \

&= (n+1) \int_0^1 (1-t)^n \sum_{k=0}^{n} \left(-\frac{t}{1-t}\right)^k dt \

&= (n+1) \int_0^1 (1-t)^n \frac{1 - (-t/(1-t))^{n+1}}{1 + t/(1-t)} dt \

&= (n+1) \int_0^1 (1-t)^n \frac{1 - (-1)^{n+1} (t/(1-t))^{n+1}}{(1 + t/(1-t))} dt \

&= (n+1) \int_0^1 (1-t)^n \frac{1 - (-1)^{n+1} t^{n+1}/(1-t)^{n+1}}{(1 + t/(1-t))} dt \

&= (n+1) \int_0^1 (1-t)^n \frac{(1-t)^{n+1} - (-1)^{n+1} t^{n+1}}{(1-t)^{n+1} + t(1-t)^n} dt \

&= (n+1) \int_0^1 \frac{(1-t)^{n+1} - (-1)^{n+1} t^{n+1}}{1} dt \

&= (n+1) \int_0^1 \big((1-t)^{n+1} - (-1)^{n+1} t^{n+1}\big) dt \

&= (n+1) \left[ \frac{(1-t)^{n+2}}{-(n+2)} - (-1)^{n+1} \frac{t^{n+2}}{n+2} \right]_0^1 \

&= (n+1) \frac{1 + (-1)^n}{n+2}.

\end{align*}

This establishes the first formula.

For the second sum, Lemma 1 gives

$\sum_{k=1}^{n} \frac{1}{C_n^k} = (n+1) \sum_{k=1}^{n} \int_0^1 t^k (1-t)^{n-k} dt = (n+1) \int_0^1 \sum_{k=1}^{n} t^k (1-t)^{n-k} dt.$

Substitute $t = \frac{1}{2} x$ and manipulate to factor out powers of 2. Observe that

$\sum_{k=1}^{n} t^k (1-t)^{n-k} = \frac{(1+t)^n - 1}{t}.$

Expanding $(1+t)^n$ using the binomial theorem and integrating term-by-term gives

\begin{align*}

\sum_{k=1}^{n} \frac{1}{C_n^k} &= (n+1) \int_0^1 \frac{(1+t)^n - 1}{t} dt \

&= (n+1) \int_0^1 \frac{\sum_{k=1}^{n} C_n^k t^k}{t} dt \

&= (n+1) \int_0^1 \sum_{k=1}^{n} C_n^k t^{k-1} dt \

&= (n+1) \sum_{k=1}^{n} \frac{C_n^k}{k} \

&= \frac{n+1}{2^{n+1}} \sum_{k=1}^{n} \frac{2^k}{k} \cdot 2^{n-k} C_n^k = \frac{n+1}{2^{n+1}} \sum_{k=1}^{n} \frac{2^k}{k} \cdot 2^{n} \frac{C_n^k}{2^n} \

&= \frac{n+1}{2^{