합, 수열, 귀납법 · Topos Uranos

요약

이 수업은 합의 기호와 그 성질(선형성, 분해, 첨자의 이동, 순서의 반전)을 도입하고, 이를 망원 합의 계산과 등차수열 및 등비수열의 합의 계산에 적용한다. 이어서 강한 귀납법과 정렬성 원리를 다루고, 귀납법이 이 둘을 함의함을 증명하며, 이들이 어떤 의미에서 귀납법과 동치인지 밝히고, 이를 이용하여 $1$ 보다 큰 모든 자연수가 소수의 곱임을 증명한다.

학습 목표

합의 기호로 합을 쓰고 변형하며, 그때 선형성, 분해, 첨자의 이동, 순서의 반전이라는 성질을 적용한다.
망원 합을 계산하고, 이를 이용하여 합의 공식을 확인하는 데 그치지 않고 이끌어 낸다.
등차수열이나 등비수열의 일반항과 처음 몇 항의 합을 구하고, 이를 문제 해결에 적용한다.
강한 귀납법과 정렬성 원리로 증명하고, 이 둘을 귀납법의 원리로부터 이끌어 내며, 정렬성 원리가 어떤 추가 사실과 함께 귀납법을 되찾게 해 주는지 설명한다.

합의 기호

페아노 공리에 관한 수업에서 어떤 규칙을 따르는 많은 항의 합, 예컨대 $1 + 2 + \cdots + n$ 같은 합이 나왔다. 말줄임표는 그 규칙을 짐작하는 일을 독자에게 맡긴다. 합의 기호는 그 규칙을 명시한다. $a_m, a_{m + 1}, \ldots, a_n$ 같은 수들이 주어지고 $m \leq n$ 일 때, 다음과 같이 쓴다.

\sum_{k=m}^{n} a_k = a_m + a_{m + 1} + \cdots + a_n

그리고 ' $a_k$ 의, $k$ 에 대하여 $m$ 부터 $n$ 까지의 합'이라고 읽는다. 문자 $k$ 같은 것을 합의 첨자라 하고, $m$ 및 $n$ 각각을 아래끝과 위끝, $a_k$ 같은 항을 일반항이라 한다. 이 합의 항의 개수는 $n - m + 1$ 개다. 첨자는 묶인 변수다. 합의 값은 첨자를 어떤 문자로 나타내는지에 의존하지 않으므로 $\sum_{k=1}^{n} k^2$ 및 $\sum_{j=1}^{n} j^2$ 두 식은 같은 수다. 첨자는 자연수를 움직이지만, 항은 다른 종류의 수여도 된다. 이 수업에는 자연수 말고도 음수를 포함한 정수와 분수가 나오는데, 이들은 다음 단원에서 구성된다. 여기서는 이를 미리 사용하며, 그 계산과 순서에 관한 기초 규칙(교환법칙, 결합법칙, 분배법칙, 부호 규칙, 뺄셈, 영이 아닌 수로의 나눗셈)만 쓴다. 아래의 합의 성질들은 이 규칙들로 증명되므로, 이 가운데 어느 종류의 수를 항으로 하더라도 성립한다.

자연수의 연산에 관한 수업의 덧셈, 곱셈, 거듭제곱과 마찬가지로, 합도 말줄임표 없이 재귀적 정의를 할 수 있다. 항이 하나뿐인 합은 그 항 자신이고, 항을 하나 덧붙이려면 그 항을 앞의 결과에 더한다.

\sum_{k=m}^{m} a_k = a_m, \qquad \sum_{k=m}^{n + 1} a_k = \sum_{k=m}^{n} a_k + a_{n + 1}

이 정의는 $m$ 에서 시작하지만, 재귀 정리는 진술된 형태대로라면 $1$ 에서부터 함수를 정의한다. 그러나 첨자를 옮기기만 하면 된다. $n$ 까지의 합 대신, 처음 $q$ 개 항의 합( $a_m$ 에서 시작하는 것)을 정의한다. 초깃값 $a_m$ 및 규칙 $g_q(x) = x + a_{m + q}$ 에 의해, 재귀 정리는 유일한 함수 $F$ ( $\mathbb{N}$ 에서 수로의 함수)을 주는데, 이 함수에서는 $F(1) = a_m$ 및 $F(q + 1) = F(q) + a_{m + q}$ 두 식이 모든 자연수 $q$ 에 대하여 성립한다. 그러면 $n \geq m$ 일 때, $n$ 까지의 합을 $F$ 함수의 값, 즉 그 항의 개수 $n - m + 1$ 에서의 값으로 정의한다. 이 개수는 자연수인데, $m < n + 1$ 이기 때문이다.

\sum_{k=m}^{n} a_k = F(n - m + 1)

$n = m$ 일 때 $F(1) = a_m$ 식을 얻고, $q = n - m + 1$ 일 때는 $m + q = n + 1$ 이므로 등식 $F(q + 1) = F(q) + a_{m + q}$ 식은 정확히 정의의 둘째 규칙이 된다. 따라서 $m$ 에서 시작하는 재귀적 정의는 각 $n \geq m$ 에 대하여 유일한 합을 정하며, $m = 1$ 일 때는 재귀 정리가 직접 주는 합과 일치한다. 그때 $F(n) = \sum_{k=1}^{n} a_k$ 식이 성립하기 때문이다.

이 기호를 쓰면, 페아노 공리에 관한 수업에서 귀납법으로 증명한 공식, 즉 처음 $n$ 개 자연수의 합의 공식은 다음과 같이 쓴다.

\sum_{k=1}^{n} k = \frac{n(n + 1)}{2}

제곱의 합 $\sum_{k=1}^{n} k^2$ 식이 다음 단계이며, 이 수업은 그것을 확인하는 데 그치지 않는다. 망원 합에 관한 절에서 그것을 미리 알지 못한 채 이끌어 낸다.

합의 위끝에 관한 귀납법은 아래끝 $m$ 에서 시작하며, 그 값이 꼭 $1$ 일 필요는 없다. 그러나 페아노 공리의 귀납법의 원리는 $1$ 에서 시작한다. 다른 자연수에서 시작하려면 다음 보조정리가 필요하다.

보조정리임의의 자연수에서 시작하는 귀납법

자연수 $n_0$ 하나가 주어졌다고 하자. 어떤 성질이 $n_0$ 에 대하여 성립하고, 임의의 자연수 $k \geq n_0$ 에 대하여 성립한다고 인정하면 $k + 1$ 에 대해서도 성립한다면, 그 성질은 모든 자연수 $n \geq n_0$ 에 대하여 성립한다. 착안점은 자연수를 $n_0$ 에서부터 다시 번호 매겨 통상의 귀납법의 원리로 돌아가는 것이다. 자연수의 연산에 관한 수업의 보조정리, 곧 $1$ 과 다른 모든 자연수는 후자라는 보조정리와 덧셈의 단조성을 쓴다. 그림에서는 $n_0 = 4$ 및 $p = 3$ 값이며, $n_0$ 부터 각 자연수 아래에 그 새 번호 $q$ 값이 적혀 있다.

증명

$n_0 = p + 1, \quad Q(q) \leftrightarrow P(p + q)$
$n_0 = 1$ 이면 이는 귀납법의 원리 그 자체다. 그렇지 않으면 $n_0 = p + 1$ 식을 만족하는 자연수 $p$ 값이 있으며, $Q$ 성질을 생각한다. 이 성질은 $P$ 성질을 $p + q$ 에 대하여 주장한다.
$Q(1) \leftrightarrow P(\resaltar{p + 1}) \leftrightarrow P(\resaltar{n_0})$
$Q$ 성질은 $1$ 에 대하여 성립한다. $Q(1)$ 식은 곧 $P(n_0)$ 식이기 때문이다.
$P(p + q) \rightarrow P(\resaltar{(p + q) + 1}) = P(\resaltar{p + (q + 1)})$
$Q(q)$ 성질이 성립하면, $1 \leq q$ 이므로 덧셈의 단조성에 의해 $p + q \geq p + 1 = n_0$ 관계가 성립하고, 주어진 단계를 $k = p + q$ 에 적용할 수 있다. 따라서 $Q(q + 1)$ 성질이 성립한다.
$n \geq n_0 \rightarrow (\exists q \in \mathbb{N})(n = p + q)$
귀납법의 원리에 의해 $Q(q)$ 성질은 모든 $q$ 에 대하여 성립한다. 모든 $n \geq n_0$ 수는 $p + q$ 꼴이다. $n = n_0$ 이면 $q = 1$ 으로 하고, $n = n_0 + l$ 이면 $q = 1 + l$ 로 하면 된다.

합의 성질

재귀적 정의로부터 위끝에 관한 귀납법으로 다음 성질들이 이끌어진다. 이 성질들은 임의의 항 $a_k$ 및 $b_k$ 와 임의의 수 $c$ 에 대하여 성립한다.

선형성: $\sum_{k=m}^{n} (a_k + b_k) = \sum_{k=m}^{n} a_k + \sum_{k=m}^{n} b_k$ 및 $\sum_{k=m}^{n} c\,a_k = c \sum_{k=m}^{n} a_k$ . 특히 상수를 $n$ 번 더하는 것은 그 상수에 $n$ 값을 곱하는 것이다: $\sum_{k=1}^{n} c = nc$ .
분해: $m \leq p < n$ 이면 $\sum_{k=m}^{n} a_k = \sum_{k=m}^{p} a_k + \sum_{k=p+1}^{n} a_k$ .
첨자의 이동: 모든 자연수 $p$ 에 대하여 $\sum_{k=m}^{n} a_k = \sum_{j=m+p}^{n+p} a_{j - p}$ .
순서의 반전: $\sum_{k=1}^{n} a_k = \sum_{j=1}^{n} a_{n + 1 - j}$ .

정리합의 성질

임의의 항 $a_k$ 및 $b_k$ 와 임의의 수 $c$ 에 대하여, 합은 선형이고, 연속된 두 합으로 분해되며, 첨자의 이동과 순서의 반전을 허용한다. 그 의미는 앞의 목록과 같다. 각 성질은 위끝에 관한 귀납법으로 증명되며, 그 귀납법은 앞의 보조정리 덕분에 아래끝에서 시작한다. 재귀적 정의와 덧셈 및 곱셈의 성질만 쓰며, 순서의 반전은 그 밖에 분해와 이동에도 기댄다.

증명

$\sum_{k=m}^{n + 1} (a_k + b_k) = \resaltar{\sum_{k=m}^{n} a_k + \sum_{k=m}^{n} b_k} + (a_{n + 1} + b_{n + 1}) = \sum_{k=m}^{n + 1} a_k + \sum_{k=m}^{n + 1} b_k$
선형성. $n = m$ 일 때 양변은 모두 $a_m + b_m$ 값이다. $n$ 에 대하여 성립하면 재귀적 정의, 귀납 가정, 덧셈의 결합법칙과 교환법칙을 적용한다. 같은 방법으로 분배법칙을 써서 $\sum_{k=m}^{n} c\,a_k = c \sum_{k=m}^{n} a_k$ 식이 증명되고, 또 $\sum_{k=1}^{n} c = nc$ 식도 증명된다. $nc + c = (n + 1)c$ 이기 때문이다.
$\sum_{k=m}^{p + 1} a_k = \sum_{k=m}^{p} a_k + \resaltar{a_{p + 1}} = \sum_{k=m}^{p} a_k + \resaltar{\sum_{k=p+1}^{p + 1} a_k}$
분해. $p$ 값을 고정하고 $n$ 에 관하여 $p + 1$ 부터 귀납법을 쓴다. $n = p + 1$ 일 때는 재귀적 정의 그 자체다. 항이 하나뿐인 합은 그 항 자신이기 때문이다.
$\sum_{k=m}^{n + 1} a_k = \resaltar{\sum_{k=m}^{p} a_k + \sum_{k=p+1}^{n} a_k} + a_{n + 1} = \dato{d}{\sum_{k=m}^{p} a_k + \sum_{k=p+1}^{n + 1} a_k}$
분해가 $n$ 에 대하여 성립하면, 양변에 $a_{n + 1}$ 항을 더하고 각 합에 재귀적 정의를 적용한다.
$\sum_{j=m+p}^{n+1+p} a_{j - p} = \resaltar{\sum_{j=m+p}^{n+p} a_{j - p}} + a_{n + 1} = \resaltar{\sum_{k=m}^{n} a_k} + a_{n + 1} = \dato{s}{\sum_{k=m}^{n + 1} a_k}$
이동. $n = m$ 일 때 양변은 모두 $a_m$ 값이다. $n$ 에 대하여 성립하면, 위끝 $(n + p) + 1$ 식은 $(n + 1) + p$ 식과 같으므로 재귀적 정의와 귀납 가정을 적용한다.
$\sum_{j=1}^{n + 1} a_{n + 2 - j} = a_{n + 1} + \resaltar{\sum_{j=2}^{n + 1} a_{n + 2 - j}} = a_{n + 1} + \resaltar{\sum_{i=1}^{n} a_{n + 1 - i}}$
순서의 반전. $n$ 에 관한 귀납법으로 증명한다. $n = 1$ 일 때 양변은 모두 $a_1$ 값이다. $n$ 에 대하여 성립하면, 항이 $n + 1$ 개인 반전된 합에서 분해로 첫 항을 떼어 내고, 첨자를 하나 이동한다. 이때 $j = i + 1$ 으로 둔다.
$a_{n + 1} + \resaltar{\sum_{i=1}^{n} a_{n + 1 - i}} = a_{n + 1} + \resaltar{\sum_{k=1}^{n} a_k} = \sum_{k=1}^{n + 1} a_k$
귀납 가정에 의해 마지막 합은 $\sum_{k=1}^{n} a_k$ 값과 같다. 교환법칙과 재귀적 정의에 의해 $n + 1$ 에 대한 순서의 반전을 얻는다.

선형성을 쓰면 복잡한 합을 이미 아는 합으로 바꿀 수 있다. 마지막 두 성질은 변수의 치환이다. 이동은 $k = j - p$ 식으로 놓고 같은 항들을 다른 번호로 훑으며, 반전은 $k = n + 1 - j$ 식으로 놓고 그것들을 마지막 항에서 첫 항으로 훑는다. 그러나 합은 곱에 대해서는 같은 방식으로 움직이지 않는다. 곱의 합은 합의 곱이 아니다. 두 항과 $a_k = b_k = k$ 식의 예 하나로 충분하다.

\sum_{k=1}^{2} k \cdot k = 1 + 4 = 5 \neq 9 = (1 + 2)(1 + 2)

명제처음 몇 홀수의 합

처음 $n$ 개 홀수의 합이 $n^2$ 값임을 증명하여라. 선형성으로 이 합을 이미 아는 두 합으로 바꾸므로 새로운 귀납법은 필요 없다.

증명

$1 + 3 + 5 + \cdots + (2n - 1) = \dato{s}{\sum_{k=1}^{n} (2k - 1)}$
$k$ 번째 홀수는 $2k - 1$ 수다. 첫째는 $1$ , 둘째는 $3$ , $n$ 번째는 $2n - 1$ 수다. 구하는 합은 다음과 같이 쓴다.
$\sum_{k=1}^{n} \resaltar{(2k - 1)} = \resaltar{2 \sum_{k=1}^{n} k - \sum_{k=1}^{n} 1}$
선형성에 의해 합은 둘로 나뉜다. 각 $k$ 값의 합의 두 배에서, 하나를 $n$ 번 더한 합을 뺀 것이다.
$2 \resaltar{\sum_{k=1}^{n} k} - \resaltar{\sum_{k=1}^{n} 1} = \resaltar{n(n + 1)} - \resaltar{n}$
첫째 합은 처음 $n$ 개 자연수의 합 $\frac{n(n + 1)}{2}$ 식이고, 인수 $2$ 값이 그 분모를 약분한다. 둘째 합은 $n$ 번에 걸쳐 수 $1$ 값을 더한 것이다.
$\resaltar{n(n + 1)} - n = \resaltar{n^2 + n} - n = n^2$
곱을 전개한다. 항 $n$ 및 $-n$ 항은 서로 지워진다.
$k^2 - (k - 1)^2 = 2k - 1$
그림이 그 까닭을 보여 준다. 각 홀수는 연속된 두 제곱수의 차, 곧 한 변이 $k - 1$ 인 정사각형을 한 변이 $k$ 인 정사각형으로 바꾸는 ㄱ자 모양의 부분이다.