Skip to content

查看源代码:
lattice-path-crossing-binomial-sum.md

---
title: 一条格路走出来的恒等式
createTime: 2026/11/3
categories:
  - study
tags:
  - maths
  - AI-powered
---

这题的式子长成那样,第一反应肯定是“拆成奇偶两段然后递推”。

确实能递推出来。但递推完总觉得哪里不对劲:这个 $2$ 是从哪冒出来的?

后来想明白了——它就藏在一条格路里。

:::problem
设 $n$ 为非负整数,求

$$
\sum_{k=0}^{n} 2^{\left\lfloor (n-k)/2 \right\rfloor} \mathrm{C}_{\left\lfloor (n+k)/2 \right\rfloor}^{\left\lfloor (n-k)/2 \right\rfloor}
$$

的值。
:::

:::note
$\mathrm{C}_m^r$ 表示从 $m$ 个东西里选 $r$ 个的方案数。原题里 $\mathrm{C}$ 的上标被吞了,这里补上;漏掉上标会得到另外一个和,而且没什么意思。
:::

:::warning 人类注
原题里 $\mathrm{C}$ 的上标没被吞,是 $k$。这和 AI 推断出的 $\left\lfloor (n-k)/2 \right\rfloor$ 是等价的。
:::

答案是 $2^n$。下面给两种证法,一种老老实实递推,一种让一条随机格路替我们数。

## 递推法

记

$$
S_n = \sum_{k=0}^{n} 2^{\left\lfloor (n-k)/2 \right\rfloor} \mathrm{C}_{\left\lfloor (n+k)/2 \right\rfloor}^{\left\lfloor (n-k)/2 \right\rfloor}.
$$

关键是把求和项按 $k$ 与 $n$ 的奇偶关系劈成两半。

:::lemma 拆分
令

$$
A(n) = \sum_{j \ge 0} 2^j \mathrm{C}_{n-j}^{j},
$$

(约定 $r > m$ 或 $r < 0$ 时 $\mathrm{C}_m^r = 0$),则对一切 $n \ge 1$ 有

$$
S_n = A(n) + A(n-1).
$$

:::

::::proof
当 $k \equiv n \pmod 2$ 时,写 $k = n - 2j$。此时 $\left\lfloor \dfrac{n-k}{2} \right\rfloor = j$ 且 $\left\lfloor \dfrac{n+k}{2} \right\rfloor = n-j$,对应 $A(n)$ 的一项 $2^j \mathrm{C}_{n-j}^j$。

当 $k \not\equiv n \pmod 2$ 时,写 $k = n - 2j - 1$。此时两处取整分别是 $j$ 与 $n-j-1$,对应 $A(n-1)$ 的一项 $2^j \mathrm{C}_{n-j-1}^j$。

两段合起来即得。$\square$
::::

接下来用 Pascal 递推式把 $A$ 的系数拆开:

$$
A(n) = \sum_{j \ge 0} 2^j \Bigl( \mathrm{C}_{n-j-1}^{j} + \mathrm{C}_{n-j-1}^{j-1} \Bigr) = A(n-1) + 2A(n-2).
$$

于是对 $n \ge 2$,

$$
\begin{align*}
  S_n &= A(n) + A(n-1) \\
  &= 2A(n-1) + 2A(n-2) \\
  &= 2\bigl( A(n-1) + A(n-2) \bigr) \\
  &= 2S_{n-1}.
\end{align*}
$$

初值 $S_0 = 1$、$S_1 = 2$,归纳即得

$$
\boxed{S_n = 2^n}.
$$

(顺便一提,$A(n) = A(n-1) + 2A(n-2)$ 的特征根是 $2$ 与 $-1$,解出 $A(n) = \dfrac{2^{n+1} + (-1)^n}{3}$,代回 $S_n = A(n) + A(n-1)$ 也直接得到 $2^n$。这个式子待会儿还要用。)

## 概率法

递推法好看,但它没解释那个 $2$ 的来历。换个角度:让一条格路替我们数。

### 铺路

在第一象限从原点出发,每一步以 $\dfrac{1}{2}$ 的概率向右走 $(x,y) \to (x+1,y)$,以 $\dfrac{1}{2}$ 的概率向上走 $(x,y) \to (x,y+1)$。走满 $n$ 步,一共 $2^n$ 条等概率的路径。

盯住 $s = x + 2y$:每向右一步 $s$ 加 $1$,每向上一步 $s$ 加 $2$。起点 $s = 0$,走完 $n$ 步之后 $s \in [n, 2n]$,而且 $s$ 严格单调递增。于是**每条路径都恰好穿过一次**直线

$$
\ell:\ x + 2y = n.
$$

穿过的方式只有两种:

- **踩线**:路径落在 $\ell$ 上的某个格点 $(x,y)$;
- **跨线**:路径走“上”这一步时从 $s = n-1$ 跳到 $s = n+1$,从直线中间穿过去。

把这 $2^n$ 条路径按**穿过的横坐标** $k$ 分类,$k$ 从 $0$ 到 $n$。

### 数路径

:::lemma 主引理
穿过横坐标为 $k$ 的路径恰有

$$
2^{\left\lfloor (n-k)/2 \right\rfloor} \mathrm{C}_{\left\lfloor (n+k)/2 \right\rfloor}^{\left\lfloor (n-k)/2 \right\rfloor}
$$

条。
:::

::::proof
分 $n-k$ 的奇偶讨论。

**$n-k$ 为偶数**,记 $j = \dfrac{n-k}{2}$,于是 $k + 2j = n$。此时路径只能踩线,且踩在格点 $(k,j)$ 上。到达 $(k,j)$ 有两种走法:

- 越过直线的那一步是“右”:前缀是一条走到 $(k-1,j)$ 的路径,共 $\mathrm{C}_{k+j-1}^{j}$ 条;
- 越过直线的那一步是“上”:前缀是一条走到 $(k,j-1)$ 的路径,共 $\mathrm{C}_{k+j-1}^{j-1}$ 条。

两种情况下越过之后都还剩 $n - k - j = j$ 步自由走,每步两种走法。于是共

$$
2^j \Bigl( \mathrm{C}_{k+j-1}^{j} + \mathrm{C}_{k+j-1}^{j-1} \Bigr) = 2^j \mathrm{C}_{k+j}^{j}
$$

条。

**$n-k$ 为奇数**,记 $j = \dfrac{n-k-1}{2}$,于是 $k + 2j = n-1$。此时踩线是不可能的(踩线要求 $k + 2j' = n$,而 $n-k$ 是奇数),路径只能跨线:先走到 $(k,j)$,再走一步“上”跳过直线。走到 $(k,j)$ 的路径有 $\mathrm{C}_{k+j}^{j}$ 条,跳过之后还剩 $n-k-j-1 = j$ 步自由走。于是共

$$
2^j \mathrm{C}_{k+j}^{j}
$$

条。

两种情形里 $j = \left\lfloor \dfrac{n-k}{2} \right\rfloor$ 且 $k+j = \left\lfloor \dfrac{n+k}{2} \right\rfloor$,引理得证。$\square$
::::

:::solution 结论
每条路径恰好穿过 $\ell$ 一次,按穿过的横坐标把 $2^n$ 条路径分成 $n+1$ 类,第 $k$ 类的大小由主引理给出,于是

$$
\sum_{k=0}^{n} 2^{\left\lfloor (n-k)/2 \right\rfloor} \mathrm{C}_{\left\lfloor (n+k)/2 \right\rfloor}^{\left\lfloor (n-k)/2 \right\rfloor} = 2^n.
$$
:::

注意两种证法其实是同一回事:递推法里按 $k \equiv n \pmod 2$ 劈开的那两段,恰好就是概率法里“踩线”与“跨线”两类路径。奇偶性只是 $x + 2y$ 的取值被 $2$ 整除与否的另一种说法。

### 验证

主引理说“穿过横坐标为 $k$”是一个可以穷举检验的命题。枚举所有 $2^n$ 条路径、数出每条路径穿过直线的横坐标,再和公式对照:

:::details Code
```python
from itertools import product
from math import comb

def C(m, r):
    return comb(m, r) if m >= 0 and 0 <= r <= m else 0

def summand(n, k):
    return 2 ** ((n - k) // 2) * C((n + k) // 2, (n - k) // 2)

def cross_x(n, steps):
    """返回路径穿过 x + 2y = n 时的横坐标"""
    x = y = 0
    for s in steps:
        if s == "R":
            x += 1
        else:
            y += 1
        if x + 2 * y >= n:
            return x
    return None

for n in range(1, 11):
    cnt = {}
    for steps in product("RU", repeat=n):
        k = cross_x(n, steps)
        cnt[k] = cnt.get(k, 0) + 1
    assert all(cnt.get(k, 0) == summand(n, k) for k in range(n + 1)), n
    assert sum(cnt.values()) == 2 ** n
    print(n, [cnt.get(k, 0) for k in range(n + 1)])
```
:::

输出($n=4$ 时各类的路径数)是 $[4, 4, 6, 1, 1]$,和 $\left(4, 4, 6, 1, 1\right)$ 逐项吻合。

## 推广

概率法的视角比递推法好用得多,因为它把“和”翻译成了“事件”。顺着这个思路可以推广出两件事。

### 踩线与跨线的比例

上面的计数其实把 $2^n$ 条路径又切了一刀:踩线的有 $A(n)$ 条,跨线的有 $A(n-1)$ 条。由递推法算出的闭式,

$$
A(n) = \dfrac{2^{n+1} + (-1)^n}{3}, \qquad A(n-1) = \dfrac{2^n - (-1)^n}{3}.
$$

所以随机取一条 $n$ 步格路,它**恰好落在**直线 $x + 2y = n$ 上的概率是

$$
\dfrac{2^{n+1} + (-1)^n}{3 \cdot 2^n} \longrightarrow \dfrac{2}{3},
$$

而跨过直线的概率趋于 $\dfrac{1}{3}$。

$n$ 越大,这个比例越接近 $2:1$。

### 把斜率换成 $c$

把直线换成

$$
\ell_c:\ x + cy = n \qquad (c \text{ 为正整数}),
$$

路径与分类方式都不变。落在直线上的格点 $(x,y)$ 满足 $x + cy = n$。停在 $(x,y)$ 的路径数为

$$
\Bigl( \mathrm{C}_{x+y-1}^{y} + \mathrm{C}_{x+y-1}^{y-1} \Bigr) 2^{n-x-y} = \mathrm{C}_{x+y}^{y} 2^{n-x-y},
$$

其中两项分别是最后一步走“右”与走“上”的贡献,剩下的 $n-x-y$ 步自由走。于是踩线的路径总数是

$$
T_c(n) = \sum_{y=0}^{\left\lfloor n/c \right\rfloor} 2^{(c-1)y} \mathrm{C}_{n-(c-1)y}^{y},
$$

其余 $2^n - T_c(n)$ 条路径跨过直线。

这个数有个漂亮的递推:

$$
T_c(n) = T_c(n-1) + 2^{c-1} T_c(n-c).
$$

因为它正是长度为 $n$ 的一维长条用“1 格方块”与“$c$ 格长条(带 $2^{c-1}$ 种颜色)”的铺法数——长条占 $c$ 格、方块占 $1$ 格,若用了 $y$ 根长条则占 $cy$ 格,剩下的格子填方块,总块数 $n-(c-1)y$,从中挑出 $y$ 个位置放长条,再给每根长条挑颜色。

几个特例:

- $c = 1$:$T_1(n) = 2^n$,所有路径都踩线,恒等式退化成二项式定理 $\sum_k \mathrm{C}_n^k = 2^n$;
- $c = 2$:回到本文,$T_2(n) = \dfrac{2^{n+1} + (-1)^n}{3}$;
- $c$ 越大,能踩线的格点越稀疏,跨线的路径占比越高。

最后一条其实是废话,但补一句:$c=2$ 之所以特殊,是因为上一步的增量 $2$ 恰好等于组合数里的那个 $2$——巧合得让人怀疑是刻意设计的。

## 结语

回头看,这个恒等式的两种证法其实是同一个计数的两种语言:递推法把和拆成两段,概率法把路径分成两类,两边都是“踩线”与“跨线”。

而 $2$ 从哪来?它就是“每一步都有两种走法”。整件事的起点不过是:一条 $n$ 步的格路有 $2^n$ 条,而每条都会穿过 $x+2y=n$ 一次。

这就完了。