Inductive reasoning is reasoning in which on the basis of a series of individual cases we make conclusion about the general rule. However, that conclusion does not have to be necessarily correct. Therefore, it also called the incomplete induction.
Mathematical induction is a method of proving that is used to demonstrate the various properties of natural numbers.
Principle of mathematical induction. If it is known that some statement is true for $n=1$ and if from the assumption that it is true for some natural number $n$ implies that it is true for the next natural number $ n +1$, then the statement is true for every natural number $n$.
The mathematical induction is given as the axiom, that is, it is the one of the Peano’s axioms given in the following form;
If $M \subseteq \mathbb{N}$ such that:
1.) (B) $1 \in M$
2.) (I) $n \in M \Rightarrow n +1 \in M$
then $M = \mathbb{N}$,
that is, the set $M$ is equal to the set of natural numbers.
The step (B) is called the basis, and (I) is called the inductive step, that is, the proof we provide in two steps. In basis we prove that some statement is true for $n=1$ and in the inductive step from assumption that the statement is true for some $n \in \mathbb{N}$ we prove that the statement is also true for the next natural number $ n + 1$.
Example 1. Prove the formula for the sum of first $n$ natural numbers by using the principle of mathematical induction:
$$ 1 + 2 + 3 + \ldots + n = \frac{n(n+1)}{2}, \quad \forall n \in \mathbb{N}.$$
Solution:
We need to prove is it the given statement true for $n=1$:
$$1 = \frac{1(1+1)}{2} = 1.$$
Therefore, the statement is true for $n=1$.
Suppose that the statement is true for some $n \in \mathbb{N}$ , that is, that for some $n \in \mathbb{N}$ the following is true:
$$ 1 + 2 + 3 + \ldots + n = \frac{n(n+1)}{2}$$
Now we must prove that the statement is also true for $n+1 \in \mathbb{N}$, that is, that for $n+1 \in \mathbb{N}$ the following is valid:
$$ 1 + 2 + 3 + \ldots + n+n+1 = \frac{(n+1)((n+1)+1)}{2} = \frac{(n+1)(n+2)}{2}.$$
By using the assumption, we have:
$$\underbrace{ 1 + 2 + 3 + \ldots + n}_{ = \frac{n(n+1)}{2}} + n+1 = \frac{n(n+1)}{2} + n + 1 = \frac{n(n+1)+ 2(n+1)}{2} = \frac{(n+1)(n+2)}{2}.$$
Therefore, the statement is true for $n+1 \in \mathbb{N}$. By the axiom of mathematical induction, the statement is true for every natural number $n$.
Example 2.
Prove that $\forall n \in \mathbb{N}$ is valid:
$$\frac{1}{1 \cdot 3} + \frac{1}{3 \cdot 5} + \cdots + \frac{1}{(2n-1)(2n+1)} = \frac{n}{2n+1}.$$
Solution:
For $n=1$
$$ \frac{1}{1 \cdot 3} = \frac{1}{2\cdot 1 +1}$$
$$\frac{1}{3} = \frac{1}{3}$$
the statement is true.
Suppose that for some $n \in \mathbb{N}$ the statement is true, that is, that for some $n \in \mathbb{N}$ is true:
$$\frac{1}{1 \cdot 3} + \frac{1}{3 \cdot 5} + \cdots + \frac{1}{(2n-1)(2n+1)} = \frac{n}{2n+1}.$$
We must prove that the statement is also true for $n+1 \in \mathbb{N}$:
$$\frac{1}{1 \cdot 3} + \frac{1}{3 \cdot 5} + \cdots + \frac{1}{(2n-1)(2n+1)}+ \frac{1}{(2(n+1)-1)(2(n+1)+1)} = \frac{n+1}{2(n+1)+1},$$
that is
$$\frac{1}{1 \cdot 3} + \frac{1}{3 \cdot 5} + \cdots + \frac{1}{(2n-1)(2n+1)}+ \frac{1}{(2n+1)(2n+3)} = \frac{n+1}{2n+3}.$$
By using the assumption, we have:
$$\underbrace{\frac{1}{1 \cdot 3} + \frac{1}{3 \cdot 5} + \cdots + \frac{1}{(2n-1)(2n+1)}}_{=\frac{n}{2n+1}} + \frac{1}{(2n+1)(2n+3)} $$
$$ = \frac{n}{2n+1} + \frac{1}{(2n+1)(2n+3)} $$
$$=\frac{n(2n+3) +1}{(2n+1)(2n+3)} $$
$$= \frac{2n^2 + 3n +1}{(2n+1)(2n+3)} $$
$$= \frac{(2n+1) (n+1)}{(2n+1)(2n+3)} $$
$$= \frac{n+1}{2n+3}.$$
Therefore, the statement is true for $n+1 \in \mathbb{N}$. By the axiom of mathematical induction, the statement is true for every natural number $n$.
The principle of the mathematical induction is applicable in many cases, and to prove various inequalities and divisibility of numbers.
Example 3. Prove that for all natural numbers such that $n \ge 3$ is valid:
$$3 ^n > 2^n + 3n.$$
Solution:
The statement is obviously true for $n=3$, because $3^3 > 2^3 + 3 \cdot 3$, that is $27 > 11$.
Suppose that the statement is true for some natural number $n$, that is
$$ 3 ^n > 2^n + 3n.$$
We need to prove that the statement is also true for $n+1 \in \mathbb{N}$, that is
$$3^{n+1} > 2^{n+1} + 3 (n+1).$$
By multiplying $3 ^n > 2^n + 3n$ with $3$ we obtain:
$$3^{n+1} > 3 \cdot (2^n + 3n),$$
that is,
$$3^{n+1} > 3 \cdot 2^n + 3n + 6n.$$
Because $3 >2$ and $6n > 3$, for every natural number from the previous inequality follows:
$$3^{n+1} > 2 \cdot 2^n + 3n +3,$$
that is,
$$3^{n+1} > 2^{n+1} + 3 (n+1).$$
Therefore, the statement is true for $n+1 \in \mathbb{N}$. By the axiom of the mathematical induction the statement is true for every natural number $n \ge 3$.
Example 4. Prove that number
$$19 | 5 ^{2n+1} \cdot 2^{n+2} + 3^{n+2} \cdot 2^{2n+1}$$
is divisible by $19$, $\forall n \in \mathbb{N}$.
Solution:
For $n=1$ we have:
$$5^{2\cdot1 +1} \cdot 2^{1+2} + 3^{1+2} \cdot 2^{2\cdot 1 + 1} =$$
$$= 5^3\cdot 2^3 + 3^3 \cdot 2^3$$
$$ = 125 \cdot 8 + 27 \cdot 8 = 1000 + 216 = 1216.$$
It follows that $19 | 1216$, therefore, the statement is true for $n=1$.
Suppose that for some $n \in \mathbb{N}$ the following is true:
$$19 | 5 ^{2n+1} \cdot 2^{n+2} + 3^{n+2} \cdot 2^{2n+1}.$$
We need to prove that for $$n+1 $$ the following is true:
$$19 | 5 ^{2(n+1)+1} \cdot 2^{(n+1)+2} + 3^{(n +1)+2} \cdot 2^{2(n+1)+1},$$
that is
$$19 | 5 ^{2n+3} \cdot 2^{(n+3} + 3^{n +3} \cdot 2^{2n+3}.$$
Then, by using the assumption, we have:
$$5 ^{2n+3} \cdot 2^{(n+3} + 3^{n +3} \cdot 2^{2n+3} = 12 \underbrace{( 5^{2n+1}\cdot 2^{n+2} + 3^{n+2} \cdot 2^{2n+1})}_{19|} + \underbrace{2 \cdot 19 \cdot 5^{2n+1} \cdot 2^{n+2}}_{19|}.$$
$$19 | 5 ^{2n+3} \cdot 2^{(n+3} + 3^{n +3} \cdot 2^{2n+3},$$
so the statement is true for $n+1 \in \mathbb{N}$. By the axiom of mathematical induction, the statement is true for $\forall n \in \mathbb{N}$.
Example 5.
Prove that $\forall n \in \mathbb{N}$ , $n>2$ the following inequality is valid:
$$\frac{1}{n} + \frac{1}{n+1} + \frac{1}{n+2} + \cdots + \frac{1}{2n} < 1.$$
Solution:
The left side of inequality we will denote as $A_n$ , that is
$$A_n = \frac{1}{n} + \frac{1}{n+1} + \frac{1}{n+2} + \cdots + \frac{1}{2n}.$$
We need to prove that the statement is true $\forall n \in \mathbb{N}, n >2$, therefore, in basis we have $n=3$.
For $n=3$ we have
$$A_3 = \frac{1}{3} + \frac{1}{4} + \frac{1}{5} < 1,$$
so the statement is true for $n=3$.
Suppose that the statement is true for some $n \in \mathbb{N}$.
We need to prove that the statement is also true for $n+1 \in \mathbb{N}$, that is
$$A_{n+1} < 1.$$
We will observing the difference between two consecutive adjacent members:
$$A_n = \frac{1}{n} + \frac{1}{n+1} + \frac{1}{n+2} + \cdots + \frac{1}{2n},$$
$$A_{n+1} =\frac{1}{n} + \frac{1}{n+1} + \frac{1}{n+2} + \cdots + \frac{1}{2n} + \frac{1}{2n +1} + \frac{1}{2n+2} .$$
It follows
$$A_{n+1} – A_{n} = \frac{1}{2n+1} + \frac{1}{2n+2} – \frac{1}{n} \cdot \frac{2}{2} $$
$$= \frac{1}{2n+1} + \frac{1}{2n+2} – \frac{1}{2n} – \frac{1}{2n} $$
$$=\underbrace{\left( \frac{1}{2n+1} – \frac{1}{2n} \right)}_{<0} + \underbrace{\left( \frac{1}{2n+2} – \frac{1}{2n} \right)}_{<0} < 0. $$
We obtain that $ A_{n+1}+ A_{n} < 0$, that is $A_{n+1} < A_{n}$.
By applying the assumption we have:
$$A_{n+1} < 1.$$
Therefore, the statement is true for $n+1 \in \mathbb{N}$.
The statement is true for $n=3$, and the assumption that the statement is true for some $n \in \mathbb{N}$ implies that the statement is also true for $ n +1 \in \mathbb{N}$, by the axiom of mathematical induction it follows that the statement is true $\forall n \in \mathbb{N}$ , $n >2$.
Example 6.
Prove that $\forall n \in \mathbb{N}$ the following is valid:
$$\cos \frac{x}{2} \cdot \cos \frac{x}{2^2} \cdot \ldots \cdot \cos \frac{x}{2^n} = \frac{\sin x}{ 2^n \cdot \sin \frac{x}{2^n}}.$$
Solution:
For $n=1$ we have
$$\frac{\sin x }{2\cdot \sin \frac{x}{2}}= \frac{\sin 2 \cdot \frac{x}{2}}{2 \cdot \sin \frac{x}{2}} = $$
$$=\frac{2 \cdot \sin \frac{x}{2} \cdot \cos \frac{x}{2}}{2 \cdot \sin \frac{x}{2}} = \cos \frac {x}{2}.$$
Therefore, the statement is true for $n=1$.
Suppose that the statement is true for some $ n \in \mathbb{N}$:
$$\cos \frac{x}{2} \cdot \cos \frac{x}{2^2} \cdot \ldots \cdot \cos \frac{x}{2^n} = \frac{\sin x}{ 2^n \cdot \sin \frac{x}{2^n}}.$$
We must prove that the statement is also true for $ n+1 \in \mathbb{N}$, that is:
$$\cos \frac{x}{2} \cdot \cos \frac{x}{2^2} \cdot \ldots \cdot \cos \frac{x}{2^n} \cdot \cos \frac{x}{2^{n+1}} = \frac{\sin x}{2^{n+1} \cdot \sin \frac{x}{2^{n+1}}}.$$
By applying the assumption it follows:
$$\underbrace{\cos \frac{x}{2} \cdot \cos \frac{x}{2^2} \cdot \ldots \cdot \cos \frac{x}{2^n}}_{= \frac{\sin x}{2^n \cdot \sin \frac{x}{2^n}}} \cdot \cos \frac{x}{2^{n+1}} =$$
$$=\frac{\sin x}{2^n \cdot \sin \frac{x}{2^n}} \cdot \cos \frac{x}{2^{n+1}} $$
$$= \frac{\sin x}{ 2^n \cdot \sin 2\cdot \frac{x}{2^{n+1}}}. $$
Now we use the double angle formula for sine ($ \sin 2x = 2 \sin x \cdot \cos x$). Therefore, we have:
$$\cos \frac{x}{2} \cdot \cos \frac{x}{2^2} \cdot \ldots \cdot \cos \frac{x}{2^n} \cdot \cos \frac{x}{2^{n+1}} =$$
$$= \frac{\sin x}{2 ^n \cdot 2 \sin \frac{x}{2^{n+1}} \cdot \cos \frac{x}{2^{n+1}}} \cdot \cos \frac{x}{2^{n+1}} $$
$$= \frac{\sin x}{2^{n+1} \cdot\sin \frac{x}{2^{n+1}}}. $$
The statement is true for $n+1 \in \mathbb{N}$, so by the principle of the mathematical induction, the statement is true $\forall n \in \mathbb{N}$.
Example 7.
Prove that $\cos \frac{\pi}{2^n}$ is irrational number $\forall n \in \mathbb{N}$, $n \ge 2$.
Solution:
For $n=2$ we have
$$ \cos \frac{\pi}{4} = \frac{\sqrt{2}}{2}.$$
$\sqrt{2}$ is irrational number $\Rightarrow \frac{\sqrt{2}}{2}$ is irrational number. Therefore, the statement is true for $n =2$.
Suppose that for some $n \in \mathbb{N}$ the statement is true, that is, for some $n \in \mathbb{N}$ the number $\cos \frac{\pi}{2^n}$ is irrational.
We need to prove that the statement is true for $n+1 \in \mathbb{N}$, that is, for $ n+1 \in \mathbb{N}$ the number $\cos \frac{\pi}{2^{n+1}}$ is irrational.
By using the half angle formula for cosine, we have:
$$\cos \frac{\pi}{2^{n+1}} = \cos \left ( \frac{1}{2} \cdot \frac{\pi}{2^n}\right) = \pm \sqrt{\frac{1 + \cos \frac{\pi}{2^n}}{2}}$$
$$ = \pm \frac{1}{\sqrt{2}} \cdot \sqrt{1 + \cos \frac{\pi}{2^n}}.$$
Let’s assume the opposite, that is $\pm \frac{1}{\sqrt{2}} \cdot \sqrt{1 + \cos \frac{\pi}{2^n}}$ is the rational number.
Let $x = \pm \frac{1}{\sqrt{2}} \cdot \sqrt{1 + \cos \frac{\pi}{2^n}}, \quad x \in \mathbb{Q}$.
After squaring we obtain
$$x^2 = \frac{1 + \cos \frac{\pi}{2^n}}{2} $$
$$ \Longrightarrow 2 x^2 = 1 + \cos \frac{\pi}{2^n},$$
that is
$$\underbrace{2 x^2 -1}_{\in \mathbb{Q}} = \underbrace{\cos \frac{\pi}{2^n}}_{\in \mathbb{I}}$$
which is the contradiction. Therefore, $\cos \frac{\pi}{2^n}$ is an irrational number for $\forall n \in \mathbb{N}$ such that $n \ge 2$.
