用阶乘之和计算第 n 个斐波那契数？

Question

在我努力解决leetcode 70，爬楼梯的过程中，我想到了一个使用阶乘的答案（有多少种不同的方式可以形成相同元素的直线）。后来想到这道题也可以用斐波那契来解，前几个答案貌似是一样的。

我的问题是：关于为什么这两者可能相同，是否有正式的数学证明（或直观的解释）？或者它们是否相同？

爬楼梯问题是一个问题，要求你找出一个人只走一两步就可以爬上 n 级楼梯的方法数。因为这只是一种表达 1 和 2 总和为 n 的方式有多少种不同的方式。我就这样解决了问题。 max_one 和 max_two 是可以存在的 1 或 2 的最大数量，我迭代了行中可以有多少个 2，找出给定数量的 2 如何形成每条不同的线（表示为一世）分子是一行中有多少个元素，分母是一行中有多少个相同的元素（多少个1，多少个2）：

from math import factorial as fac
class Solution:
  def climbStairs(self, n):
    if n == 1:  return 1
    if n == 2:  return 2 
    max_two = n//2
    max_one = n
    ways = 0
    for i in range(0,max_two+1):
      ways += fac(max_one-i)/(fac(max_one-2*i) * fac(i))

    return int(ways)

Answer 1

恭喜！您重新发现了一个非常酷的恒等式，涉及斐波那契数列。具体来说，您找到的规则就是这张图片中直观展示的规则，其中沿着这些倾斜对角线将帕斯卡三角形的项相加得到斐波那契数列：

要了解这是为什么，请注意求和中的每一项都等于 (n - i) 选择 i，这是帕斯卡三角形的第 (n - i) 行第 i 列中的条目。求和中的每一项对应于向上移动一行和一列，因此这些线上的角度。

至于证明，您概述的论点本质上是重复计算论点的基础。我们知道，斐波那契数列计算了以一号和二号步数走下一段楼梯的方法数，我们可以通过归纳法严格证明这一点。此外，我们知道您的总和计数相同的数量，因为您正在使用 0、1、2、3、... 等大小为 2 的步长来枚举所有向下路径的方法。由于我们用两种方式计算相同的数量，因此这两个表达式必须相等。

如果这还不够，您可以通过归纳法证明这一点，使用恒等式 (n choose k) = (n-1 choose k) + (n-1 choose k-1) 并拆分分为 n 为偶数和 n 为奇数的情况。

希望对您有所帮助！

用阶乘之和计算第 n 个斐波那契数？

Calculating the nth Fibonacci number with a sum of factorials?

python

factorial

fibonacci