$k> 0$ 。当 $k$为奇数时，
begin{aligned}
sum_{i = 0}^{k} binom{n}{i} &= [binom{n}{0} + binom{n}{1} ] + [binom{n}{2} + binom{n}{3} ] + dots + [binom{n}{k-1} + binom{n}{k} ]
&= binom{n+1}{1} + binom{n+1}{3} + dots + binom{n+1}{k}
end{aligned}
又有
begin{aligned}
sum_{i = 0}^{k} binom{n}{i} &= binom{n}{0} + [binom{n}{1} + binom{n}{2}] + [binom{n}{3} + binom{n}{4}] + dots + [binom{n}{k-2} + binom{n}{k-1}] + binom{n}{k}
&= binom{n}{0} + binom{n+1}{2} + binom{n+1}{4} + dots + binom{n+1}{k-1} + binom{n}{k}
&= binom{n+1}{0} + binom{n+1}{2} + binom{n+1}{4} + dots + binom{n+1}{k-1} + binom{n}{k}
end{aligned}
两式相加得
begin{aligned}
2 sum_{i = 0}^{k} binom{n}{i} = binom{n}{k} + sum_{i=0}^{k} binom{n+1}{i}
end{aligned}
当 $k$ 为偶数时，经过类似的推导，可得
begin{aligned}
2 sum_{i = 0}^{k} binom{n}{i} = binom{n}{k} + sum_{i=0}^{k} binom{n+1}{i}
end{aligned}
容易验证，当 $k = 0$ 时，上式仍成立。于是，对任意 $0 le k le n$ 有
begin{aligned}
2 sum_{i = 0}^{k} binom{n}{i} = binom{n}{k} + sum_{i=0}^{k} binom{n+1}{i}
end{aligned}
亦即
begin{equation}
sum_{i=0}^{k} binom{n+1}{i} = 2 sum_{i = 0}^{k} binom{n}{i} - binom{n}{k} label{E:1}
end{equation}
为了简便，将 $ sum_{i=0}^{k} binom{n}{i}$ 记做 $S(n,k)$ 。反复使用 eqref{E:1} 式，可以得到
begin{aligned} S(n,k) = 2^{n-k} S(k,k) - 2^{n - k - 1} binom{k}{k} - 2^{n - k - 2} binom{k+1}{k} - dots - 2^{1} binom{n-2}{k} - 2^{0} binom{n-1}{k} end{aligned}
