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 次瀏覽

開啟你的職業生涯

完成課程獲得認證

開始學習