A. Summations

합 식에 대해 알아보자.

A.1. Summation formulas and properties

유한합은 \sum_{i=1}^{n} a_{i}, 무한합은 \sum_{i=1}^{\infty} a_{i} = \lim_{n \to \infty} \sum_{i=1}^{n} a_{i} 로 나타낼 수 있다. 이것이 존재하지 않으면 이 급수는 발산하고, 존재하면 수렴한다고 한다. \sum_{i=1}^{\infty} \lvert a_{i} \rvert가 수렴하는 절대수렴급수는 더하는 순서를 바꿀 수 있으나 단지 수렴하는 급수는 바꿀 수 없다.

Linearity

합과 무한합은 선형 연산과 \Theta-표현을 보존한다.

Arithmetic series

\sum_{k=1}^{n}k = \frac{n(n+1)}{2} = \Theta(n^{2})산술급수라 한다.

Sum of squares and cubes

\sum_{k=1}^{n}k^{2} = \frac{n(n+1)(2n+1)}{6}, \sum_{k=1}^{n}k^{3} = \frac{n^{2}(n+1)^{2}}{4}이다.

Geometric series

x \neq 1에 대해 기하급수(지수급수) \sum_{k=0}^{n} x^{k} = \frac{x^{n+1} - 1}{x - 1}이다. \lvert x \rvert < 1이면 \sum_{k=0}^{\infty} x^{k} =\frac{1}{1 - x}이다.

Harmonic series

n번째 조화 수H_{n} = \sum_{k=1}^{n} \frac{1}{k} = \ln n + O(1)이다.

Integrating and differentiating series

|x| < 1일 때 \sum_{k=0}^{\infty} k x^{k} = \frac{x}{(1 - x)^{2}}이다.

Telescoping series

단축\sum_{k=1}^{n} (a_{k} - a_{k-1}) = a_{n} - a_{0}이다. 비슷하게, \sum_{k=0}^{n-1} (a_{k} - a_{k+1}) = a_{0} - a_{n}이다. \sum_{k=1}^{n-1} \frac{1}{k(k+1)} = 1 - \frac{1}{n}이다.

Products

\prod_{k=1}^{n} a_{k}는 숫자 n개의 곱이다. n = 1이면 이 값은 0이다. \lg(\prod_{k=1}^{n} a_{k}) = \sum_{k=1}^{n} \lg(a_{k})이다.

A.2. Bounding summations

합의 상한이나 하한을 정하는 법을 알아보자.

Mathematical induction

많은 경우는 수학적 귀납법으로 증명이 가능하다. \sum_{k=0}^{n+1} 3^{k} \leq c3^{n} + 3^{n+1} \leq c3^{n+1} 등의 증명이 있다.

Bounding the terms

항 각각에 대한 상한을 이용하는 방법도 있다. \sum_{k=1}^{n} k \leq n^{2}

아니면 항간의 비율의 상한이 0 < r < 1일 때 \sum_{k=0}^{n} a_{k} \leq \sum_{k=0}^{\infty} a_{0}r^{k} = \frac{a_{0}}{1 - r} 등을 쓰는 방법도 있다.

이 때 0 < r < 1이 상수여야 하는 것은 중요하다. \sum_{k=1}^{\infty} \frac{1}{k} = \infty이다. 인접한 항간의 비율이 1로 무한히 접근하기 때문이다.

Splitting summations

합들을 쪼개 계산하는 방법도 있다. \sum_{k=1}^{n} k \geq \sum_{k=\frac{n}{2}}^{n} k = \Omega(n^{2})

이는 무한 급수에도 자주 쓰인다.

또는 이런 방법도 가능하다. \sum_{k=1}^{n} \frac{1}{k} \leq \sum_{i=0}^{\lfloor \lg n \rfloor} \sum_{j=0}^{2^{i} - 1} \frac{1}{2^{i} + j} \leq \sum_{i=0}^{\lfloor \lg n \rfloor} \sum_{j=0}^{2^{i} - 1} \frac{1}{2^{i}} = \sum_{i=0}^{\lfloor \lg n \rfloor} 1 \leq \lg n + 1

Approximation by integrals

적분에 의한 근사도 가능하다. 다음의 성질을 이용한다.

\int_{m-1}^{n} f(x) dx \leq \sum_{k=m}^{n} f(k) \leq \int_{m}^{n+1} f(x) dx

이를 이용하면 다음의 성질을 보일 수 있다. \ln(n+1) \leq \sum_{k=1}^{n} \frac{1}{k} \leq \ln n + 1

답글 남기기

아래 항목을 채우거나 오른쪽 아이콘 중 하나를 클릭하여 로그 인 하세요:

WordPress.com 로고

WordPress.com의 계정을 사용하여 댓글을 남깁니다. 로그아웃 /  변경 )

Google photo

Google의 계정을 사용하여 댓글을 남깁니다. 로그아웃 /  변경 )

Twitter 사진

Twitter의 계정을 사용하여 댓글을 남깁니다. 로그아웃 /  변경 )

Facebook 사진

Facebook의 계정을 사용하여 댓글을 남깁니다. 로그아웃 /  변경 )

%s에 연결하는 중