你在这里

立方和公式的一个组合数学证明

    观察下面几个式子:
      13 = 1; (1)2 = 1
      13 + 23 = 9; (1 + 2)2 = 9
      13 + 23 + 33 = 36; (1 + 2 + 3)2 = 36
      13 + 23 + 33 + 43 = 100; (1 + 2 + 3 + 4)2 = 100
      …… ……
    大家应该可以猜到,事实上,对于任意正整数 n ,下述等式永远成立:
      13 + 23 + … + n3 = (1 + 2 + … + n)2
    这个恒等式的证明方法有很多很多,今天我看到了一种有趣的组合证明方法,来源于《Proofs that Really Count》的第 8 章。

    首先,让我们考虑所有这样的数列:它由 0 到 n 之间的整数组成,长度为 4 ,并且最后一个数严格大于前面所有的数。我们把所有满足要求的数列所组成的集合叫做集合 A 。也就是说:
      A = {(a, b, c, d) | 0 ≤ a, b, c < d ≤ n}
    集合 A 里面有多少元素呢?我们可以这样来计算:最后一个数 d 的值可以从 1 到 n 当中选择,只要 d 选定了,前面的数都可以从 0 到 d - 1 之间任意选择,这一共会产生 d3 种选法。于是,集合 A 的元素个数就是 13 + 23 + … + n3。
    接下来,让我们考虑所有这样的数列:它由 0 到 n 之间的整数组成,长度为 4 ,并且第 2 个数严格大于第 1 个数,第 4 个数严格大于第 3 个数。我们把所有满足要求的数列所组成的集合叫做集合 B 。也就是说:
      B = {(x, y, z, w) | 0 ≤ x < y ≤ n 并且 0 ≤ z < w ≤ n}
    集合 B 里面有多少元素呢?我们可以按照下面这种方式来计算。如果 x 选的是 n - 1,那么 y 有 1 种选法;如果 x 选的是 n - 2,那么 y 有 2 种选法……如果 x 选的是 0,那么 y 有 n 种选法。总之,选择合适的 x 和 y 就有 1 + 2 + … + n 种选法。类似地,选择合适的 z 和 w 也有 1 + 2 + … + n 种选法,因而满足要求的数列一共有 (1 + 2 + … + n)2 个。
    接下来,我们在 A 、 B 两个集合之间建立一种一一对应的关系,从而证明 13 + 23 + … + n3 = (1 + 2 + … + n)2 。对于 A 当中的任意一个元素 (a, b, c, d) :如果 a < b ,那么数列保持原形不变,仍然是 (a, b, c, d) ;如果 a > b ,那么把数列变为 (c, d, b, a) ;如果 a = b ,那么把数列变为 (b, d, c, d) 。容易看出,集合 A 当中的每一个元素都会唯一地对应于集合 B 当中的某个合法的元素。举三个例子:
      (1, 2, 3, 4) → (1, 2, 3, 4)
      (2, 1, 3, 4) → (3, 4, 1, 2)
      (1, 1, 2, 4) → (1, 4, 2, 4)
    反过来,对于 B 当中的任意一个元素 (x, y, z, w) :如果 y < w ,那么数列保持原形不变,仍然是 (x, y, z, w) ;如果 y > w ,那么把数列变为 (w, z, x, y) ;如果 y = w ,那么把数列变为 (x, x, z, w) 。容易看出,集合 B 当中的每一个元素都能变回为集合 A 当中的元素。因此,集合 A 和集合 B 里的元素确实是一样多的。