수열

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

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

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

5. 수열의 곱6. 생성함수7. 수열의 극한8. 외부 링크

1. 일반항 정의

수열(數列, sequence)은 정의역이 자연수이고 공역이 수[1]인 열, 즉 함수의 일종을 의미한다. 보통 아래와 같이 정의역이 1일 때의 함숫값부터 나열한다. 고등학교에서는 주로 [math(a:\N\to\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씩 계속 곱해간다. 이렇듯 수열 중에서는 규칙이 손쉽게 보이는 것도 있지만, 그 규칙이 복잡하여 잘 보이지 않는 경우도 있다.

수열을 이루는 각 수를 항(項, element)이라고 한다. 예를 들어 [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. 수열의 귀납적 정의

자세한 내용은 수열의 귀납적 정의 문서

#!if (문단 == null) == (앵커 == null)
를

#!if 문단 != null & 앵커 == null
의 [[수열의 귀납적 정의#s-|]]번 문단을

#!if 문단 == null & 앵커 != null
의 [[수열의 귀납적 정의#|]] 부분을

참고하십시오.

4. 수열의 합

수와 연산 Numbers and Operations
{{{#!wiki style="margin: 0 -10px -5px; min-height: calc(1.5em + 5px)" {{{#!folding [ 펼치기 · 접기 ] {{{#!wiki style="margin: -5px -1px -11px"	<colbgcolor=#765432> 수 체계	자연수(수학적 귀납법 · 홀수 · 짝수 · 소수 · 합성수) · 정수 · 유리수(정수가 아닌 유리수) · 실수(무리수 · 초월수) · 복소수(허수) · 사원수 · 팔원수
표현	숫자(아라비아 숫자 · 로마 숫자 · 그리스 숫자) · 기수법(자연어 수 표기법 · 과학적 표기법 · E 표기법 · 커누스 윗화살표 표기법 · 콘웨이 연쇄 화살표 표기법 · BEAF · 버드 배열 표기법) · 진법(십진법 · 이진법 · 8진법 · 12진법 · 16진법 · 60진법) · 분수(분모 · 분자 · 기약분수 · 번분수 · 연분수 · 통분 · 약분) · 소수{유한소수 · 무한소수(순환소수 · 비순환소수)} · 환원 불능 · 미지수 · 변수 · 상수
연산	사칙연산(덧셈_{([math(Sigma)])} · 뺄셈 · 곱셈_{(구구단 · [math(Pi)])} · 나눗셈) · 역수 · 절댓값 · 제곱근(이중근호) · 거듭제곱 · 로그(상용로그 · 자연로그 · 이진로그) · 역산 · 검산 · 연산자 · 교환자 · 계승
	방식	암산(방식) · 세로셈법 · 주판 · 산가지 · 네이피어 계산봉 · 계산기 · 계산자
용어	이항연산(표기법) · 항등원과 역원 · 교환법칙 · 결합법칙 · 분배법칙
기타	수에 관련된 사항(0과 1 사이의 수 · 음수 · 작은 수 · 큰 수) · 혼합 계산(48÷2(9+3) · 111+1×2=224 · 2+2×2) · 0으로 나누기(바퀴 이론) · 0의 0제곱		}}}}}}}}}

이제 수열 [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]
[math( \displaystyle \sum_{\emptyset} a_k = 0)][3]

수열 합의 성질을 잘 보면 적분의 일반적인 성질과 일치한다. 수열이 함수의 일부이고 수열의 합(부분합)이 함수의 정적분에 대응하기 때문이다. 수열 합은 이산 변수, 함수의 정적분은 연속 변수에 해당하므로 부분합과 정적분은 변수의 종류만 다르고 형태가 같다.

위를 종합하여 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. 자연수 거듭제곱 꼴의 합

자세한 내용은 파울하버의 공식 문서

#!if (문단 == null) == (앵커 == null)
를

#!if 문단 != null & 앵커 == null
의 [[파울하버의 공식#s-|]]번 문단을

#!if 문단 == null & 앵커 != null
의 [[파울하버의 공식#|]] 부분을

참고하십시오.
다음은 외워두면 편리하다.

[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{1}{3}n(4n^2-1) \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. 수열의 곱

자세한 내용은 곱의 기호 문서

#!if (문단 == null) == (앵커 == null)
를

#!if 문단 != null & 앵커 == null
의 [[곱의 기호#s-|]]번 문단을

#!if 문단 == null & 앵커 != null
의 [[곱의 기호#|]] 부분을

참고하십시오.
수열의 합을 [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. 생성함수

자세한 내용은 생성함수 문서

#!if (문단 == null) == (앵커 == null)
를

#!if 문단 != null & 앵커 == null
의 [[생성함수#s-|]]번 문단을

#!if 문단 == null & 앵커 != null
의 [[생성함수#|]] 부분을

참고하십시오.

수열 [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. 수열의 극한

자세한 내용은 수열의 극한 문서

#!if (문단 == null) == (앵커 == null)
를

#!if 문단 != null & 앵커 == null
의 [[수열의 극한#s-|]]번 문단을

#!if 문단 == null & 앵커 != null
의 [[수열의 극한#|]] 부분을