[이산수학2-3]Mathmetical Induction(수학적 귀납법)

수학적 귀납법의 원리 ▷ 기본 과정(Basis Step) - P(n=1) 이 참임을 증명 - 이때 무조건 n=1이 아니여도 된다. ▷ 추론 과정(Inductive Step) - n>=1일 때, if S(n)이 참이면, then S(n+1)이 참임을 증명. - 기본과정과 추론 과정이 증명되면 기본 과정에서 연쇄적으로 무한대까지 참인 결과를 얻어낼 수 있다. Factorial을 귀납적으로 표현하면 다음과 같다.

수학적 귀납법의 예시 ▷ 등비수열의 합(Geometric Sum) - 등비수열의 합은 등비수열의 n번째 항까지의 합을 의미한다. ▷ 멱집합의 크기 ▷ 타일링 문제(A Tiling Problem) Q) k * k size의 정사각형 공간에서 1 * 1 size의 타일을 제거한 것을 trimino로만 구현이 가능한가? (이때 k는 2의 거듭제곱이다.)

Trimino 루프 불변자(loop invariant) - 루프가 실행되기 직전에 참이고 루프의 각 반복 후에 참인 프로그램 변...