Outline
수학적 귀납법
이항 정리
수학적 귀납법
정렬성의 원리 : 공집합이 아니고 음이 아닌 정수들을 원소로 갖는 모든 집합 S는 최소 원소를 가진다. 즉, S는 S에 속하는 모든 $b$에 대해 $a<=b$를 만족하는 $a$를 가진다.
유한 귀납법의 기본 원리 : 양의 정수들로 이루어진 집합 $S$가 다음 두 가지 성질을 만족한다고 하자.
(a) 정수 1은 $S$에 속한다.
(b) 정수 k가 $S$에 속하면, 다음 정수 k+1도 $S$에 속한다.
그러면 $S$는 모든 양의 정수를 가진다.
pf)
$S$에 속하지 않은 양의 정수 집합이 $T$이고 공집합이 아니라 가정하자.
정렬성의 원리에 의해 $T$는 최소 원소 $a$를 포함한다. 1이 $S$에 속하므로 $a>1$이다.
$a$가 $T$의 최소 원소이므로 $T$는 $a-1$을 가지지 않는다. 즉 $a-1$은 $S$에 속한다.
$S$는 정의에 따라 $(a-1)+1$을 포함하며 이는 모순이다.
유한 귀납법에서
(a)는 basis for the induction
(b)는 induction step
(b)를 수행하며 만들어지는 가정을 induction hypothesis라 부른다.
이항 정리
$$\binom{n}{k} = \frac{n!}{k!(n-k)!}$$
$$\binom{n}{k} = \frac{n(n-1)\cdots (k+1)} {(n-k)!} = \frac{n(n-1)\cdots (n-k+1)}{k!}$$
Pascal's rule
$$\binom{n}{k} + \binom{n}{k-1} = \binom{n+1}{k}$$
$$(a+b)^n = \binom{n}{0}a^n+\binom{n}{1}a^{n-1}b+\cdots|\binom{n}{n-1}ab^{n-1}+\binom{n}{n}b^n$$
여러가지 특징
$$\binom{n}{k}\binom{k}{r} = \binom{n}{r} \binom{n-r}{k-r} \ \ \ \ n\geq k\geq r\geq 0$$
$$\binom{n}{k} = \frac{n-k+1}{k} \binom{n}{k-1} \ \ \ \ n\geq k\geq 1$$
$2\leq k \leq n-2$일 때,
$$\binom{n}{k}=\binom{n-2}{k-2}+2\binom{n-2}{k-1}+\binom{n-2}{k} \ \ \ \ n\geq 4$$
$n\leq 1$일 때,
$$\sum_{i=0}^{n} \binom{n}{i}=2^n$$
$$\sum_{i=0}^{n} (-1)^i\binom{n}{i}=0$$
$$\sum_{i=0}^{n} i\binom{n}{i} = n2^{n-1}$$
$$\sum_{i=0}^{n} 2^i\binom{n}{i}=3^n$$
$$\binom{n}{0}+\binom{n}{2}+\cdots = \binom{n}{1}+\binom{n}{3}+\cdots = 2^{n-1}$$
$$\sum_{i=0}^{n} (-1)^i\frac{1}{1+i}\binom{n}{i}=\frac{1}{n+1}$$
$$\binom{2n}{n}=\frac{\prod_{i=1}^{n} 2i-1}{\prod_{i=1}^{n} 2i}2^{2n}$$
$n\leq 2$일 때,
$$\sum_{i=2}^{n}\binom{i}{2}=\binom{n+1}{3}$$
$$\sum_{i=1}^{n}\binom{2i}{2}=\frac{n(n+1)(4n-1)}{6}$$
$$\sum_{i=1}^{n} (2i-1)^2 = \binom{2n+1}{3}$$
$n>1$일 때,
$$2^n<\binom{2n}{n} <2^{2n}$$
카탈란 수
$$C_n = \frac{1}{n+1} \binom{2n}{n} =\frac{(2n)!}{n!(n+1)!}$$
$$C_n = \frac{2(2n-1)}{n+1} C_{n-1}$$
'<Elementary Number Theory>, David M. Burton저'를 기반하여 개인 공부 목적으로 작성되었습니다.
오타가 및 오류가 있을 수 있으며, 문제가 될 시 삭제될 수 있습니다.