데코수학/ 집합론/ 수학적 귀납법

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

1

개념

•

논리 중에서 자연수에 의존하는 논리가 수학적 귀납법

◦

P(1)P(1)P(1)이 만족하고, P(k)P(k)P(k)가 참이고 P(k+1)P(k+1)P(k+1)이 만족하면, 모든 자연수에 대하여 P(n)P(n)P(n) 성립하는 논리

▪

초기항과 다음 항을 정의하는 식이 맞다면 무한루프가 돌아서 모든 자연수에 대하여 참이 성립한다.

◦

P(1),P(k)⇒P(k+1),k∈N⇔∀n∈N,P(n)P(1), P(k) \Rightarrow P(k+1), k \in \mathbb{N} \Leftrightarrow \forall n \in \mathbb{N}, P(n)P(1),P(k)⇒P(k+1),k∈N⇔∀n∈N,P(n)

•

정렬 원리

◦

A⊆N,(A≠∅)⇒∃min⁡AA \subseteq \mathbb{N}, (A \neq \emptyset) \Rightarrow \exists \min AA⊆N,(A=∅)⇒∃minA

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

•

n!=n(n−1)!,0!=1n! = n(n-1)!, 0! = 1n!=n(n−1)!,0!=1

•

xn=x⋅xn−1x^{n} = x \cdot x^{n-1}xn=x⋅xn−1

•

fn(x)=ddxfn−1(x),f0(x)=f(x)f^{n}(x) = {d \over dx} f^{n-1}(x), f^{0}(x) = f(x)fn(x)=dxd​fn−1(x),f0(x)=f(x)

•

nCk=n!k!(n−k)!_{n}C_{k} = {n! \over k!(n-k)!}n​Ck​=k!(n−k)!n!​

•

nCk=n−1Ck−1+n−1Ck,1C0=1,1C1=1_{n}C_{k} = _{n-1}C_{k-1} + _{n-1}C_{k}, _{1}C_{0} = 1, _{1}C_{1} = 1n​Ck​=n−1​Ck−1​+n−1​Ck​,1​C0​=1,1​C1​=1

•

∑k=0nK=n(n+1)2\sum_{k=0}^{n} K = {n(n+1) \over 2}∑k=0n​K=2n(n+1)​

•

∑k=0nK2=n(n+1)(2n+1)6\sum_{k=0}^{n} K^{2} = {n(n+1)(2n+1) \over 6}∑k=0n​K2=6n(n+1)(2n+1)​

•

∑k=0nK3=n2(n+1)24\sum_{k=0}^{n} K^{3} = {n^{2}(n+1)^{2} \over 4}∑k=0n​K3=4n2(n+1)2​

◦

수열합 자체도 귀납법으로 공식을 이끌어 낼 수 있는데, kkk의 합을 알면 k2k^{2}k2의 합을 알 수 있고, k와 k2k^{2}k2의 합을 알면 k3k^{3}k3의 합을 알 수 있다.