Proof by Induction

\(1 + 2 + 3 + ... + n = \dfrac{1}{2} n(n + 1)\)

STEP 1

For n = 1:

\begin{equation*} \begin{split} 1 & = \tfrac{1}{2} (1)(1 + 1) \\\\ 1 & = 1 \\\\ \text{LHS} & = \text{RHS} \end{split} \end{equation*}

The statement is true for n = 1

STEP 2

Assume the statement is true for n = k:

\begin{equation*} 1 + 2 + 3 + ... + k = \tfrac{1}{2} k(k + 1) \end{equation*}

So, for n = k + 1:

\begin{equation*} 1 + 2 + 3 + ... + k + {\color {magenta} (k + 1)} = \tfrac{1}{2} (k + 1) (k + 2) \end{equation*}

\begin{equation*} \begin{split} & \text{LHS} \\\\ & 1 + 2 + 3 + ... + k + (k + 1) \quad {\color {blue} \rightarrow 1 + 2 + 3 + ... + k = \tfrac{1}{2} k(k + 1)}\\\\ & \tfrac{1}{2} k(k + 1) + (k + 1) \\\\ & (k + 1) ( \tfrac{1}{2} k + 1) \\\\ & \tfrac{1}{2} (k + 1) (k + 2) \\\\ & \text{LHS} = \text{RHS} \end{split} \end{equation*}

If the statement is true for n = k, then it is true for n = k + 1

STEP 3

Based on step 1 and 2, then:

The statement is true for n = 1, then the statement is true for n = 2

The statement is true for n = 2, then the statement is true for n = 3

and so on,

The statement is true for n ≥ 1

Exercise

Proof the statements below by mathematical induction

\(1 + 8 + 15 + \dotso + (7n - 6) = \dfrac{1}{2} (7n^2 - 5n)\)

Solution:

STEP 1

For n = 1:

\begin{equation*} \begin{split} 1 & =\tfrac{1}{2} [7(1)^2 - 5(1)] \\\\ 1 & = 1\\\\ \text{LHS} & = \text{RHS} \end{split} \end{equation*}

The statement is true for n = 1

STEP 2

Assume the statement is true for n = k:

\begin{equation*} 1 + 8 + 15 + \dotso + (7k - 6) = \tfrac{1}{2} (7k^2 - 5k) \end{equation*}

So, for n = k + 1:

\begin{equation*} \begin{split} 1 + 8 + 15 + \dotso + (7k - 6) + {\color {magenta} [7(k + 1) - 6]} & = \tfrac{1}{2} [7(k + 1)^2 - 5(k + 1)] \\\\ & = \tfrac{1}{2} [7(k^2 + 2k + 1) - 5k - 5] \\\\ & = \tfrac{1}{2} [7k^2 + 9k + 2] \end{split} \end{equation*}

\begin{equation*} \begin{split} & \text{LHS} \\\\ & 1 + 8 + 15 + \dotso + (7k - 6) + [7(k + 1) - 6] \quad {\color {blue} \rightarrow 1 + 8 + 15 + ... + (7k - 6) = \tfrac{1}{2} [7(k + 1)^2 - 5(k + 1)]}\\\\ & \tfrac{1}{2} (7k^2 - 5k) + [7(k + 1) - 6] \\\\ & \tfrac{1}{2} (7k^2 - 5k) + 7k + 1 \\\\ & \tfrac{1}{2}(7k^2 - 5k + 14k + 2 \\\\ & \tfrac{1}{2}(7k^2 + 9k + 2) \\\\ & \tfrac{1}{2}(7k^2 + 9k + 2) \\\\ & \text{LHS} = \text{RHS} \end{split} \end{equation*}

If the statement is true for n = k, then it is true for n = k + 1

STEP 3

Based on step 1 and 2, then:

The statement is true for n = 1, then the statement is true for n = 2

The statement is true for n = 2, then the statement is true for n = 3

and so on,

The statement is true for n ≥ 1

\(\dfrac{1}{1! \:.\: 3} + \dfrac{1}{2! \:.\: 4} + \dfrac{1}{3! \:.\: 5} + ... + \dfrac{1}{n! \: (n + 2)} = \dfrac{1}{2} - \dfrac{1}{(n + 2)!}\)

Solution:

STEP 1

For n = 1:

\begin{equation*} \begin{split} \frac{1}{1! \:.\: 3} & = \frac{1}{2} - \frac{1}{(1 + 2)!} \\\\ \frac{1}{3} & =\frac{1}{2} - \frac{1}{3!} \\\\ \frac{1}{3} & =\frac{1}{2} - \frac{1}{3 \:.\: 2 \:.\: 1} \\\\ \frac{1}{3} & =\frac{1}{2} - \frac{1}{6} \\\\ \frac{1}{3} & = \frac{1}{3}\\\\ LHS & = RHS \end{split} \end{equation*}

The statement is true for n = 1

STEP 2

Assume the statement is true for n = k:

\begin{equation*} {\color {blue} \frac{1}{1! \:.\: 3} + \frac{1}{2! \:.\: 4} + \frac{1}{3! \:.\: 5} + ... + \frac{1}{k! \: (k + 2)}} = {\color {red} \frac{1}{2} - \frac{1}{(k + 2)!}} \end{equation*}

So, for n = k + 1:

\begin{equation*} {\color {blue} \frac{1}{1! \:.\: 3} + \frac{1}{2! \:.\: 4} + \frac{1}{3! \:.\: 5} + ... + \frac{1}{k! \: (k + 2)}} + {\color {magenta} \frac{1}{ (k + 1)! \: (k + 3)}} = \frac{1}{2} - \frac{1}{(k + 3)!} \end{equation*}

\begin{equation*} \begin{split} & \text{LHS} \\\\ & {\color {blue} \frac{1}{1! \:.\: 3} + \frac{1}{2! \:.\: 4} + \frac{1}{3! \:.\: 5} + ... + \frac{1}{k! \: (k + 2)}} + {\color {magenta} \frac{1}{ (k + 1)! \: (k + 3)}} \\\\ & {\color {red} \frac{1}{2} - \frac{1}{(k + 2)!}} + {\color {magenta} \frac{1}{ (k + 1)! \: (k + 3)}} \\\\ & \frac{1}{2} - \frac{1}{(k + 2)(k + 1)!} + \frac{1}{ (k + 1)! \: (k + 3)} \\\\ & \frac{1}{2} - \frac{1}{(k + 1)!} \left(\frac{1}{k + 2} - \frac{1}{k + 3}\right) \\\\ & \frac{1}{2} - \frac{1}{(k + 1)!} \left(\frac{(k + 3) - (k + 2)}{(k + 2)(k + 3)}\right) \\\\ & \frac{1}{2} - \frac{1}{(k + 1)!} \:.\: \frac{1}{(k + 2)(k + 3)} \\\\ & \frac{1}{2} - \frac{1}{(k + 3)!} \\\\ & \text{LHS} \end{split} \end{equation*}

If the statement is true for n = k, then it is true for n = k + 1

STEP 3

Based on step 1 and 2, then:

The statement is true for n = 1, then the statement is true for n = 2

The statement is true for n = 2, then the statement is true for n = 3

and so on,

The statement is true for n ≥ 1

\(\displaystyle \sum_{r = 1}^n 3^r = \dfrac{3}{2}(3^n - 1)\)

Solution:

STEP 1

For n = 1:

\begin{equation*} \begin{split} \sum_{r = 1}^1 3^r & = \frac{3}{2}(3^1 - 1) \\\\ 3^1 & = 3 \\\\ \text{LHS} & = \text{RHS} \end{split} \end{equation*}

The statement is true for n = 1

STEP 2

Assume the statement is true for n = k:

\begin{equation*} {\color {blue} \sum_{r = 1}^{k} 3^r} = {\color {red} \frac{3}{2}(3^k - 1)} \end{equation*}

So, for n = k + 1:

\begin{equation*} \sum_{r = 1}^{k + 1} 3^r = \frac{3}{2}(3^{k + 1} - 1) \end{equation*}

\begin{equation*} \begin{split} & \text{LHS} \\\\ & \sum_{r = 1}^{k + 1} 3^r \\\\ & {\color {blue} \sum_{r = 1}^{k} 3^r} + \sum_{r = k + 1}^{k + 1} 3^r \\\\ & {\color {red} \frac{3}{2}(3^{k} - 1)} + 3^{k + 1} \\\\ & \tfrac{3}{2} \:.\: 3^{k} - \tfrac{3}{2} + 3^k \:.\: 3^1 \\\\ & 3^{k} \: (\tfrac{3}{2} + 3) - \tfrac{3}{2} \\\\ & \tfrac{9}{2} \: 3^{k} - \tfrac{3}{2} \\\\ & \tfrac{3}{2} (3 \:.\: 3^k - 1)\\\\ & \tfrac{3}{2} (3^{k + 1} - 1)\\\\ & \text{LHS} = \text{RHS} \end{split} \end{equation*}

If the statement is true for n = k, then it is true for n = k + 1

STEP 3

Based on step 1 and 2, then:

The statement is true for n = 1, then the statement is true for n = 2

The statement is true for n = 2, then the statement is true for n = 3

and so on,

The statement is true for n ≥ 1

\(\displaystyle \sum_{r = 1}^n \dfrac{2r - 1}{3^r} = 1 - \dfrac{n + 1}{3^n}\)

Solution:

\(5^n + 3\) is divisible by 4, for \(n \geq 1\)

Solution:

STEP 1

For n = 1:

\(5^1 + 3 = 8\) is divisible by 4

The statement is true for n = 1

STEP 2

Assume the statement is true for n = k:

\begin{equation*} 5^k + 3 = 4p \end{equation*}

So, for n = k + 1:

\begin{equation*} \begin{split} & 5^{k + 1} + 3 \\\\ & 5 \:.\: 5^k + 3 \\\\ & 4 \:.\: 5^k + 5^k + 3 \quad {\color {blue} \rightarrow 5^k + 3 = 4p} \\\\ & 4 \:.\: 5^k + 4p \\\\ & 4 \: (5^k + p) \quad {\color {blue} \rightarrow \text{ divisible by 4}} \end{split} \end{equation*}

If the statement is true for n = k, then it is true for n = k + 1

STEP 3

Based on step 1 and 2, then:

The statement is true for n = 1, then the statement is true for n = 2

The statement is true for n = 2, then the statement is true for n = 3

and so on,

The statement is true for n ≥ 1

\(2^{2n + 1} + 3^{2n +1}\) is divisible by 5, for \(n \geq 1\)

Solution:

STEP 1

For n = 1:

\(2^{2(1) + 1} + 3^{2(1) +1} = 35\) is divisible by 5

The statement is true for n = 1

STEP 2

Assume the statement is true for n = k:

\begin{equation*} 2^{2k + 1} + 3^{2k +1} = 5p \end{equation*}

So, for n = k + 1:

\begin{equation*} \begin{split} & 2^{2(k + 1) + 1} + 3^{2(k + 1) +1} \\\\ & 2^{2k + 3} + 3^{2k + 3} \\\\ & 2^{2k + 1} \:.\: 2^2 + 3^{2k + 1} \:.\: 3^2 \\\\ & 4 \:.\: 2^{2k + 1} + 9 \:.\: 3^{2k + 1} \\\\ & 4 \:.\: 2^{2k + 1} + 4 \:.\: 3^{2k + 1} + 5 \:.\: 3^{2k + 1} \\\\ & 4 \:.\: (2^{2k + 1} + 4 \:.\: 3^{2k + 1}) + 5 \:.\: 3^{2k + 1} \quad {\color {blue} \rightarrow 2^{2k + 1} + 4 \:.\: 3^{2k + 1} = 5p} \\\\ & 4 \:.\: 5p + 5 \:.\: 3^{2k + 1} \\\\ & 5 (4 + 3^{2k + 1}) \quad {\color {blue} \rightarrow \text{ divisible by}} \end{split} \end{equation*}

If the statement is true for n = k, then it is true for n = k + 1

STEP 3

Based on step 1 and 2, then:

The statement is true for n = 1, then the statement is true for n = 2

The statement is true for n = 2, then the statement is true for n = 3

and so on,

The statement is true for n ≥ 1

\(3^n > 1 + 2n\), for \(n > 1\)

Solution:

STEP 1

For n = 2:

\begin{equation*} \begin{split} 3^2 & > 1 + 2(2) \\\\ 9 & > 5 \end{split} \end{equation*}

The statement is true for n = 2

STEP 2

Assume the statement is true for n = k:

\begin{equation*} {\color {blue} 3^k} > {\color {red} 1 + 2k} \end{equation*}

So, for n = k + 1:

\begin{equation*} \begin{split} 3^{k +1} & > 1 + 2(k + 1) \\\\ 3 \:.\: 3^k & > 2k + 2 \\\\ 2 \:.\: 3^k + {\color {blue} 3^k} & > 1 + {\color {red} 1 + 2k} \end{split} \end{equation*} Since \(2 \:.\: 3^k > 1\) and \(3^k > 1 + 2k\), then the statement is true for n = k + 1

STEP 3

Based on step 1 and 2, then:

The statement is true for n = 2, then the statement is true for n = 3

The statement is true for n = 4, then the statement is true for n =5

and so on,

The statement is true for n > 1

\((x + y)^n > x^n + y^n\), untuk \(n > 1\)

Solution:

\(\sin x + \sin 2x + \sin 3x + ... + \sin nx = \dfrac{\sin \frac{1}{2}(n + 1)x \sin \frac{1}{2}nx}{\sin \frac{1}{2}x}\)

Solution:

STEP 1

For n = 1:

\begin{equation*} \begin{split} \sin x & = \frac{\sin \frac{1}{2}(1 + 1)x \sin \frac{1}{2}(1)x}{\sin \frac{1}{2}x} \\\\ \sin x & = \frac{\sin \frac{1}{2}(2)x \cancel {\sin \frac{1}{2}x}}{\cancel {\sin \frac{1}{2}x}} \\\\ \sin x & = \sin x \\\\ \text{LHS} & = \text{RHS} \end{split} \end{equation*}

The statement is true for n = 1

STEP 2

Assume the statement is true for n = k:

\begin{equation*} {\color {blue} \sin x + \sin 2x + \sin 3x + ... + \sin kx} = {\color {red} \frac{\sin \frac{1}{2}(k + 1)x \sin \frac{1}{2}kx}{\sin \frac{1}{2}x}} \end{equation*}

So, for n = k + 1:

\begin{equation*} {\color {blue} \sin x + \sin 2x + \sin 3x + ... + \sin kx }+ {\color {magenta}\sin (k + 1)x} = \frac{\sin \frac{1}{2}(k + 2)x \sin \frac{1}{2}(k + 1)x}{\sin \frac{1}{2}x} \end{equation*}

\begin{equation*} \begin{split} & \text{LHS} \\\\ &{\color {blue}\sin x + \sin 2x + \sin 3x + ... + \sin kx} + {\color {magenta} \sin (k + 1)x}\\\\ & {\color {red} \frac{\sin \frac{1}{2}(k + 1)x \sin \frac{1}{2}kx}{\sin \frac{1}{2}x}} + {\color {magenta} \sin (k + 1)x} \\\\ & \frac{\sin \frac{1}{2}(k + 1)x \sin \frac{1}{2}kx + \sin (k + 1)x \sin \frac{1}{2}x}{\sin \frac{1}{2}x} \\\\ & \frac{\sin \frac{1}{2}(k + 1)x \sin \frac{1}{2}kx + 2 \sin \frac{1}{2}(k + 1)x \cos \frac{1}{2}(k + 1)x \sin \frac{1}{2}x}{\sin \frac{1}{2}x} \\\\ & \frac{\sin \frac{1}{2}(k + 1)x \: [\sin \frac{1}{2}kx + 2 \cos \frac{1}{2}(k + 1)x \sin \frac{1}{2}x]}{\sin \frac{1}{2}x} \\\\ & \frac{\sin \frac{1}{2}(k + 1)x \: [\cancel {\sin \frac{1}{2}kx} + \sin (\frac{1}{2}k + 1)x - \cancel {\sin \frac{1}{2} kx}]}{\sin \frac{1}{2}x} \\\\ & \frac{\sin \frac{1}{2}(k + 1)x \: \sin (\frac{1}{2}k + 1)x}{\sin \frac{1}{2}x} \\\\ & \frac{\sin \frac{1}{2}(k + 1)x \: \sin \frac{1}{2}(k + 2)x}{\sin \frac{1}{2}x} \\\\ & \text{LHS} = \text{RHS} \end{split} \end{equation*}

If the statement is true for n = k, then it is true for n = k + 1

STEP 3

Based on step 1 and 2, then:

The statement is true for n = 1, then the statement is true for n = 2

The statement is true for n = 2, then the statement is true for n = 3

and so on,

The statement is true for n ≥ 1

\(\cos x + \cos 2x + \cos 3x + ... + \cos nx = \dfrac{\cos \frac{1}{2}(n + 1)x \sin \frac{1}{2}nx}{\sin \frac{1}{2}x}\)

Solution:

Kembali ke Proof by Induction