在Python中找到给定递归关系的第n个项

假设我们有一个称为bn的数字序列，它使用类似b1 = 1和bn + 1 / bn = 2n的递归关系表示。我们必须找到给定n的log2(bn)的值。

因此，如果输入类似于6，则输出将为5，因为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}

通过记录双方，我们得到

对数₂（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