일단 명칭은 이런데 이게 귀납법인가?
 ''[[철학,philosophy]]([[수리논리,mathematical_logic]]학을 제외한 고전적 철학)에서 말하는 귀납법이랑은 분명 다르지만 [[수학,math]]에서 [[귀납,induction]]은 (거의?) 항상 이걸 일컬음?? i.e. 수학과 철학에서 단어 induction의 의미가 다름? via 수백+내생각. chk''

도미노에 비유함.
 여기선 교육적으로 좋지 않은 비유라 함 ... https://youtu.be/NLcv5VGGQXU (12 Math) induction은 확장 논리 보다는 축소 논리의 도구로 보는게 맞다고.

표현들:
[[귀납가설,induction_hypothesis]]
{
https://proofwiki.org/wiki/Definition:Induction_Hypothesis
... Google:induction+hypothesis
[[가설,hypothesis]]
근데 이름이 가설이지만 사실 [[가정,assumption]]에 더 가까운? 
AKA inductive_hypothesis ? chk
}

[[induction_step]] induction_step
{
induction step

AKA inductive_step ? Ggl:"inductive step"

https://proofwiki.org/wiki/Definition:Induction_Step
isa [[귀납,induction]] [[단계,step]]
} // induction step Ggl:"induction step"

위 둘은 ([[하노이의_탑,tower_of_Hanoi]]같은) recursive_algorithm(curr [[재귀,recursion]])에 나오는데 mklink.

[[transfinite_induction]] - w 
{
pagename 아마도 초한귀납...

Cmp: [[transfinite_recursion]]

Cmp: [[finite_induction]] (?) tmp
{
 principle of finite induction
 https://planetmath.org/principleoffiniteinduction

 https://proofwiki.org/wiki/Principle_of_Finite_Induction

 ... Ggl:"finite induction" Ggl:유한귀납 ?
}

tmp bmks ko
https://chocobear.tistory.com/63

[[WtEn:transfinite_induction]]
[[WpEn:Transfinite_induction]]
...
Ggl:"transfinite induction"
Ggl:"초한 귀납"
Ndict:"초한 귀납"

KmsE:"transfinite induction" { [[Date(2023-11-14T13:55:00)]] "transfinite induction = 초한귀납법" }
}

= 수학적 귀납법을 사용한 증명 방법 =
전제: 자연수 n에 관한 [[명제,proposition]] p(n)이 있다.
1. n=1일때 성립함을 보인다. (show)
2. n=k일때 성립한다고 가정한다. (assume)
3. n=k+1일때 성립함을 보인다. (show)

= Principle of Mathematical Induction = 
Let ''S,,n,,'' be a [[진술,statement]] about the positive integer ''n''.
Suppose that
 1. ''S,,1,,'' is true.
 2. ''S,,k+1,,'' is true whenever ''S,,k,,'' is true.
Then ''S,,n,,'' is true for all positive integers ''n''.

(Stewart Calculus 7e, p.98)

= Proof by induction =
수학적 [[귀납,induction]]법을 쓴 [[증명,proof]]법
 1. 성질(property)이 입력 크기(input size) 1인 경우에 성립함(holds)을 증명 (base_case)
 1. 성질이 입력 크기 $1$ 에서 $n$ 까지 성립한다고 가정
 1. 성질이 입력 크기 $n+1$ 에서 성립함을 보임(show)
그러면, 성질은 모든 입력 크기 $n$ 에 대해 성립한다.

(김황남)

= Uses =
수학적귀납법의 사용처, 사용 예

베르누이 부등식 증명
[[베르누이_부등식,Bernoulli_inequality]] - curr at [[부등식,inequality#s-2]]

----
[[점화식,recurrence_relation]]로 정의된 [[수열,sequence]]
 $a_1=2,\,a_{n+1}=\frac12(a_n+6)$
에 대해

1. [[증가수열,increasing_sequence]]임을 밝히기
Q. Show that $a_{n+1}>a_n$ for all $n\ge 1.$
A. $n=1$ 일 때 참이다. $a_2=4>a_1$ 이기 때문.
이것이 $n=k$ 일 때 참이라고 가정하면
 $a_{k+1}>a_k$
 $a_{k+1}+6>a_k+6$
 $\frac12(a_{k+1}+6)>\frac12(a_k+6)$
 $a_{k+2}>a_{k+1}$
We have deduced([[연역,deduction]]) $a_{n+1}>a_n$ is true for $n=k+1.$ Therefore the inequality([[부등식,inequality]]) is true for all $n$ by '''induction'''.

2. 그리고 저 수열이 6 미만임을 밝히기([[유계,bounded]] [[유계수열,bounded_sequence]]) - 모든 $n$ 에 대해 $a_n<6$
증가수열이므로 이것이 [[하계,lower_bound]]가 있음을 우리는 안다. 모든 $n$ 에 대해, $a_n\ge a_1=2$ 이다.
$n=1$ 일 때 $a_1<6$ 이므로 주장(assertion)이 참이다.
$n=k$ 일때도 참이라 가정(suppose)한다. 그러면
 $a_k<6$
 $a_k+6<12$
 $\frac12(a_k+6) < \frac12(12) = 6$
 $a_{k+1}<6$
따라서 '''induction'''에 의해 $\forall n,\,a_n<6.$

(Stewart 9e p734)

= 한계, 약점, 단점 =
자연수에 대한 명제에만 적용 가능?
 - 이 표현을 어디서 봤더라? 아무튼, 그니까... 이산적인 steps로 환원가능하고(reducible), 그 steps 사이에 명확한 점화관계([[점화식,recurrence_relation]]) 가 있는, 이런 경우에만 사용가능. 이 생각이 맞는지? chk


= other resources =

see 맛있는해석학 4e p46 2.3 수학적 귀납법
https://blog.kyouko.moe/1
[[https://terms.naver.com/entry.naver?docId=3338051&ref=y&cid=47324&categoryId=47324 수학백과: 수학적 귀납법]]

----
mklink:
수열의귀납적정의. [[수열,sequence]]의 [[귀납,induction]]적 정의, 그러니까 [[점화식,recurrence_relation]]/[[재귀,recursion]] 같은거.

이것의 자연스러운 일반화: well-founded_induction - 작성중


Related:

[[추론,inference]]
 [[귀납,induction]]
 [[연역,deduction]]
 [[abduction]]

----
Twins:
https://mathworld.wolfram.com/PrincipleofMathematicalInduction.html
[[https://terms.naver.com/entry.naver?docId=3338051&ref=y&cid=47324&categoryId=47324 수학백과: 수학적 귀납법]]
https://encyclopediaofmath.org/wiki/Mathematical_induction
https://everything2.com/title/Mathematical+Induction
[[Namu:수학적%20귀납법]]
[[Libre:수학적_귀납법]]

https://artofproblemsolving.com/wiki/index.php/Induction
https://planetmath.org/principleoffiniteinduction
[[WpEn:Mathematical_induction]]
[[WpKo:수학적_귀납법]]
https://proofwiki.org/wiki/Definition:Mathematical_Induction
https://proofwiki.org/wiki/Principle_of_Mathematical_Induction

Up: [[수학,math]]