• P(n) : Assertion involving ’n'

• Goal: To prove P(n) is true for all $n \in \mathbb{N}$

• This can be achieved in two steps:

Basis step

To verify P(1) is true.

Inductive step

Assume induction hypothesis: P(k) is true.

• To prove: P(k+1) is true

• ie, to prove the conditional statement.

• P(k) $\rightarrow$ P(k+1)

For a positive integer j, the $j^{th}$ harmonic number denoted $H_j$ is defined as

$H_j = 1+ \frac{1}{2} +\frac{1}{3}+ ….+\frac{1}{j}$

Prove that: $H_{2^{n}} \geq 1 + \frac{n}{2}$ $\forall n \in \N \cup \{0\} .$

Proof:

• Basis step

  • P(n)$:H_{2^{n}} \geq 1 + \frac{n}{2}$

  • To prove P(0)

  • $H_{2^{0}} = H_1 = 1 \geq 1 + \frac{0}{2}$

  • i.e P(0) is true.

• Inductive step

  • Assume that P(k) is true.

  • $H_{2^{k}} = 1+ \frac{1}{2}+ …. + \frac{1}{2^k} \\ \quad \quad \geq 1+ \frac{k}{2}$

• $\text{To prove that P(k+1) is true}$.

  • $H_{2^{k+1}} = 1+ \frac{1}{2} + …. + \frac{1}{2^{k+1}}$

  • $H_{2^{k+1}} =\biggl(1+ \frac{1}{2}+…+\frac{1}{2^{k}}\biggl)+\frac{1}{2^{k}+1}+…+\frac{1}{2^{k+1}}$

$H_{2^k} + \frac{1}{2^{k}+1}+….+ \frac {1} {2^{k+1}}$

$\Rightarrow ~ \geqq (1+\frac{k}{2}) + \underbrace{\frac{1}{2^k+1} + … + \frac{1}{2^{k+1}}}_{2^k\ \text{terms}}$

$\Rightarrow ~ 2^k+1,\ 2^k+2 …. \leq 2^{k+1}$

$\Rightarrow ~ H_{2^{k+1}} \geq(1+\frac{k}{2})$$+ \frac{1}{2^{k+1}} + \frac{1}{2^{k+1}}+ … + \frac{1}{2^{k+1}}$

$= 1 + \frac{k}{2} + 2^k. \frac{1}{2^{k+1}} = 1+\frac{k}{2}+\frac{1}{2}$

$H_{2^{k+1}}= 1+\frac{k+1}{2}$

$H_{2^{k+1}} \geq 1+ \frac{k+1}{2}$

$\text{Hence, by MI}$

$H_{2^{n}} \geq 1+ \frac{n}{2}, \quad \forall n \in \mathbb{N} \cup \{ 0 \}$

• $1 + \frac{1}{2}+ \frac{1}{3}+…+ \frac{1}{n}+ …..$

• $H_{2^{n}} \geq 1+ \frac{n}{2}$

Example:

Use MI to prove that $n^3 - n$ is divisible by 3 for every positive integer.

• Basis step to verify P(1) is true.

  • P(n): $n^3-n$ is divisible by 3.

  • P(1): $1^3-1=0$ is a multiple of 3.

• Inductive step

  • Assume P(k) is true ie, $k^3-k$ is divisible by 3.

  • $k^3 - k=3. d, \ \ d \in \mathbb{N}$

To prove P(k+1) is true.

$(k+1)^3 - (k+1) =k^3 + 3k^2 + 3k + 1 - k -1$

$=k^3 + 3k^2 + 3k - k$

$=(k^3 -k) + 3(k^2 +k)$

$=3d + 3(k^2+k)$

Thus P(k+1) is true.

$\therefore$ P(n) is true for all $n \in \mathbb{N}$

$7^{n+2} + 8^{2n+2}$ is divisible by 57 for all non negative integer n.

Proof:

P(n) : $7^{n+2}+8^{2n+1}$ is divisible by 57. We have to Prove that,

P(n) is true for all $n \in \mathbb{N} \cup \{0\}$

• Basic Step
  • To prove that P(0) is true.
  • $7^{0+2}\ +8^{2.0+1} = 7^2 + 8 =57$
  • $7^{0+2}\ +8^{2.0+1} \ \text {is divisible by} \ 57. \ i.e,\quad$ P(0) is true

• Inductive step:

  • Assume P(k) is true.
  • ie $7^{k+2} + 8^{2k+1}$ is divisible by 57.
  • $7^{k+2} + 8^{2k+1}=57.d \quad$ ($d$ is a non-negative integer.)

• To prove $7^{k+1+2} + 8^{2(k+1) + 1}$ is divisible by $57$.

  $7^{k+1+2} + 8^{2(k+1) + 1}$
  $\Rightarrow ~ 7^{k+3} + 8^{2k+3}$

  $\Rightarrow ~ 7. 7^{k+2} + 8^{2k+1} .8^2$
  $\Rightarrow ~ 7. 7^{k+2} + 64 . 8^{2k+1}$

$7^{k+1+2} + 8^{2(k+1) + 1} = 7. 7^{k+2} + 7.8^{2k+1}-7.8^{2k+1} + 64. 8^{2k+1}$

$=7(7^{k+2} + 8^{2k+1}) + 57 . 8^{2k+1}$

$=7. M(57) + 57. 8^{2k+1} \quad$ (M $\rightarrow$ multiple of 57.)

$=M(57) ~$ i.e. P(k+1) is true.

Hence by M.I, P(n) is true for all $n \in \mathbb{N} \cup \{0 \}$.

A set with n elements has $2^n$ subsets, for all non negative integer n.

Proof:

P(n) : A set with n elements has $2^n$ subsets.

• Basis step: To prove P(0) is true.

  • P(0): consider empty set $\phi$

  • Subsets are $\phi$

  • $1=2^0$ subsets are there.

• Inductive step:
  • Assume P(k) is true.
  • i.e A set with k elements has $2^k$ subsets.
• To prove P(k+1) is true.
  • consider a set $T$ with $k+1$ elements,
  • $T = S \cup \{a\}$ $\quad S \rightarrow$ A set with $k$ elements

Observe:

For a subset $X$ of $S$, $\exists \ \text{two subsets for} \ T$

1. $X$ itself
2. $X \cup \{ a \}$

$T = \{ a_1,a_2,a_3,a_4 \}$

$T = S \cup \{a \}$

$S = \{ a_1,a_3,a_4 \}$

$a=a_2$

$\phi, \ T , \{a_1\}, \{a_2\}$ $\{a_3\}, \{a_4\}, \{a_1 \ a_2\}$ ,$\{a_1 \ a_2\}…….\ \{a_1 \ a_2\ a_3\}$ , $\{a_2 \ a_3\ a_4\}\ ……$

Here $T \rightarrow S \cup a_1 \quad \{a_2\} \rightarrow \phi \cup \{a_2\}$

• $S\ has 2^k subsets$

• Hence, $2. \ 2^k \ subsets \ for \ T$

• Hence, $2^{k+1} \ subsets \ for \ T$

• $i.e \quad$ P(k+1) is true

• $\text {By mathematical induction} \ \text {P(n) is true for all n}\ n \in N \cup \{0\}.$

What is wrong with this ‘Proof’?

For every positive integer $n$,

$\sum_{i=1}^n i = \frac{(n+\frac{1}{2})^2}{2}$.

Proof:
Assume given statement is correct.

• Basis step:
  • The formula is true for n=1.
• Inductive step:
  • Suppose that $\sum_{i=1}^k i = \frac{(k+\frac{1}{2})^2}{2}.$

Then, $\sum _{i=1} ^{k+1} i = \biggl(\sum _{i=1}^k i \biggl) + (k+1)$

$=\frac{(k+\frac{1}{2})^2}{2}+k+1 \quad (\text{by inductive hypothesis}).$

$=\frac{k^2+k+\frac{1}{4}}{2} + k +1$$=\frac{k^2+3k+\frac{9}{4}}{2} =\frac{(k+\frac{3}{2})^2}{2}$

$=\frac{[(k+1) + \frac{1}{2}]^2}{2}, \ \ \text{completing the inductive step}$

Hence, by mathematical induction, for every positive integer $n$

$\sum_{i=1}^n i = \frac{(n+\frac{1}{2})^2}{2}$

Let’s verify what is wrong with this proof.

• Basis step:

  • The formula is true for n=1

• Verify basis step.

  • P(1) is not true.
  • $\therefore ~ 1 \neq \frac{(1+\frac{1}{2})^2}{2}$

P(n): All horses in a set of n horses are of same color.

What is wrong with a ‘proof’ that all horses are of same color?

Proof:

To Prove that P(n) is true for all $n$,

• Basis step:
  • clearly, P(1) is true.
• Inductive step:
  • Assume that P(k) is true.
  • i.e, all the horses in any set of k horses are of same color.

Consider any k+1 horses.

Let us number these as horses $1,2,3,…,k,k+1.$

Now the first k of these horses all must have the same color, and the last $k$ of these must have the same color.

Beacuse the set of the first k horses and the set of the last $k$ horses over lap. all $k+1$ must be of same color.

This shows P(k+1) is true.

Let’s verify what is wrong with this proof.

• Basis step is correct.
• Inductive step:
  • Assume that P(k) is true.

Mistake is in inductive step,

• The two sets do not overlap.

• If $k+1=2$

• In fact, P(1) $\rightarrow$ P(2) is false.

• Mathematical Induction

  • $\times$ inductive reasoning

  • $\checkmark$ deductive reasoning

• Well ordered principle