수학적 귀납
Mathematical induction, 결과를 증명하거나 자연수에 대한 설명을 설정하는 기술입니다. 이 부분에서는 다양한 예제를 통해 방법을 설명합니다.
정의
Mathematical Induction 모든 자연수에 대해 진술, 공식 또는 정리가 사실임을 증명하는 데 사용되는 수학적 기술입니다.
이 기술은 다음과 같이 진술을 증명하는 두 단계를 포함합니다.
Step 1(Base step) − 진술이 초기 값에 대해 참임을 증명합니다.
Step 2(Inductive step)-이 명령문은 N 마찬가지 경우 증명 번째 반복 (또는 숫자 N )가 다음과 같은 사실 (N + 1) 번째 반복 (또는 숫자 N + 1 ).
그것을하는 방법
Step 1− 진술이 참인 초기 값을 고려하십시오. n = 초기 값에 대해 진술이 참임을 보여야한다.
Step 2− n = k 값에 대해 진술이 참이라고 가정합니다 . 그런 다음 n = k + 1에 대해 진술이 참임을 증명하십시오 . 우리는 실제로 n = k + 1 을 두 부분으로 나누고, 한 부분은 n = k (이미 증명 됨)이고 다른 부분을 증명하려고합니다.
문제 1
$ 3 ^ n-1 $는 n = 1, 2, ...에 대해 2의 배수입니다.
Solution
Step 1 − $ n = 1, 3 ^ 1-1 = 3-1 = 2 $ (2의 배수)
Step 2 − $ n = k $에 대해 $ 3 ^ n-1 $이 참이라고 가정 해 봅시다. 따라서 $ 3 ^ k -1 $가 참 (가정입니다)
$ 3 ^ {k + 1} -1 $도 2의 배수임을 증명해야합니다.
$ 3 ^ {k + 1}-1 = 3 \ times 3 ^ k-1 = (2 \ times 3 ^ k) + (3 ^ k-1) $
첫 번째 부분 $ (2 \ times 3k) $는 확실히 2의 배수이고 두 번째 부분 $ (3k -1) $도 이전 가정과 동일합니다.
따라서 $ 3 ^ {k + 1} – 1 $는 2의 배수입니다.
따라서 $ 3 ^ n – 1 $이 2의 배수임을 증명합니다.
문제 2
$ 1 + 3 + 5 + ... + (2n-1) = n ^ 2 $ for $ n = 1, 2, \ dots $
Solution
Step 1 − $ n = 1, 1 = 1 ^ 2 $의 경우 1 단계가 충족됩니다.
Step 2 − $ n = k $에 대한 진술이 참이라고 가정 해 보겠습니다.
따라서 $ 1 + 3 + 5 + \ dots + (2k-1) = k ^ 2 $는 참 (가정 임)
우리는 $ 1 + 3 + 5 + ... + (2 (k + 1) -1) = (k + 1) ^ 2 $도 성립한다는 것을 증명해야합니다
$ 1 + 3 + 5 + \ dots + (2 (k + 1)-1) $
$ = 1 + 3 + 5 + \ dots + (2k + 2-1) $
$ = 1 + 3 + 5 + \ dots + (2k + 1) $
$ = 1 + 3 + 5 + \ dots + (2k-1) + (2k + 1) $
$ = k ^ 2 + (2k + 1) $
$ = (k + 1) ^ 2 $
따라서 $ 1 + 3 + 5 + \ dots + (2 (k + 1)-1) = (k + 1) ^ 2 $ 홀드가 2 단계를 충족합니다.
따라서 $ 1 + 3 + 5 + \ dots + (2n-1) = n ^ 2 $가 증명됩니다.
문제 3
$ (ab) ^ n = a ^ nb ^ n $이 모든 자연수 $ n $에 대해 참임을 증명하십시오.
Solution
Step 1 − $ n = 1, (ab) ^ 1 = a ^ 1b ^ 1 = ab $의 경우 1 단계가 충족됩니다.
Step 2 − $ n = k $에 대해 진술이 참이라고 가정 해 봅시다. 따라서 $ (ab) ^ k = a ^ kb ^ k $가 참입니다 (가정입니다).
$ (ab) ^ {k + 1} = a ^ {k + 1} b ^ {k + 1} $도
주어진 경우 $ (ab) ^ k = a ^ kb ^ k $
또는 $ (ab) ^ k (ab) = (a ^ kb ^ k) (ab) $ [양쪽에 'ab'곱하기]
또는 $ (ab) ^ {k + 1} = (aa ^ k) (bb ^ k) $
또는 $ (ab) ^ {k + 1} = (a ^ {k + 1} b ^ {k + 1}) $
따라서 2 단계가 증명됩니다.
따라서 $ (ab) ^ n = a ^ nb ^ n $ 은 모든 자연수 n에 대해 참입니다.
강력한 유도
강력한 귀납법은 또 다른 형태의 수학적 귀납법입니다. 이 유도 기법을 통해 다음 단계를 사용하여 명제 함수 $ P (n) $가 모든 양의 정수 $ n $에 대해 참임을 증명할 수 있습니다.
Step 1(Base step) − 최초 명제 $ P (1) $가 참임을 증명합니다.
Step 2(Inductive step) − 조건문 $ [P (1) \ land P (2) \ land P (3) \ land \ dots \ land P (k)] → P (k + 1) $가 양의 정수 $에 대해 참임을 증명합니다. k $.