帕斯卡三角与斐波那契数列解释
帕斯卡三角与斐波那契数列解释
提问于 2013-11-18 13:32:23
好的，我需要重新绘制帕斯卡三角形，并解释嵌入其中的斐波那契数列。我需要观察超过12行的三角形(在斐波那契数列中以数字144结束) --我理解这一部分，因为我只是在解释每一行是如何对角线形成斐波那契数之和的。
但我需要使用的事实是，三角形第n行的第r个数字是C(n，r) = n!/r！不--！
最后这部分让我迷惑了..如何使用C(n，r)来解释三角形中的斐波那契数列？？
请帮帮忙。谢谢
回答 1
Stack Overflow用户
发布于 2014-06-12 21:59:03
考虑以下问题：
如果你可以一次走一步或一次走两步，你能以多少种方式爬上n级阶梯？
解决方案1:让我们为这个问题构造一个递归关系。很明显，递归是这样的：，其中a(1)=1和a(2)=2，因此，n的答案是(n+1)th斐波那契项。
解决方案2:每一种独特的向上爬的方式都对应于一个唯一的1和2序列，这些序列加起来就是n。这样的序列的数量就是我们的答案。让我们开始计算这样的序列：
不带2= $ {n \choose 0 } $的序列数。
1个2= $ {n-1 \choose 1 } $的序列数。
。
。
。
诸若此类。
在偶数n的情况下，最后一项是$ {n/2 \choose n/2 } $。
对于奇数n，它将是$ {(n+1)/2 \choose (n-1)/2 } $。
如你所见，这些是帕斯卡三角形中的对角项。
由于这两个解决方案计算的结果相同，因此它们必须相等。由此，我们得到了斐波那契数与帕斯卡三角形对角线之间的关系。
有关更多疑问，请参阅链接http://ms.appliedprobability.org/data/files/Articles%2033/33-1-5.pdf。
页面原文内容由Stack Overflow提供。腾讯云小微IT领域专用引擎提供翻译支持
原文链接：
https://stackoverflow.com/questions/20040761
复制相关文章
相似问题
腾讯云开发者
