(Mathematical Induction) 이산수학 (Discrete Mathematics) 3.3 수학적 귀납법 (Mathematical Induction) 2006년 봄학기 문양세 강원대학교 컴퓨터과학과

Introduction 3.3 Mathematical Induction A powerful technique for proving that a predicate P(n) is true for every natural number n, no matter how large. (모든 자연수 n에 대해서 P(n)이 true임을 보일 수 있는 매우 유용한 방법임) Essentially a “domino effect” principle. (앞에 것이 성립하면(넘어지면), 바로 다음 것도 성립한다(넘어진다.) Based on a predicate-logic inference rule: P(0) n0 (P(n)P(n+1)) n0 P(n) P(0)가 true이고, P(n)이 true라 가정했을 때 P(n+1)이 true이면, 모든 n에 대해 P(n)이 true이다.

Intuitively, we can prove that induction is correct. Validity of Induction 3.3 Mathematical Induction Intuitively, we can prove that induction is correct. P(1) = T since (P(0) = T)  (P(0)P(1) = T) P(2) = T since (P(1) = T)  (P(1)P(2) = T) P(3) = T since (P(2) = T)  (P(2)P(3) = T) … P(n) = T since (P(n-1) = T)  (P(n-1)P(n) = T)

Outline of an Inductive Proof 3.3 Mathematical Induction Want to prove n P(n)… E.g. use a direct proof: Induction basis (or base case): Prove P(0). (기본 단계) Induction step: Prove n P(n)P(n+1). (귀납적 단계) Let nN, assume P(n). (induction hypothesis) Under this assumption, prove P(n+1). Inductive inference rule then gives n P(n). Can also be used to prove nc P(n) for a given constant cZ, where maybe c0. (Base로 0이 아닌 상수 c를 사용할 수 있다.) In this circumstance, the base case is to prove P(c) rather than P(0), and the inductive step is to prove nc (P(n)P(n+1)).

By induction hypothesis P(n) Induction Examples (1/4) 3.3 Mathematical Induction Prove that the sum of the first n odd positive integers is n2. That is, prove: (처음 n개 홀수의 합은 n2와 동일하다.) Proof by Induction Induction basis: Let n=1. Since 1 = 12, P(1) is true. Induction step: Let n1, assume P(n), and prove P(n+1). P(n) By induction hypothesis P(n)

Induction Examples (2/4) 3.3 Mathematical Induction Prove that n>0, n<2n. Let P(n)=(n<2n) : Induction basis: P(1) = (1 < 21) = (1 < 2) = T. Induction step: For n>0, prove P(n)P(n+1). Assuming n<2n, prove n+1 < 2n+1. Note n + 1 < 2n + 1 (by inductive hypothesis) < 2n + 2n (because 1 < 2=2∙20  2∙2n-1= 2n) = 2n+1 So n + 1 < 2n+1, and we’re done.

Induction Examples (3/4) 3.3 Mathematical Induction Prove that the sum of the first n positive integers is n(n+1)/2. Let P(n) = Induction basis: Let P(1) = Induction step: Let n1, assume P(n), and prove P(n+1).

Induction Examples (4/4) 3.3 Mathematical Induction Prove when n2. Induction basis: n = 2, Induction step: Assume P(n), and prove P(n+1).

Second Principle of Induction (강 귀납법) 3.3 Mathematical Induction Characterized by another inference rule: P(0) n0: (0kn P(k))  P(n+1) n0: P(n) Difference with 1st principle is that the inductive step uses the fact that P(k) is true for all smaller k<n+1, not just for k=n. (Induction step에서 k=n인 경우 대신에, k<n+1인 모든 k에 대해 P(k)가 true라 가정한다.) P(0)가 true이고, P(0),…,P(n)이 모두 true라 가정했을 때 P(n+1)이 true이면, 모든 n에 대해 P(n)이 true이다.

Examples of Second Principle (1/2) 3.3 Mathematical Induction Show that every n>1 can be written as a product p1p2…ps of some series of s prime numbers. Let P(n)=“n has that property” (모든 양의 정수는 소수의 곱으로 나타낼 수 있다.) Induction basis: n=2, let s=1, p1=2. Thus, P(2) = T. Induction step: Let n2. Assume  2kn: P(k). Consider n+1. If prime, let s=1, p1=n+1. Done. Else n+1=ab, where 1<an and 1<bn. Then a=p1p2…pt and b=q1q2…qu. Then n+1= p1p2…pt q1q2…qu, a product of s=t+u primes.

Examples of Second Principle (2/2) 3.3 Mathematical Induction Prove that every amount of postage of 12 cents or more can be formed using just 4-cent and 5-cent stamps.” (12센트 이상의 우표는 4센트 혹은 5센트 우표만을 사용하여 구성할 수 있다.) Induction basis: 12=3(4), 13=2(4)+1(5), 14=1(4)+2(5), 15=3(5), so 12n15, P(n). Induction step: Let n15, assume 12kn P(k). Stamps for (n+1) cents = stamps for (n3) cents + 4-cent stamp Stamps for (n+1) cents = some 4-cent or 5-cent stamps + 4-cent stamp By Induction Hypothesis