Kvant Math Problem 199

We begin by examining the first sum for small values of $n$.

kvantmathematicsolympiad

Verified: no
Verdicts: SKIP + SKIP
Solve time: 6m06s
Source on kvant.digital

Problem

  1. Prove that the sum $$C_n^0-C_{n-1}^1\cdot\dfrac14+C_{n-2}^2\cdot\dfrac1{4^2}-\ldots+(-1)^i C_{n-i}^i\cdot\frac1{4^i}+\ldots$$ $\Big($the sum is taken over all integers $i$, $0\le i\le\dfrac n2\Big)$ is equal to $\dfrac{n+1}{2^n}$.
  2. Prove that if $p$ and $q$ are distinct numbers and $p+q=1$, then the sum $$C_n^0-C_{n-1}^1pq+C_{n-2}^2p^2q^2-\ldots+(-1)^i C_{n-i}^i p^iq^i+\ldots,$$ analogous to the previous one is equal to $\dfrac{p^{n+1}-q^{n+1}}{p-q}$ for arbitrary $n$.

Here $C_n^k$ are binomial coefficients, i.e., $C_n^0=1$ and $C_n^k=\dfrac{n(n-1)\ldots(n-k+1)}{1\cdot2\cdot\ldots\cdot k}$. (The numbers $C_n^k$ were discussed in “Kvant” No. 2 of this year.)

D. A. Fridkin

Exploration

We begin by examining the first sum for small values of $n$. For $n=1$, the sum reduces to $C_1^0 = 1$, and the claimed formula gives $(1+1)/2^1 = 1$, which matches. For $n=2$, the sum is $C_2^0 - C_1^1 \cdot \frac{1}{4} = 1 - \frac{1}{4} = \frac{3}{4}$, while the formula gives $(2+1)/2^2 = 3/4$, confirming agreement. For $n=3$, the sum is $C_3^0 - C_2^1 \cdot \frac{1}{4} + C_1^2 \cdot \frac{1}{16} = 1 - 2\cdot \frac{1}{4} + 0 = 1 - \frac{1}{2} = \frac{1}{2}$, matching $(3+1)/2^3 = 4/8 = 1/2$. The pattern suggests the formula is correct, but these checks alone are not a proof.

The alternating signs and the factors of $(1/4)^i$ indicate a connection to binomial coefficients in expansions such as $(1 - x)^n$, but the indices are shifted, giving $C_{n-i}^i$. The sum resembles a convolution of two sequences, which suggests a generating function approach. The second sum generalizes this by replacing $1/4$ with $pq$ and considering $p+q=1$, hinting at a more general formula that reduces to the first when $p=q=1/2$. The crucial step is identifying a generating function or recurrence that produces $C_{n-i}^i$.

Problem Understanding

The first problem is to prove that

$$\sum_{i=0}^{\lfloor n/2\rfloor} (-1)^i C_{n-i}^i \frac{1}{4^i} = \frac{n+1}{2^n}.$$

The second problem is to prove the generalized version with distinct $p$ and $q$ summing to $1$:

$$\sum_{i=0}^{\lfloor n/2\rfloor} (-1)^i C_{n-i}^i (pq)^i = \frac{p^{n+1}-q^{n+1}}{p-q}.$$

Both problems are of Type B. The core difficulty is recognizing the sum as a coefficient in a suitable generating function expansion or as a solution to a recurrence relation. The key insight is that $C_{n-i}^i$ counts subsets avoiding adjacent elements or can be encoded via recurrences.

Proof Architecture

Lemma 1 establishes a recurrence for $S_n = \sum_{i=0}^{\lfloor n/2\rfloor} (-1)^i C_{n-i}^i x^i$ as $S_n = S_{n-1} - x S_{n-2}$. This follows by splitting the sum into terms with $i=0$ and $i>0$ and reindexing.

Lemma 2 solves the recurrence $S_n = S_{n-1} - x S_{n-2}$ with $S_0=1$, $S_1=1$, giving $S_n = \frac{\alpha^{n+1}-\beta^{n+1}}{\alpha-\beta}$, where $\alpha$ and $\beta$ are roots of $r^2 - r + x = 0$. This is standard for second-order linear recurrences with constant coefficients.

Lemma 3 applies Lemma 2 with $x=1/4$, computing roots $\alpha=1/2$, $\beta=1/2$, taking the limit appropriately, to obtain $S_n = (n+1)/2^n$.

Lemma 4 applies Lemma 2 with $x=pq$ and $\alpha=p$, $\beta=q$, using $p+q=1$, yielding $S_n = (p^{n+1}-q^{n+1})/(p-q)$.

The hardest step is rigorously deriving Lemma 1 and ensuring the sum limits $i\le n/2$ are correctly handled in the recurrence.

Solution

Define $S_n(x) = \sum_{i=0}^{\lfloor n/2\rfloor} (-1)^i C_{n-i}^i x^i$. The goal is to find a closed form. We first establish a recurrence.

For $i\ge 1$, we have $C_{n-i}^i = C_{n-1-(i-1)}^{i-1} + C_{n-2-(i-1)}^{i-1}$ by Pascal's identity applied to the top index. Multiplying by $(-1)^i x^i$ and summing $i=1$ to $\lfloor n/2\rfloor$, we obtain

$$\sum_{i=1}^{\lfloor n/2\rfloor} (-1)^i C_{n-i}^i x^i = -x \sum_{i=0}^{\lfloor (n-2)/2\rfloor} (-1)^i C_{n-2-i}^i x^i + \sum_{i=0}^{\lfloor (n-1)/2\rfloor} (-1)^i C_{n-1-i}^i x^i - C_{n-1}^0 x^0.$$

Including the $i=0$ term $C_n^0 = 1$, this simplifies to

$$S_n(x) = S_{n-1}(x) - x S_{n-2}(x).$$

The base cases are $S_0(x) = 1$ and $S_1(x) = 1$. This confirms Lemma 1.

The characteristic equation of this recurrence is $r^2 - r + x = 0$. Let $\alpha$ and $\beta$ be its roots:

$$\alpha = \frac{1 + \sqrt{1 - 4x}}{2}, \qquad \beta = \frac{1 - \sqrt{1 - 4x}}{2}.$$

Then the general solution is

$$S_n(x) = \frac{\alpha^{n+1} - \beta^{n+1}}{\alpha - \beta},$$

satisfying the initial conditions $S_0 = (\alpha - \beta)/(\alpha - \beta) = 1$ and $S_1 = (\alpha^2 - \beta^2)/(\alpha - \beta) = \alpha + \beta = 1$, confirming Lemma 2.

For the first sum, take $x = 1/4$. Then $\alpha = \beta = 1/2$. The formula reduces via the limit

$$\frac{\alpha^{n+1} - \beta^{n+1}}{\alpha - \beta} \to (n+1) \alpha^n = \frac{n+1}{2^n},$$

establishing the first part.

For the second sum, take $x = pq$, with $p+q = 1$. Then $\alpha = p$, $\beta = q$, giving

$$S_n(pq) = \frac{p^{n+1} - q^{n+1}}{p - q},$$

as required.

This completes the proof.

∎

Verification of Key Steps

The critical step is the derivation of the recurrence $S_n = S_{n-1} - x S_{n-2}$. To check it independently, consider small $n$: $n=2$, $S_2 = C_2^0 - C_1^1 x = 1 - x$, while $S_1 - x S_0 = 1 - x \cdot 1 = 1 - x$, matching. For $n=3$, $S_3 = 1 - 2x + 0 = 1 - 2x$, and $S_2 - x S_1 = (1 - x) - x\cdot 1 = 1 - 2x$, again confirming. The limit as $\alpha \to \beta$ is verified by computing $(1/2)^{n+1} - (1/2)^{n+1} = 0$ formally and applying the derivative trick: $(\alpha^{n+1}-\beta^{n+1})/(\alpha-\beta) \to (n+1) \alpha^n$, which gives the correct factor.

Alternative Approaches

One could attempt a combinatorial argument by interpreting $C_{n-i}^i$ as counting ways to select $i$ disjoint pairs of adjacent positions in a line of $n$ objects and assign weights $(-1/4)^i$. Summing over all $i$ leads to the same recurrence. Another approach uses generating functions: define $F(t) = \sum_{n\ge0} S_n t^n$, which leads to a rational function $F(t) = 1/(1-t+xt^2)$; expanding the denominator in partial fractions recovers the closed form. The recurrence method is preferable because it directly handles the finite sum and naturally extends to the $p,q$ generalization.