一图胜万言: fibonacci数列的一些结论的有趣证明

看到一篇有趣的文章, 作者举了一个简单的出现了fibonacci数列的例子, 然后用这个例子证明了一系列关于fibonacci数列的结论. 这种巧妙的构造总是让人惊叹如果生活中处处都存在这样的“捷径”那该是多么精彩!

 试想有两排蜂巢形状的路径, 假设现在你要从左上S处开始行走到达右下E处,
 每次只能向右走, 或者从上面的一格走到其右下的一格(从下面的一格走到其右上的一格),
 那么一共有多少不同的路径呢?

容易证明, 这个路径数是一个fibonacci数, 作者给出了这个图清楚地表示了从S走到每一个格子不同的路径数.

容易证明, 路径数序列与fibonacci数列的初始值以及递归形式都是一样的, 这里走到第一个格子S只有F(1) = 1条路径.

现在可以开始证明一些关于fibonacci数列的结论了, 这些结论用其他方法当然也能够比较容易地得到, 但是用作者给出的这个例子, 我们将看到这些结论是多么的“显然”.

首先作者把这些蜂巢简化成了一些互联的点, 下面说明

F(a) * F(b) + F(a+1) * F(b+1) = F(a+b+1)

如图, 一个包含a+b+1个点的路, 总共有F(a+b+1)种不同的路径. 而这些路径可以分成两部分: 通过第a+1个点的以及没有通过第a+1个点的. 前者一共有: F(a+1) * F(b+1)条, 而后者则有F(a) * F(b)条.

于是, 结论不证自明.

如果这种方法只能证明一个结论, 那么也并不算神奇. 此文神奇之处正在于, 这种fibonacci数列的呈现方式帮助作者直观地证明了一系列命题, 比如:

记P(N)为将整数N表示为1和2的有序数列之和, 证明P(N) = F(N+1)

当然, 这个结论用归纳法也是很容易证明的, 那么作者的这种表示方法是如何证明这个结论的呢?

如图, 可以发现12表示成的1和2之和, 每一种方式都一一对应了一种S->E的路径, 于是, 结论自然又不证自明.

还有一些诸如降N表示为1和2之和, 不考虑顺序有多少种方式? (不需要用文章的方法..) 用1x2的多米诺平铺2*n的地板有多少种方式等等的问题, 都是不错的等菜题.

有兴趣的话可以通读全文, 看看作者如何证明其他有趣结论.