1 minute read

> Go to Number Theory Contents

Mathmatical Induction (수학적 귀납법)

To prove a statement that is true for each positive integer n, the proof technique, Mathematical Induction, is devised.
Mathmatical Induction(수학적 귀납법): 양의 정수 n(자연수, natural number)에 대해 참인 문장을 증명하기 위해 만들어짐

Natural number (자연수)
$n \in \mathbb{Z}$, $n > 0$
$\mathbb{N} = {1, 2, 3, , …}$

어떤 숫자 n이 자연수이면, n+1 또한 자연수이다.
$n = 1, n+1 = 2$
$n = 2, n+1 = 3$
….
Will use this property to prove mathematical induction

$S(n): \sum_{i=1}^{n} (2i-1)=n^2$ for every positive integer n.

(1) S(n)?
Statement concerning fixed integer n.

(2) Prove.
Assume S(n) is true, and show S(n+1) is also true.
$\therefore S(n)$ is true for $n=1,2,3,…$ (for all $n \in \mathbb{Z}$)

$n=1, S(1) = (2 \cdot 1 - 1) = 1 = 1^2$, true.
$S(n+1): \sum_{i=0}^{n+1} (2i-1) = (n+1)^2$ is true.

\begin{align}
LHS &= \sum_{i=1}^{n} (2i-1) + (2(n+1)-1) \nonumber\newline &= n^2 + (2n+1) \nonumber\newline &= (n+1)^2 = RHS \nonumber \end{align}
n이 1일 때, True이고 n+1이 true이기 때문에 모든 양의 정수 n에 대하여 만족한다. (1st principle)

2nd principle

Define a function recursively for all positive integers n by $f(1) = 1, f(2) = 5$, and for $n \leq 2, f(n+1)=f(n)+2f(n-1)$. Show that $f(n) = 2^n + (-1)^n$.

Starting number: 1
difference between this example and 1st principle?
Check S(1), S(2) both separately
f(n)이 3부터 시작하기 때문.
1st principle: Only assume s(n)
2nd principle:

Assume $S(n)$ is true and s(k) is true for $k = 1, …, n-1$
Will show $S(n+1)$ is true
$S(n)$ 외에도 $S(n-1)$과 $S(n-2)$또한 필요하다.

  1. Let $S(n) be f(n) = 2^n + (-1)^n$ for a fixed integer $n$.
  2. $f(1)=1$ by 1, $2^1+(-1)^1=1$ Therefore, S(1) is true.
  3. $f(2)=5$ by 2, $2^2+(-1)^2=5$ Therefore, S(2) is true.

\begin{align} f(n+1) &= f(n) + 2f(n-1) \nonumber \newline &= (2^n+(-1)^n) + 2(2^{n-1}+(-1)^{n-1}) \nonumber \newline &= 2^n + (-1)^n ++ 2^n + 2(-1)^{n-1} \nonumber \newline &= 2(2^n) + (-1)^{n-1}((-1)+2) \nonumber \newline &= 2^{n+1}+(-1)^{n+1} \nonumber \end{align}
Therefore, by Induction Principle 2nd,
$S(n)$ is true for $n = 1, 2, 3, …$

You May Also Enjoy