파이썬으로 점화식의 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^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₁ = 1이라고 가정하면,

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

이제 n을 (n+1)로 치환하면,

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

이처럼 복잡해 보이는 점화식 문제도 수학적 유도를 통해 간단한 닫힌 형태(closed form)의 공식으로 변환하면, 반복 계산 없이 O(1) 시간에 답을 구할 수 있습니다.