(유튜브 동영상인데 현재는 삭제되어서 내용만 남김)

1

개념

• 논리 중에서 자연수에 의존하는 논리가 수학적 귀납법
  • $P(1)$이 만족하고, $P(k)$가 참이고 $P(k+1)$이 만족하면, 모든 자연수에 대하여 $P(n)$ 성립하는 논리
    • 초기항과 다음 항을 정의하는 식이 맞다면 무한루프가 돌아서 모든 자연수에 대하여 참이 성립한다.
  • $P(1), P(k) \Rightarrow P(k+1), k \in \mathbb{N} \Leftrightarrow \forall n \in \mathbb{N}, P(n)$
• 정렬 원리
  • $A \subseteq \mathbb{N}, (A \neq \emptyset) \Rightarrow \exists \min A$

수학적 귀납법을 이용한 수식 정의

• $n! = n(n-1)!, 0! = 1$
• $x^{n} = x \cdot x^{n-1}$
• $f^{n}(x) = {d \over dx} f^{n-1}(x), f^{0}(x) = f(x)$
• ${n}C{k} = {n! \over k!(n-k)!}$
• ${n}C{k} = {n-1}C{k-1} + {n-1}C{k}, {1}C{0} = 1, {1}C{1} = 1$
• $\sum_{k=0}^{n} K = {n(n+1) \over 2}$
• $\sum_{k=0}^{n} K^{2} = {n(n+1)(2n+1) \over 6}$
• $\sum_{k=0}^{n} K^{3} = {n^{2}(n+1)^{2} \over 4}$
  • 수열합 자체도 귀납법으로 공식을 이끌어 낼 수 있는데, $k$의 합을 알면 $k^{2}$의 합을 알 수 있고, k와 $k^{2}$의 합을 알면 $k^{3}$의 합을 알 수 있다.