수열

• 정의
  • 수열
  • 등비수열
  • 등차수열
  • 점화관계
    • 반복법
• 용어 정리
• 참고문헌

정의

수열

Sequences

A sequence is a function from a subset of the set of integers (usually either the set $\{0, 1, 2, ...\}$ or the set $\{1,2,3,...\}$)to a set S. We use the notation $a_n$ to denote the image of the integer $n$. We call $a_n$ a term of the sequence.

• 수열은 정수 집합의 부분집합($\{0, 1, 2, ... \}$)으로부터 집합 S로의 함수이다.
• 정수 $n$의 상(image)을 나타내기 위해서 $a_n$을 사용한다.
• $a_n$을 수열의 항(term)이라고 한다$a_n$을 수열의 항(term)이라고 한다.

등비수열

geometric progression

A geometric progression is a sequence of the form
$a, ar, ar^2, ..., ar^n, ...$
where the initial term $a$ and the common ratio $r$ are real numbers.

• 등비수열은 지수 함수 $f(x) = ar^x$의 이산적 모습이다.

등차수열

arithmetic progression

An arithmetic progression is a sequence of the form
$a, a + d, a + 2d, ..., a + nd, ...$
where the initial term $a$ and the common difference $d$ are real numbers.

• 등차수열은 선형 함수 $f(x) = dx + a$의 이산적 모습이다.

점화관계

Recurrence Relations

A recurrence relation for the sequence $\{a_n\}$ is an equation that expresses $a_n$ in terms of one or more of the previous terms of the sequence, namely, $a_0, a_1, ..., a_{n−1}$, for all integers $n$ with $n ≥ n_0$, where $n_0$ is a nonnegative integer. A sequence is called a solution of a recurrence relation if its terms satisfy the recurrence relation. (A recurrence relation is said to recursively define a sequence.)

• $a_n$을 수열에 있는 하나 이상의 이전 항들을 이용하여 표시하는 등식.
• 수열의 항들이 점화관계를 만족하면, 이 수열을 점화관계의 해(solution)라고 부른다.
• 점화관계를 수열의 재귀적 정의라고도 부른다.
• 점화관계로부터 수열의 닫힌 공식(closed formula, 수열의 일반항)을 구하는 것을 다음과 같이 부른다.
  • "초기 조건이 수반된 점화관계를 풀었다"
  • "수열의 해를 얻었다"

반복법

iteration

점화 관계를 초기조건부터 연속적으로 적용하여 일반항을 얻을 수 있을 때까지 반복하는 방법.

반복법으로 다음 점화관계를 풀어보자.

반복하다 보면 규칙이 보인다.

• 이렇게 초항부터 반복을 시작하여 $a_n$을 얻어내는 방법을 전향 대입(forward substitution)이라 한다.
• 반대로 $a_n$ 부터 반복하는 것을 후향 대입(backward substitution)이라 한다.

용어 정리

참고문헌

• Rosen의 이산수학 / Kenneth H. Rosen 저 / 공은배 등저 / 한국맥그로힐(McGraw-Hill KOREA) / 2017년 01월 06일