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

    观察下面几个式子：

      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 里的元素确实是一样多的。

41 条评论

发表评论

89  +    =  93