Python中求解给定递推关系的第n项

假设我们有一系列数字称为bn，它用递推关系表示，例如b1=1且bn+1/bn=2n。我们需要找到给定n的log2(bn)的值。

因此，如果输入为6，则输出为15，因为log2(bn) = (n * (n - 1)) / 2 = (6*(6-1))/2 = 15

我们可以通过如下方式解决此关系：

b_n+1/b_n = 2ⁿ

b_n/b_n-1 = 2^n-1

…

b₂/b₁ = 2¹，如果我们将以上所有式子相乘，我们可以得到

(b_n+1/b_n).(b_n/b_n-1)……(b₂/b₁) = 2^{n + (n-1)+……….+1}

所以，b_n+1/b₁ = 2^n(n+1)/2

因为1 + 2 + 3 + ………. + (n-1) + n = n(n+1)/2

所以，b_n+1 = 2^n(n+1)/2 * b₁；我们假设初始值b₁ = 1

所以，b_n+1 = 2^n(n+1)/2

用(n+1)替换n后，我们得到：

b_n = 2^n(n-1)/2

两边取对数，我们得到：

log₂(b_n) = n(n-1)/2

示例

让我们来看下面的实现以更好地理解：

在线演示

def add_upto_n(n):
   res = (n * (n - 1)) / 2
   return res
n = 6
print(int(add_upto_n(n)))

输入

6

输出

15

Arnab Chakraborty

更新于：2020年8月25日

569 次浏览

开启你的职业生涯

完成课程获得认证

开始学习