1. Ordinary Induction vs Strong Induction 저번에 배운 ordinary induction을 떠올려보자. Base case를 하나 증명하고, P(k) → P(k+1)이 성립함을 보이면 끝이었다. 그런데 항상 이게 가능할까? 코인 게임을 생각해보자. n+1개의 코인이 있을 때 Ali는 1개 또는 2개를 집을 수 있다. 그러면 Brad는 n개 또는 n-1개를 받게 된다. P(n+1)을 증명하려면 P(n)뿐만 아니라 P(n-1)도 알아야 한다는 뜻이다. Ordinary induction으로는 부족하다. 이럴 때 쓰는 게 Strong Induction이다. Ordinary induction이 바로 아래 발판만 밟고 올라가는 거라면, strong inductio..