수열

이산수학 Discrete Mathematics
{{{#!wiki style="margin: 0 -10px -5px; min-height: calc(1.5em + 5px)" {{{#!folding [ 펼치기 · 접기 ] {{{#!wiki style="margin: -5px -1px -11px; word-break: keep-all"	이론
<colbgcolor=#3CC> 기본 대상	수학기초론(수리논리학 · 집합론) · 수열 · 조합 · 알고리즘 · 확률
다루는 대상과 주요 토픽
수열	등차수열(뛰어 세기) · 등비수열 · 계차수열 · 조화수열 · 귀납적 정의(점화식) · 급수 · 규칙과 대응 · 규칙 찾기 · 피보나치 수열 · 읽고 말하기 수열 · 생성함수
조합	경우의 수(/공식) · 순열(완전 순열 · 염주 순열) · 치환 · 분할(분할수) · 최단거리 · 제1종 스털링 수 · 제2종 스털링 수 · 카탈랑 수 · 벨 수 · 라흐 수 · 포함·배제의 원리 · 더블 카운팅 · 조합론
그래프	수형도(트리) · 인접행렬 · 마방진 · 마법진 · 한붓그리기(해밀턴 회로) · 쾨니히스베르크 다리 건너기 문제
기타	P-NP 문제^미해결 · 4색정리 · 이항정리(파스칼의 삼각형) · 이산 푸리에 변환 · 비둘기 집의 원리 · 상트페테르부르크의 역설 · 투표의 역설 · 에르고딕 가설^미해결 · 콜라츠 추측^미해결 · 시행착오 (예상과 확인) · 불 논리 · 브라에스 역설
관련 문서	논리학 관련 정보 · 수학 관련 정보 · 컴퓨터 관련 정보 · 틀:수학기초론 · 틀:통계학 · 틀:이론 컴퓨터 과학	}}}}}}}}}

1. 수열의 일반항 정의2. 주요한 수열들3. 수열의 귀납적 정의4. 수열의 합

4.1. 자연수 거듭제곱 꼴의 합4.2. 무리식과 유리식에 대한 합

5. 수열의 곱6. 생성함수7. 수열의 극한8. 기타9. 관련 문서

1. 수열의 일반항 정의

수열(number sequence)은 정의역이 자연수이고 공역이 수[1]인 열, 즉 함수의 일종을 의미하며, 보통 아래와 같이 정의역이 1일 때의 함숫값부터 나열한다. 고등학교에서는 주로 [math(a:\mathbb{N}\to\mathbb{R})]인 함수를 다루지만 간혹 복소수까지 등장하는 경우도 있다.

다음은 두 가지의 수열을 나타낸 것이다.

[math(1 \quad 3 \quad 5 \quad 7 \quad 9\quad 11\quad\cdots)]
[math(1 \quad 2 \quad 4 \quad 8 \quad 16\quad 32\quad\cdots)]

첫 번째 수열의 경우 첫째항 1로부터 2씩 계속 더해가며, 두 번째 수열의 경우 첫째항 1로부터 2씩 계속 곱해간다. 이렇듯 수열 중에서는 규칙이 손쉽게 보이는 것도 있지만, 그 규칙이 복잡하여 잘 보이지 않는 경우도 있다.

수열을 이루는 각 수를 항이라고 한다. 예를 들어 [math(n)]번째 수는 제[math(n)]항인 것이다. 수열을 나타낼 때는 [math(\{a_{n}\})]과 같이 나타낸다. [math(a)]는 수열을 명명하는 문자이며, [math(a_{n})] 자체는 수열 [math(\{a_{n}\})]의 [math(n)]번째 항을 나타내며, 일반항이라 한다.

예를 들어 수열 [math(\{n^2-1\})]은

[math(\begin{aligned} 0\quad3\quad8\quad15\quad24\quad 35 \quad \cdots \end{aligned})]

으로 나타낼 수 있을 것이다.

2. 주요한 수열들

등차수열: 이웃하는 항의 차(공차)가 일정한 수열. 즉, 항의 값이 일차함수와 같이 선형적인 수열
등비수열: 이웃하는 항의 비(공비)가 일정한 수열. 즉, 항의 값이 지수함수와 같이 지수적인 수열
조화수열: 각 항의 역수가 등차수열인 수열
계차수열: 어떤 수열의 이웃한 항 사이의 차로 구성된 수열
특정 함수로 정의되는 수열

다항수열: 다항함수로 정의되는 수열. 수열의 합은 각각의 항에 거듭제곱의 합 공식을 따로따로 적용하여 각 항의 계수를 곱해준다. 정적분과 원리가 다소 비슷하다.
삼각수열: 삼각함수로 정의되는 수열. 수열의 합을 구할 때 항을 몇천 개나 합해야 하는 문제가 나오지만 그건 장식이고 주기가 [math(2{\pi})]임을 이용해서 주기만큼 나눈 나머지에 해당하는 항을 더하면 된다.

부분군열
피보나치 수열: 가장 단순한 이계 동차 선형점화식을 따르는 수열로, 일반항에 황금비가 등장한다.
콜라츠 수열: 유명한 [math(3n+1)]의 문제. 1937년에 나온 수열인데 2024년 기준으로 아직도 수렴하는지 알려지지 않은 난제 중 하나이다.

3. 수열의 귀납적 정의

자세한 내용은 수열의 귀납적 정의 문서 참고하십시오.

4. 수열의 합

이제 수열 [math(\{a_{n} \})]의 [math(n)]항까지의 합을 생각할 수 있고, 그것을 기호로

[math(\begin{aligned} \sum_{k=1}^{n} a_{k} =a_{1}+a_{2}+a_{3}+ \cdots +a_{n} \end{aligned})]

으로 쓴다. 기호 [math(\Sigma)]는 sum이라 읽는데, 대한민국 교육현장 대부분은 원래 그리스 문자의 이름인 sigma로 읽는 경우가 대부분이다. 다음은 합의 기호를 쓸 때 참고할 점들이다.

합의 기호 밑에는 각 항수를 대입할 문자(index)를 지정하고, 더하기를 시작할 첫 항을 지정한다. [math(k)]에 대한 일반항을 첫째 항부터 더할 것이라면, [math(k=1)]이라고 쓰면 된다. 만약 일반항에 여기서 지정한 문자가 아닌 다른 문자가 들어간다면 그 문자는 상수로 취급한다.
합의 기호 위에는 마지막 항을 지정한다. 제[math(n)]항까지 더할 것이라면, [math(n)]이라고 쓰면 된다.
합의 기호 오른쪽에는 일반항을 써준다. 항수가 들어갈 문자는 앞에서 지정한 문자와 같아야 한다. 예를 들어 [math(n)]에 대한 수열에서 일반항이 [math(3n-2)]이고 [math(n)]에 들어가는 수가 항수라면, [math(n)] 대신에 앞에서 지정한 문자로 바꿔 써야 한다.

합의 기호에 대한 일반적인 성질은 다음과 같다.

[math( \displaystyle \sum_{k=1}^{n}\left(a_k \pm b_k\right) = \sum_{k=1}^{n}a_k \pm \sum_{k=1}^{n}b_k)] (복부호동순)
[math( \displaystyle \sum_{k=1}^{n}ca_k = c\sum_{k=1}^{n}a_k)] (단, [math(c)]는 상수)
[math( \displaystyle \sum_{k=1}^{n}c = cn)][2]

위를 종합하여 1부터 100까지의 합은 다음과 같이 나타낼 수 있을 것이다.

[math(\begin{aligned} \sum_{k=1}^{100} k=5050 \end{aligned})]

또한, 첫째 항부터 [math(n)]번째 항까지의 합을 [math(S_{n})]이라 한다면,

[math(\begin{aligned} S_{n}-S_{n-1}=a_{n} \end{aligned})]

이 성립한다.

4.1. 자연수 거듭제곱 꼴의 합

다음은 외워두면 편리하다.

[math(\displaystyle \sum_{k=1}^{n} k =\dfrac{n(n+1)}{2})]
[math(\displaystyle\sum_{k=1}^{n} k^2 =\dfrac{n(n+1)(2n+1)}{6})]
[math(\displaystyle\sum_{k=1}^{n} k^3 =\biggl\{ \dfrac{n(n+1)}{2} \biggr\}^{2})]

임의의 자연수 [math(m)]에 대해, [math(k^m)]의 합인 [math(\displaystyle \sum_{k=1}^n k^m)]에 대한 공식은 파울하버의 공식이라고 알려져 있다. 자세한 내용은 해당 문서 참고.

위를 이용하여 홀수의 제곱의 합을 구해보자. 홀수는 [math((2n-1))]로 나타낼 수 있으므로 다음과 같다.

[math(\begin{aligned}\displaystyle \sum_{k=1}^{n} (2k-1)^{2}&=\sum_{k=1}^{n} (4k^2-4k+1) \\ &=4\sum_{k=1}^{n}k^2-4\sum_{k=1}^{n}k+\sum_{k=1}^{n} 1 \\&= 4 \cdot \frac{n(n+1)(2n+1)}{6}+4\cdot \frac{n(n+1)}{2}+n \\ &=\frac{n(4n^2-1)}{3} \end{aligned})]

4.2. 무리식과 유리식에 대한 합

무리식 관련

분수꼴로 된 무리식과 관련한 수열의 합을 구할 때는 유리화를 사용한다.

[math(\begin{aligned}\displaystyle \sum_{k=1}^{n} \dfrac{1}{\sqrt{k}+\sqrt{k+1}}&=\sum_{k=1}^{n} \dfrac{\sqrt{k}-\sqrt{k+1}}{(\sqrt{k}+\sqrt{k+1})(\sqrt{k}-\sqrt{k+1})} \\ &=-\sum_{k=1}^{n}(\sqrt{k}-\sqrt{k+1}) \\&=-(1-\sqrt{2}+\sqrt{2}-\sqrt{3}+\sqrt{3}-\cdots+\sqrt{n}-\sqrt{n+1}) \\ &=\sqrt{n+1}-1 \end{aligned})]

유리식 관련

유리식과 관련한 수열의 합을 구할 때는 부분분수 분해

[math(\dfrac{1}{AB}=\dfrac{1}{B-A} \biggl(\dfrac{1}{A}-\dfrac{1}{B} \biggr)\quad)] (단, [math(A \neq 0)], [math(AB \neq 0)])

을 이용한다.

[math(\begin{aligned}\displaystyle \sum_{k=1}^{n} \frac{1}{k(k+1)} &= \sum_{k=1}^{n} \biggl( \frac{1}{k}-\frac{1}{k+1} \biggr) \\&=1-\frac{1}{2}+\frac{1}{2}-\frac{1}{3}+\frac{1}{3}-\cdots+\frac{1}{n}-\frac{1}{n+1} \\&=\frac{n}{n+1} \end{aligned})]

또한 다음을 참고한다.

[math(\begin{aligned}\displaystyle \sum_{k=1}^{n} (\sqrt{k+m}-\sqrt{k})&=\sum_{k=1}^{m}(\sqrt{n+k}-\sqrt{k}) &&\quad (n \geq m) \\ \sum_{k=1}^{n} \biggl(\frac{1}{k}-\frac{1}{k+m} \biggr)&= \sum_{k=1}^{m} \biggl(\frac{1}{k}-\frac{1}{k+n} \biggr) &&\quad (n \geq m)\end{aligned})]

5. 수열의 곱

수열의 합을 [math(\Sigma)]로 나타냈듯이 곱도 [math(\Pi)]로 나타낼 수 있다.

[math(\begin{aligned} \prod_{k=1}^{n}a_{k}=a_{1}a_{2}a_{3} \cdots a_{n} \end{aligned})]

6. 생성함수

자세한 내용은 생성함수 문서 참고하십시오.

수열 [math(\{a_n\})]에 대해 생각하는 형식적인 멱급수

[math(\begin{aligned} \displaystyle A(x) = \sum_{i=0}^{\infty} a_i x^i \end{aligned})]

로 정의된다.

생성함수로 수열의 합을 계산할 수 있다.

[math(\displaystyle \sum_{k=1}^{n} A(k) = \int_{1}^{n} A(k) \ \mathrm{d}\lfloor k \rfloor \quad)] (단, [math(\lfloor k \rfloor)]는 최대 정수 함수)

7. 수열의 극한

자세한 내용은 수열의 극한 문서 참고하십시오.

8. 기타

OEIS라는 온라인 사전 사이트가 있는데, 수학 및 물리학에서 다루는 여러 수열에 대해서 볼 수 있는 사이트이다.

9. 관련 문서

[1] 초등학교 수학 등 기초적인 수준에서는 자연수에서 자연수로 가는 함수를 다루나, 점차 수준이 높아지면서 공역의 수의 범위가 실수 혹은 복소수까지 확장된다.[2] [math(c)]가 아님에 유의

수열