技术求助：帕斯卡三角形带2幂的对角线和及组合恒等式证明

Hey there! Let's break down these two combinatorial problems step by step—they're both great examples of how recursion, induction, and generating functions can crack tricky summations.

First, let's define the diagonal we're talking about: in Pascal's triangle, take the diagonal starting at the $n$-th row, 0-th entry (this includes terms like $\binom{n}{0}, \binom{n+1}{1}, \binom{n+2}{2}, ..., \binom{n+k}{k}, ...$). The sum with powers of 2 we're studying is:
$$S(n) = \sum_{k=0}^\infty \binom{n+k}{k} 2^{-(n+k)}$$

Key Observations & Proof #

We can solve this using generating functions or recursion:

• Generating Function Approach: We know the standard generating function for combinations of the form $\binom{n+k}{k}$ is:
  $$\sum_{k=0}^\infty \binom{n+k}{k} x^k = \frac{1}{(1-x)^{n+1}}$$
  Set $x = \frac{1}{2}$, and multiply both sides by $2^{-n}$ (to account for the $2^{-(n+k)}$ term):
  $$\sum_{k=0}^\infty \binom{n+k}{k} 2^{-(n+k)} = 2^{-n} \cdot \frac{1}{(1-\frac{1}{2})^{n+1}} = 2^{-n} \cdot 2^{n+1} = 2$$
• Recursive Approach: Let $S(n)$ be the sum. For base case $n=0$, $S(0) = \sum_{k=0}^\infty 2^{-k} = 2$ (geometric series). Assume $S(n-1)=2$, then use Pascal's identity $\binom{n+k}{k} = \binom{n+k-1}{k} + \binom{n+k-1}{k-1}$ to split the sum:
  $$S(n) = 2^{-n} + \frac{1}{2}S(n-1) + \frac{1}{2}S(n)$$
  Solving for $S(n)$ gives $S(n)=S(n-1)=2$, so all such diagonal sums equal 2.

You mentioned struggling with the index-dependent exponent using induction or direct methods—let's fix that with a structured inductive proof that leverages Pascal's identity to eliminate the exponent dependency issue.

Inductive Proof #

• Base Case: When $n=0$, the sum is just $\binom{0+0}{0}2^{-(0+0)} = 1$, which equals the right-hand side.
• Inductive Step: Assume the statement holds for some $m \geq 0$, i.e.:
  $$\sum_{i=0}^m \binom{m+i}{i}2^{-(m+i)} = 1$$
  We need to show it holds for $m+1$:
  $$\sum_{i=0}^{m+1} \binom{(m+1)+i}{i}2^{-((m+1)+i)} = 1$$

Start by splitting the sum into the first term and the rest, then apply Pascal's identity $\binom{m+1+i}{i} = \binom{m+i}{i} + \binom{m+i}{i-1}$:
$$\sum_{i=0}^{m+1} \binom{m+1+i}{i}2^{-(m+1+i)} = 2^{-(m+1)} + \sum_{i=1}^{m+1} \left(\binom{m+i}{i} + \binom{m+i}{i-1}\right)2^{-(m+1+i)}$$

Split the sum into two parts, factor out $\frac{1}{2}$ (to handle the $2^{-(m+1+i)}$ term):
$$= 2^{-(m+1)} + \frac{1}{2}\sum_{i=1}^{m+1} \binom{m+i}{i}2^{-(m+i)} + \frac{1}{2}\sum_{i=1}^{m+1} \binom{m+i}{i-1}2^{-(m+i)}$$

Now rewrite each sum:

1. The first sum becomes $\frac{1}{2}\left(\sum_{i=0}^{m+1} \binom{m+i}{i}2^{-(m+i)} - 2^{-m}\right)$. Using our inductive hypothesis, $\sum_{i=0}^m \binom{m+i}{i}2^{-(m+i)}=1$, so this becomes $\frac{1}{2}\left(1 + \binom{2m+1}{m+1}2^{-(2m+1)} - 2^{-m}\right)$.
2. The second sum: let $j = i-1$, so it becomes $\frac{1}{2}\sum_{j=0}^m \binom{m+1+j}{j}2^{-((m+1)+j)} = \frac{1}{2}\left(\sum_{j=0}^{m+1} \binom{m+1+j}{j}2^{-((m+1)+j)} - \binom{2m+2}{m+1}2^{-(2m+2)}\right)$. Let’s call the full sum we’re trying to prove $L$, so this is $\frac{1}{2}\left(L - \binom{2m+2}{m+1}2^{-(2m+2)}\right)$.

Substitute back and multiply through by 2 to eliminate fractions:
$$2L = 2^{-m} + 1 + \binom{2m+1}{m+1}2^{-(2m+1)} - 2^{-m} + L - \binom{2m+2}{m+1}2^{-(2m+2)}$$

Simplify using the identity $\binom{2m+2}{m+1} = 2\binom{2m+1}{m+1}$ (since $\binom{2m+1}{m} = \binom{2m+1}{m+1}$):
$$2L = 1 + L + \frac{\binom{2m+1}{m+1}}{2^{2m+1}} - \frac{2\binom{2m+1}{m+1}}{2^{2m+2}}$$
The last two terms cancel out, leaving $2L = 1 + L$, so $L=1$.

Bonus Probability Interpretation #

This sum also makes intuitive sense probabilistically: imagine a fair coin flip game where you stop when you get $n$ heads or $n+1$ tails. The term $\binom{n+i}{i}2^{-(n+i)}$ is the probability of stopping after $i$ tails and $n$ heads (with the last flip being a head). Summing over all possible $i$ (0 to $n$) gives the total probability of winning the game, which must equal 1 (since the game always ends).

内容的提问来源于stack exchange，提问作者Jan K