https://ocw.mit.edu/courses/6-042j-mathematics-for-computer-science-fall-2010/resources/lecture-2-induction/

증명하는 방법으로는 크게 두 가지가 있다.
Indirect proof : 말 그대로 직접적으로 증명하지 않는 증명법. - 반대 명제가 거짓임을 밝혀 이 명제가 참임을 증명하는 귀류법(proof by contradiction)이 대표적인 예시.
Direct proof : 말 그대로 직접적으로 명제가 참임을 증명하는 방법. - 귀납법(induction)이 대표적인 예시.

귀납법은 이산 수학 분야와 컴퓨터 과학에서 매우 중요한 역할을 한다고 한다.
사실 이산 수학에서 이산 discrete이라는 특징을 규정하는데 사용된다고 한다.

일반 귀납법 Ordinary Induction

P라는 명제를 증명하고자 한다면

1. P(0) 0의 경우에 P가 참이고
2. P(n) 이 참임이 P(n+1)가 참임을 함의한다면
3. P(m)도 마찬가지로 참이다.
   위와 같은 논리 형식에 맞춰서 증명을 하면 된다.
   보기에는 참 간단한데 왜 이렇게 어려운지 모르겠다.

예시

수업에서 예시로 제시된 문제는 다음과 같다.

1

P = For all $n \in \mathbb{N}$: $1+2+3+\cdots+n=\frac{n(n+1)}{2}$
그럼 위의 P를 증명하기 위해 다음과 같은 두 명제를 증명해야 한다.

1. P(0) 증명 base case
2. P(n)가 P(n+1)를 함의함을 증명
   다음과 같다.

먼저, base case 증명

$\frac{0(0+1)}{2} = 0$

다음, 함의관계 증명

P(n) implies P(n+1)
중요한 부분은 왼쪽을 가정하고 오른쪽을 증명하는 점이다.
$1+2+3\cdot+n=\frac{n(n+1)}{2}$ 을 가정
$1+2+3\cdot+n+(n+1)=\frac{(n+1)((n+1)+1)}{2}$ 을 증명

P(n)의 양 변은 같기 때문에 (가정되었기 때문에)
양 변에 (n+1)을 더해줘도 양 변은 같다.
$1+2+3\cdot+n+(n+1)=\frac{n(n+1)}{2}+(n+1)$
오른쪽 변은 다음과 같이 변할 수 있다.
$\frac{n(n+1)}{2}+(n+1)=\frac{n(n+1)}{2}+\frac{2n(n+1)}{2}=\frac{n^2+3n+2}{2}=\frac{(n+1)(n+2)}{2}$
마지막으로 (n+2)는 (n+1)+1 이므로 $\frac{(n+1)((n+1)+1)}{2}$가 나온다.

2. L트로미노 타일링 문제

$2^n*2^n$개로 이루어진 타일 위에 'ㄴ'자 모양으로 생긴 3칸 넓이의 타일을 배치하려고 할 때,
한 칸은 Bill 이라는 사람의 동상을 세울 수 있다(= 한 칸의 자리는 비어있다).

base case

P(0) 는 $2^0*2^0=1$ 이라서 한 칸의 자리가 비어있으니 참

inductive step

P(n) -> P(n+1)
$2^{n+1}*2^{n+1}=2^{2n+2}=2^{2n}*2^2=4(2^n*2^n)$
n+1은 n일때의 타일 전체가 4개 있는것과 같다.
그래서 $2^n*2^n$의 경우가 참이라면 나머지 세 개의 $2^n*2^n$에서도 참이고
나머지 세 개에서도 한 자리씩 비게 되고 거기에 마지막 타일을 넣으면 전체$2^{n+1}*2^{n+1}$ 개의 타일에서도 딱 한 칸을 제외하고 모두 타일로 덮을 수 있다.

https://ocw.mit.edu/courses/6-042j-mathematics-for-computer-science-fall-2010/resources/lecture-3-strong-induction/

Now, good proofs are very much like good code.
In fact, one of the reasons we care so much about teaching you how to write a good proof in computer science is so that later on,
you'll be able to prove that your programs are doing what you expect-- what they're supposed to do.

증명이 프로그래밍에 매우 중요하다고.

Invariant 불변식

수업에서는 위치 바꾸는 퍼즐문제를 통해 설명한다.

불변식이란?

초기 상태에서 목표 상태로 이행할 수 없음을 증명할때 가장 효과적으로 동원되는 방법이 불변식을 찾아서 목표 상태에 그 불변식이 존재하지 않음을 증명하는 방법이다.
초기 상태에 가할 수 있는 여러 변화들이 있을 떄 (수업에서 나온 예시는 퍼즐의 행 이동과 열 이동)
이 변화들의 조합으로는 절대 바뀌지 않는 성질이 불변식이다.

예시

A B C
D E F
H G -

3x3 칸에 다음과 같이 알파벳이 나열되어있는데 H와 G의 자리를 바꿔서 올바르게 순서대로 정렬할 수 있을까?

규칙은 퍼즐을 빈칸으로 움직이는것 밖에 없고 이는 두 방법으로 구체화된다.

1. 빈 칸의 아래 혹은 위에 있는 퍼즐을 빈 칸으로 옮기는 것 (열 이동)
2. 빈 칸의 왼쪽 혹은 오른쪽에 있는 퍼즐을 빈 칸으로 옮기는 것 (행 이동)

이 두 방법을 어떻게 조합해도 바꿀수 없는 어떤 성질을 찾는다면 뭐가 될 수 있을까?

1. 일단 행 이동은 알파벳 나열 순서를 바꾸지 못한다.

A B C
D E F
H - G

위 처럼 초기 상태에서 G를 옮겨도 나열 순서는 바뀌지 않는다. 오직 열 이동만이 나열 순서를 바꿀 수 있다.

2. 열 이동은 자기 앞이나 뒤에 있는 두 개의 퍼즐들의 상대적 순서를 바꾼다.

A B C
D - F
H E G

위 처럼 E를 한 칸 내리면서 열 이동을 가하면, E 뒤에 있는 F와 H의 위치값(순서)가 1씩 늘어나고 옮겨진 퍼즐 자신은 -2가 된다.

3. 움직이는 동안 역전된 쌍의 개수는 2개씩 변화하거나(열 이동) 혹은 그대로다(행 이동)
   역전쌍이란 초기 상태에 G와 H의 순서가 서로 바뀌어있던것 처럼, 원래 순서와 달리 배치되어있는 두 알파벳을 한 쌍으로 묶은것을 칭하기로 한다.
   초기 상태에는 G와 H만 빼고 나머지는 순서가 일치했기에 연전쌍은 (G,H) 하나뿐이다.
   그런데 위의 2번 열 이동의 예시를 보면 역전쌍의 개수가 2개 늘어나는것을 볼 수가 있다.
   A>B>C>D>E>F>G>H 가 맞는 순서인데 지금은
   A>B>C>D>F>H>E>G 이렇게 나열되어 있다.
   F보다 앞에 있어야 할 E가 F뒤에 있으니 역전쌍이 생긴다. (E,F)
   H보다 앞에 있어야 할 E와 G가 H뒤에 있으니 역전쌍이 생긴다. (E,H) (G,H)
   역전쌍의 개수는 3개로 초기 1개에서 +2가 됐다.
   (다시 그대로 E를 위로 올리면 -2로 역전쌍의 개수는 1개가 된다.)

여기서 불변식은 바로 초기에 역전쌍의 개수가 홀수라는 것이고,
어떻게 변화를 조합해도 역전쌍의 개수의 parity(홀짝여부) 는 변하지 않기 때문에 목표상태에 도달할 수 없다.

'강한' 귀납법?

일반 귀납법에서는 귀납 단계에서 P(n) -> P(n+1) 을 증명한다면
강한 귀납은 다음과 같이 증명한다.

1. P(0)이 참이고 (기본단계)
2. P(0),P(1),....,P(n) 모두가 참임이 P(n+1)을 함의한다면
3. P(m)도 마찬가지로 참이다.

예) 피보나치 수열

피보나치 수열은 수학자 피보나치가 13세기 초 인구 증가 모델(?)을 만들면서 생겼다고 한다.
파인애플 싹과 솔방울의 모양과 같은 자연의 많은 것들을 설명하는데 사용된다고 한다.

명제 : $F(n)$ is even IFF $F(n+3)$ is even

base case

피보나치 수열은 base case가 두 개 필요하다 : 0 일때와 1일때.

• n=0 : F(0) = 0 이고 F(3) = 2 로 둘 다 짝수다.
• n=1 : F(1) = 1 이고 F(4) = 3 으로 둘 다 짝수가 아니다.

귀납단계

어떤 수 m과 k가 있다고 하자.

$m + k$ is even IFF [m is even IFF k is even].
((k가 짝수)일 경우에만 m도 짝수)일 경우에만 $m+k$도 짝수다.
즉 m과 k가 같은 홀짝성을 가질 경우에만 $m+k$는 짝수다.

강한 귀납은 0,1,...,n 까지 모든 경우가 P(n+1)을 함의한다는 것을 증명하는 방법이라고 했다.

1. $F(n+1)$ is even
2. IFF $F(n)+F(n-1)$ is even
   (def of $F(n+1)$)
3. IFF [$F(n)$ is even IFF $F(n-1)$ is even]
4. IFF [$F(n+3)$ is even IFF $F(n+2)$ is even]
   (by strong ind. hyp. $P(n),P(n-1)$)
5. IFF $F(n+3)+F(n+2)$ is even
6. IFF $F(n+4)$ is even.
   (by def of $F(n+4)$)

증명하려고 하는 명제는 F(n+1)의 경우, 즉 F(n+4)가 짝수인 경우에만 F(n+1)도 참이라는것.

• F(n+1)이 짝수라는 것은 F(n) + F(n-1)이 짝수라는 의미고,
• F(n) + F(n-1) 이 짝수라는 의미는 F(n-1)과 F(n)가 같은 홀짝성을 가진다는 의미이고, (위의 m,k 명제)
• F(n-1)과 F(n)이 같은 홀짝성을 가진다는 것은 거기에 같은 숫자를 더한다고 해도 (가령 3씩 더해 F(n+2)와 F(n+3) 모두) 같은 홀짝성을 가진다는 의미이고,
• F(n+2)와 F(n+3)이 같은 홀짝성을 가진다는 것은 그 다음 수열인 F(n+4)라는 의미다.