24. Series

1. Series란?

 Series(급수)는 비슷한 형태의 항들을 더하거나 곱한 것이다.

 

곱 형태도 급수다:

 

 이산구조에서 급수를 배우는 이유는 명확하다. 루프가 몇 번 도는지 세고 싶을 때, 지수 성장과 다항 성장을 구분하고 싶을 때, 급수가 그 도구가 된다.

 

---

2. 등비급수 (Geometric Series)

 공비 q인 급수다. The Legend of the Chessboard이 대표적인 예다 — 첫 칸에 밀알 1개, 다음 칸에 2개, 그다음에 4개... 64칸을 채우면 2^64−1 ≈ 1.84×10^19개가 된다.

 

유한 등비급수 (q ≠ 1):

유한 등비급수

 

무한 등비급수:

• |q| < 1이면 수렴: 1 / (1 - q)
• |q| ≥ 1이면 발산

 1 / (1 - q)처럼 무한합을 유한한 식으로 표현한 것을 closed form이라고 한다.

무한히 더해야 할 것을 단번에 계산할 수 있게 해주는 표현이다.

---

3. 지수급수 (Exponential Series)

지수급수

모든 실수 x에 대해 수렴한다. c^x=e^xlnc 로 임의의 밑도 이 급수를 통해 계산할 수 있다.

---

4. 조화급수 (Harmonic Series)

조화급수

항이 계속 0에 가까워지는데도 합은 무한히 발산한다. 단, 엄청나게 느리게 커진다.

lnn ≤ Hn ​≤ lnn + 1, 즉 Hn​ = Θ(lnn)

---

5. 거듭제곱합과 알고리즘 분석

알고리즘의 실행 횟수를 세다 보면 자연스럽게 이런 급수가 나온다.

for i = 1 to n:
    for j = 1 to i:
        do something

 

i = 1일 때 1번, i = 2일 때 2번, ..., i = n일 때 n번. 전부 더하면:

이걸 일반화하면, k겹 중첩 루프는 Θ(n^k)로 실행된다.

중첩 깊이	급수	시간복잡도
1겹	∑i	Θ(n^2)
2겹	∑i^2	Θ(n^3)
$k$겹	∑i^k	Θ(n^k+1)

 

---

6. 급수 조작과 Generating Function

 때로는 알려진 급수를 미분하거나 곱해서 새로운 급수의 closed form을 구할 수 있다.

위처럼 단순한 등비급수가 아닌 경우가 그렇다. 이걸 어떻게 구할까?

 

출발점은 항상 이 등비급수 공식이다:

 

Step 1. 양변을 x에 대해 미분한다:

 

Step 2. 양변에 x를 곱한다:

 

Step 3. x = 1 / 2를 대입한다:

 

 이처럼 수열 a0,a1,a2,…에 대해 F(x)=∑i=0∞aixi 형태의 함수를 generating function이라 부른다. 급수를 마치 다항식처럼 대수적으로 조작하면 복잡한 문제도 풀 수 있다.

 

 핵심 흐름을 정리하면:

알려진 급수 → 미분 / 곱하기 → 새로운 급수의 closed form → 원하는 값 대입

---

 

7. 이항정리 (Binomial Theorem)

 

 이 공식이 강력한 이유는, 특정 값을 대입하는 것만으로 이항계수 관련 급수를 단번에 구할 수 있기 때문이다.

 

• 직관적으로도 말이 된다. n개 원소 집합의 부분집합 개수가 2^n이고, C(n, i)는 크기 i인 부분집합의 수니까.