[ 이산 수학 ] 8. 수학적 귀납

귀납법

 

 

 

수학적 귀납법의 논리

1. n = 1 일때 p(1)이 참임을 보임  (Basic Step)
2. n = k 일때 p(k)이 참임을 가정  (Inductive Step - 1)  Assume)
3. n = k+1 일 때 p(k+1)이 참임을 보임  (Inductive Step - 2) get result)

 

ex) 무한의 사다리타기

1. 우리가 0번 째 반판에서 >  첫 번째 발판에 도달 가능.

2. 그럼 우리가 N번째 발판에 도달했다면 > N+1번째 발판에도 도달 가능하다!

 

P(1) is true , then P(a) → P(a+1) 

 

 

Validity of Mathematical Induction 

: 그냥 귀납법이 성립하면 반례는 나오지 않을 것이라는 ,

중간에 " 이거 아닌 거 있는데요? " 이거 안 된다는 내용

 

 

예제 1)

저 합 공식이 성립하는 걸 증명해라.

1단계 [ 기본 단계 ] : n=1일 때 성립? ㅇㅇ

2단계 [ 귀납 단계 ] : n=k일 때 참이라고 하고, n=k+1 넣어서 식 만들어보자.

 

성립함. 귀납 성공

 

 

 

---

예제 2)

 

---

 

예제 3)

 

 

* 우선 우리가 k < 2^k 가 참인 건 전제로 맞춰놓았다.

* 1< 2^k 는 참이다 ( k는 항상 양수이므로 )

→   P(k) = k <2^k 에서 P(k+1)로 만들어주자.

 

P(k)를 이용하여 좌변 먼저 만들어줄 예정이다.  양 변에 1을 더한다. k+1 < 2^k +1 . 

 

또한 P(k+1) 에서 사용할 2^(k+1)도 P(k)를 이용하여 만들어보자.

2^k+1 < 2^k + 2^k

2^k+1 < 2* 2^k

2^k+1 < 2^(k+1)  

 

세 항을 같이 본다면 k+1 ( <  2^k + 1 ) <  2^ (k+1)

 

(도움 될 듯)

 

 

 

---

예제 4)

 

 

 

---

 

 

예제 5)

 

 

원소 [ a가 있는 subset ] [ 없는 subset ]  하나씩이라서 그럼

 

---

 

Tile 예제

 

 

 

(도움/출처)

https://dongwoo338.tistory.com/6

https://rebro.kr/64

 

영어가 문제가 아니었는 듯

---

수학적 강 귀납법의 논리

1. n = 1 일때 p(1)이 참임을 보임
2. n = 1, n = 2, n = 3, ... n = k 가 모두 참임을 가정
3. n = k+1 일 때 p(k+1)이 참임을 보임

 

1부터 K까지 참인 걸 보여야 K+1이 참일 수 있음

그냥 귀납법) 1'이랑' K가 참이면 K+1도 참

 

 

예제 1) 

basic : P(2) 일 때 명제가 참

Inductive assume : P(j) (2<= j <= k ) 모두 다 참이면

Inductive derive :   P(k+1) 도 참이다 이말이야

 

 

---

 

---

 

 

최소 n변 이상을 갖고있는 도형 (= 삼각형 이상의 도형)은 (n>=3)

n-2개의 삼각형으로 나눠진다.

 

 

(출처)

 

한동대학교 최희열교수님 - 이산수학