Pythonで漸化式のn番目の項を求める方法：log₂(bₙ)の計算

次のような数列 b_n を考えてみましょう。この数列は、b₁ = 1 および b_n+1/b_n = 2ⁿ という漸化式で表されます。ここでの課題は、与えられた n に対して log₂(b_n) の値を求めることです。

たとえば、入力が 6 の場合、出力は 15 になります。これは log₂(b_n) = (n × (n − 1)) / 2 = (6 × (6 − 1)) / 2 = 15 となるためです。

数学的な導出手順

この問題は、漸化式を段階的に展開することで解くことができます。

b_n+1/b_n = 2ⁿ

b_n/b_n−1 = 2ⁿ⁻¹

…（中略）…

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₁ = 1 を仮定すると、

b_n+1 = 2^n(n+1)/2 × b₁ = 2^n(n+1)/2

n を (n+1) で置き換えると、最終的に次の式が得られます。

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

両辺の底を2とする対数を取ると、

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

Pythonでの実装例

それでは、実際の実装を見てみましょう。

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

n = 6
print(int(add_upto_n(n)))

入力

6

出力

15

まとめ

このように、漸化式を直接計算する代わりに、数列の規則性を解析して閉じた形（一般項）を導出することで、O(1) の計算量で任意の n 番目の項の対数値を瞬時に求めることができます。大きな n に対しても効率的に動作するのが、このアプローチの大きな利点です。