수학적귀납법,mathematical_induction

일단 명칭은 이런데 이게 귀납법인가?
철학,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


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

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





KmsE:transfinite induction { 2023-11-14 "transfinite induction = 초한귀납법" }
}

[edit]

수학적 귀납법을 사용한 증명 방법

전제: 자연수 n에 관한 명제,proposition p(n)이 있다.
1. n=1일때 성립함을 보인다. (show)
2. n=k일때 성립한다고 가정한다. (assume)
3. n=k+1일때 성립함을 보인다. (show)

[edit]

Principle of Mathematical Induction

Let Sn be a 진술,statement about the positive integer n.
Suppose that
  1. S1 is true.
  2. Sk+1 is true whenever Sk is true.
Then Sn is true for all positive integers n.

(Stewart Calculus 7e, p.98)

[edit]

Proof by induction

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

(김황남)

[edit]

Uses

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



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)

[edit]

한계, 약점, 단점

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


[edit]

other resources