PROOF 61
증명하라.
이항정리
실수 ℝ 위에서.
한 줄씩, 이유를 따라가 봅시다
먼저 이미 주어진 것과 앞으로 보여야 할 것을 나누어 읽어 보세요. 다음 줄로 넘어갈 때마다 어떤 정의나 앞의 결과를 사용했는지 묻습니다. 연결이 보이지 않으면 결론을 외우기보다 그 전제로 잠시 돌아가도 좋습니다.
정의 D1
(a+b)ⁿ 은 (a+b) 를 n 개 곱한 것을 뜻한다.
증명.
(1)(a+b)¹ = a + b약속
(2)(a+b)^(k+1) = (a+b)ᵏ (a+b)약속
∎
정의 D2
원소가 n 개인 집합의 k 원소 부분집합의 개수를 nCk 라 한다.
증명.
부분집합에는 자리가 없다. 원소가 무엇인지만이 부분집합을 정한다.약속
∎
정의 D3
n 개의 자리 1, …, n 의 각 자리에 a 와 b 중 하나를 정한 것을 길이 n 의 택 f 라 하고, 정한 것들의 곱을 T(f) = f(1)f(2)⋯f(n) 이라 한다.
증명.
(1)자리 i 는 (a+b)ⁿ 의 i 번째 인수에 해당한다.약속, D1
(2)두 택이 어느 한 자리에서라도 다르면 서로 다른 택이다.약속
∎
보조정리 L1
모든 자연수 n 에 대하여 (a+b)ⁿ 은 길이 n 인 모든 택 f 의 곱 T(f) 를 더한 것과 같다.
증명.
(1)길이 1 의 택은 a 를 고른 것과 b 를 고른 것뿐이다.D3
(2)그 곱의 합은 a + b 이고 (a+b)¹ = a + b 이므로 P(1) 이다.(1), D1
(3)P(k) 라 하자. 즉 (a+b)ᵏ = ΣT(f) 이며 합은 길이 k 의 택 전체에 대한 것이다.가정
(4)(a+b)^(k+1) = (a+b)ᵏ (a+b)D1
(5) = (ΣT(f))(a+b)(3), (4), E
(6) = Σ T(f)(a+b)(5), A1, A4
(7) = Σ (T(f)a + T(f)b)(6), A1
(8)T(f)a 는 f 의 뒤에 마지막 자리로 a 를 붙인 길이 k+1 의 택의 곱이고, T(f)b 는 b 를 붙인 것의 곱이다.(7), D3, A3
(9)길이 k+1 의 택은 앞의 k 자리와 마지막 자리로 꼭 한 번씩 이렇게 나타나므로 (7) 의 합은 그 택 전체에 대한 합이다. 즉 P(k+1) 이다.(7), (8), A4, A5
(10)P(1) 이고 P(k) ⟹ P(k+1) 이므로 모든 n 에 대하여 성립한다.(2), (9), A6
∎
보조정리 L2
길이 n 의 택 가운데 b 를 정확히 k 번 고른 것은 nCk 개이며, 그 곱은 모두 aⁿ⁻ᵏbᵏ 이다.
증명.
(1)택 f 에 집합 B(f) = {i : f(i) = b} 를 대응시킨다.D3
(2)두 택이 다르면 어느 자리에서 다르므로 B(f) 도 다르다.(1), D3
(3)거꾸로 {1, …, n} 의 부분집합 B 마다 그 자리에만 b 를 고른 택이 있다.(1), D3
(4)그러므로 f ↦ B(f) 는 부분집합 전체로 가는 전단사다.(2), (3)
(5)b 를 정확히 k 번 고른 택은 |B(f)| = k 인 것이고, 그 개수는 k 원소 부분집합의 개수 nCk 다.(4), A7, D2
(6)그러한 택의 곱은 a 를 n−k 개, b 를 k 개 곱한 것이므로 순서를 바꾸어 aⁿ⁻ᵏbᵏ(5), D3, A2, A3
∎
정리 T1
(a+b)ⁿ = nC0 aⁿ + nC1 aⁿ⁻¹b + ⋯ + nCn bⁿ
증명.
(1)(a+b)ⁿ 은 길이 n 인 모든 택의 곱의 합이다.L1
(2)각 택은 b 를 고른 횟수 k 가 0 부터 n 까지 가운데 하나로 정해지므로 꼭 한 무리에 속한다.D3
(3)k 무리의 항은 모두 aⁿ⁻ᵏbᵏ 이고 그 개수는 nCk 다.(2), L2
(4)같은 것을 nCk 번 더하면 nCk · aⁿ⁻ᵏbᵏ(3), A9
(5)합을 무리별로 모으면 (a+b)ⁿ = Σ nCk aⁿ⁻ᵏbᵏ (k = 0, …, n)(1), (2), (4), A4, A5
∎
따름정리 C
1 ≤ k ≤ n 인 k 에 대하여 nCk + nC(k−1) = (n+1)Ck
증명.
(1)원소가 n+1 개인 집합 X 에서 원소 x 를 하나 고정한다.가정
(2)X 의 k 원소 부분집합을 x 를 포함하지 않는 것과 포함하는 것으로 나눈다. 두 모임은 배반이고 합하면 전체다.(1), D2
(3)x 를 포함하지 않는 것은 나머지 n 개의 k 원소 부분집합이므로 nCk 개다.(2), D2
(4)x 를 포함하는 것은 S ↦ S∖{x} 로 나머지 n 개의 k−1 원소 부분집합과 전단사이므로 nC(k−1) 개다.(2), A7, D2
(5)nCk + nC(k−1) = (n+1)Ck(3), (4), A8, D2
(6)(a+b)ⁿ 의 계수가 nCk 이므로, 이 관계는 계수들 사이의 관계이기도 하다. 파스칼 삼각형의 각 수가 위의 두 수의 합인 것이 (5) 다.(5), T1
∎
비고
A1 은 이 증명에서 제거할 수 있는가.
이 편에는 대수의 줄과 세는 줄이 섞여 있다. 제거하면 어느 쪽이 남는지 확인하라.