Fibonacci数列最好说明一下前两项是f[1] = f[2] = 1,递推式f[n+2] = f[n+1]+f[n] ①.
由S[n] = ∑{0 ≤ k ≤ n} (-1)^k·C(n,k)·f[n+1+k],其实应该有S[1] = f[2]-f[3] = -f[1] = -1.
S[2] = f[3]-2f[4]+f[5] = -f[2]+f[3] = 1,S[3] = f[4]-3f[5]+3f[6]-f[7] = -f[3]+2f[4]-f[5] = -1.
所以应该是S[1] = -1,S[2] = 1,S[3] = -1,...这样.
从上面几个简单的例子其实不难看到证明的思路.
关键就是组合恒等式C(n+1,k) = C(n,k)+C(n,k-1) ②.
为了方便,约定C(n,-1) = C(n,n+1) = 0 ③,则上式对k = 0,1,...,n+1都成立.
S[n+1] = ∑{0 ≤ k ≤ n+1} (-1)^k·C(n+1,k)·f[n+2+k]
= ∑{0 ≤ k ≤ n+1} (-1)^k·(C(n,k)+C(n,k-1))·f[n+2+k] (由②)
= ∑{0 ≤ k ≤ n+1} (-1)^k·C(n,k)·f[n+2+k]-∑{0 ≤ k ≤ n+1} (-1)^(k-1)·C(n,k-1)·f[n+2+k]
= ∑{0 ≤ k ≤ n} (-1)^k·C(n,k)·f[n+2+k]-∑{1 ≤ k ≤ n+1} (-1)^(k-1)·C(n,k-1)·f[n+2+k] (由③)
= ∑{0 ≤ k ≤ n} (-1)^k·C(n,k)·f[n+2+k]-∑{0 ≤ k ≤ n} (-1)^k·C(n,k)·f[n+3+k]
= ∑{0 ≤ k ≤ n} (-1)^k·C(n,k)·(f[n+2+k]-f[n+3+k])
= ∑{0 ≤ k ≤ n} (-1)^k·C(n,k)·(-f[n+1+k]) (由①)
= -∑{0 ≤ k ≤ n} (-1)^k·C(n,k)·f[n+1+k]
= -S[n].