Proof by Induction: Step by Step [With 10+ Examples]

The method of mathematical induction is used to prove mathematical statements related to the set of all natural numbers. For the concept of induction, we refer to our page “an introduction to mathematical induction“. One has to go through the following steps to prove theorems, formulas, etc by mathematical induction.

Steps of Induction

Proofs by induction: Note that the mathematical induction has $4$ steps. Let P(n) denote a mathematical statement where $n \geq n_0.$ To prove P(n) by induction, we need to follow the below four steps.

1. Base Case: Check that P(n) is valid for $n=n_0.$
2. Induction Hypothesis: Suppose that P(k) is true for some $k \geq n_0.$
3. Induction Step: In this step, we prove that P(k+1) is true using the above induction hypothesis.
4. Conclusion: If the above three steps are satisfied, then by the mathematical induction we can conclude that P(n) is true for all integers $n \geq n_0.$

Let us see how we use the above steps of induction to prove formulas, equations, theorems, and many more.

Solved Problems: Prove by Induction

Problem 1: Prove that $2n+1<2^n$ for all natural numbers $n \geq 3$

Solution: Let P(n) denote the statement 2n+1<2ⁿ

Base case: Note that 2.3+1 < 2³. So P(3) is true.

Induction hypothesis: Assume that P(k) is true for some k $\geq$ 3. So we have 2k+1<2^k.

Induction step: To show P(k+1) is true.

Now, 2(k+1)1

= 2k+2+1 =(2k+1)+2

< 2^k + 2, by induction hypothesis.

< 2^k + 2^k  as $k \geq 3$

=2 . 2^k

=2^k+1

So k+1 < 2^k+1. It means that P(k+1) is true.

Conclusion: We have shown that P(k) implies P(k+1). Hence by mathematical induction, we conclude that P(n) is true for all integers n $\geq$ 3. In other words, 2n+1 < 2ⁿ is proved.

 

Problem 2: Prove that $2^{2n}-1$ is always a multiple of $3$

Solution: Let P(n) denote the statement: $2^{2n}-1$ is a multiple of $3.$

Base case: Put $n=1.$ Note that $2^{2.1}-1$ $=4-1=3,$ which is a multiple of $3.$ So P(1) is true.

Induction hypothesis: Assume that P(k) is true for some $k \geq 1.$ So we have $2^{2k}-1$ is a multiple of $3.$ In other words, we have $2^{2k}-1=3t$ for some integer $t.$ 

Induction step: To show P(k+1) is true, that is, $2^{2(k+1)}-1$ is a multiple of 3.

Now, $2^{2(k+1)}-1$

$=2^{2k+2}-1$

$=2^{2k}\cdot 2^2-1$

$=4\cdot 2^{2k}-1$

$=3 \cdot 2^{2k}+2^{2k}-1$

$=3\cdot 3^{2k}+3t,$ by induction hypothesis.

$=3(2^{2k}+t),$ which is clearly divisible by $3.$

It follows that $2^{2(k+1)}-1$ is a multiple of $3,$ that is,  P(k+1) is true.

Conclusion: We have shown that P(k) implies P(k+1). Hence by mathematical induction, we conclude that P(n) is true for all integers $n \geq 1.$ In other words, we have proven $2^{2n}-1$ is a multiple of $3$ for all natural numbers $n.$

Also Read:

Surds: We discuss the definition of surds with their orders, properties, types, and a few solved examples.

Indices: Click here for the definition, and laws of indices with some solved examples.

Logarithm: The definition of logarithm with their rules, and formulas are discussed here with a few solved examples.

Arithmetic Progression (AP): Definition, Formula, Sum, N-th term, and Common difference with Solved Examples.

Geometric Progression (GP): Definition, Formula, Sum, N-th term, and Common difference with Solved Examples.

 

Problem 3: By mathematical induction, prove that $4^n+15n-1$ is divisible by $9$ for all $n \in \mathbb{N}$

Solution: Let P(n) denote the statement: 4ⁿ+15n-1 is divisible by 9.

Base case: Put $n=1.$ Note that $4^1+15.1-1$ $=4+15-1$ $=18,$ which is a multiple of $3.$ So P(1) is true.

Induction hypothesis: Assume that P(k) is true for some $k \geq 1.$ So $4^n+15n-1$ is divisible by $9.$ In other words, we have $4^k+15k-1$ $=9t$ for some integer $t.$

Induction step: To show P(k+1) is true, that is, 4^k+1+15(k+1)-1 is divisible by 9.

Now, $4^{k+1}+15{k+1}-1$

$=4\cdot 4^k+15k+15-1$

$=4\cdot 4^k+60k-4-45k+18$

$=4(4^k+15k-1)-9(5k-2)$

$=4\cdot 9t -9(5k-2),$ by induction hypothesis

$=9(t-5k+2),$ which is clearly divisible by $9.$

It follows that 4^k+1+15(k+1)-1 is divisible by 9, that is,  P(k+1) is true.

Conclusion: We have shown that P(k) implies P(k+1). Hence by mathematical induction, we conclude that P(n) is true for all integers $n \geq 1.$ In other words, we have proven 4ⁿ+15n-1 is divisible by 9 for all natural numbers n.

 

Problem 4: Prove that $n^2<n!$ for all integers $n \geq 4$

Solution: Let P(n) denote the statement: n²<n!

Base case: Put $n=4.$ Note that $4^2<4!=24.$ So P(4) is true.

Induction hypothesis: Assume that P(k) is true for some k $\geq$ 4. So k²<k!

Induction step: To show P(k+1) is true, that is, (k+1)²<(k+1)!

Claim: We claim that (k+1)²<k²(k+1)

As k $\geq$ 4, we have $k-\frac{1}{2} \geq 4-\frac{1}{2}=\frac{7}{2}$

Squaring, we get $(k-\frac{1}{2})^2 \geq \frac{49}{4}$ $\cdots$ (I)

Now, $k^2-(k+1)$

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

$=(k-\frac{1}{2})^2-\frac{5}{4}$

$\geq \frac{49}{4}-\frac{5}{4}>0$, by (I)

$\Rightarrow k+1<k^2$

As $k+1 \geq 0$, we deduce $(k+1)^2<k^2(k+1)$ $\cdots$ (II). This proves our claim.

Now by induction hypothesis, 

$k^2<k!$ when $k \geq 4$

$\Rightarrow k^2(k+1)<k! \times (k+1)$

$\Rightarrow k^2(k+1)< (k+1)!$ $\cdots$ (III)

Combining (II) and (III), we get that

$(k+1)^2<k^2(k+1)<(k+1)!$

∴ $(k+1)^2<(k+1)!$ Thus, P(k+1) is true.

Conclusion: We have shown that P(k) implies P(k+1). Hence by mathematical induction, we conclude that P(n) is true for all integers n $\geq$ 4. In other words, we have proven n²<n! for all natural numbers $n \geq 4$.

 

Problem 5: For real numbers x and y, prove that (xy)n=xnyn for all natural numbers n.

Solution: Let P(n) denote the statement: (xy)ⁿ=xⁿyⁿ

Base case: Put n=1. See that (xy)¹=x¹y¹=xy. So P(1) is true.

Induction hypothesis: Assume that P(k) is true for some $k \geq 1.$ So we have $(xy)^k=x^k y^k.$

Induction step: To show P(k+1) is true, that is, (xy)^k+1=x^k+1y^k+1

Now, $(xy)^{k+1}$

$=(xy)^k\cdot xy$

$=x^ky^k \cdot xy$, by induction hypothesis.

$=(x^k \cdot x)(y^k \cdot y)$, by the commutative and associative property of real numbers.

$=x^{k+1}y^{k+1}$

It means that P(k+1) is true.

Conclusion: We have shown that P(k) implies P(k+1). Hence by mathematical induction, we conclude that P(n) is true for all integers n $\geq$ 1. In other words, $(xy)^n=x^ny^n$ for all natural numbers n.

 

Problem 6: By mathematical induction, prove that $7^{2n}+2^{3(n-1)}. 3^{n-1}$ is divisible by $25.$

Solution: Let P(n) denote the statement: $7^{2n}+2^{3(n-1)}. 3^{n-1}$ is divisible by $25.$

Base case: Put $n=1.$ Note that $7^{2.1}+2^{3(1-1)}. 3^{1-1}$ $=49+1$ $=50$ divisible by $25$. So P(1) is true.

Induction hypothesis: Assume that P(k) is true for some $k \geq 1.$ So $7^{2k}+2^{3(k-1)}. 3^{k-1}$ is divisible by $25$ and we have $7^{2k}+2^{3(k-1)}. 3^{k-1}$ $=25t$ for some integer $t.$

Induction step: To show P(k+1) is true.

Now, $7^{2(k+1)}+2^{3(k+1-1)}$ $. 3^{k+1-1}$

$=49 \cdot 7^{2k}+2^{3(k-1)+3}$ $. 3^{k-1+1}$

$=49 \cdot 7^{2k}+8\cdot 2^{3(k-1)}$ $\cdot 3\cdot  3^{k-1}$

$=49[7^{2k}+2^{3(k-1)}. 3^{k-1}]$ $-25 \cdot 2^{3(k-1)}\cdot 3^{k-1}$

$= 49 \cdot 25t-25\cdot 2^{3(k-1)}\cdot 3^{k-1},$ by induction hypothesis

$=25[49t-2^{3(k-1)}\cdot 3^{k-1}],$ which is clearly divisible by $25.$

It means that P(k+1) is true.

Conclusion: We have shown that P(1) is true and P(k) implies P(k+1). Thus by mathematical induction, we conclude that P(n) is true for all integers $n \geq 1.$ In other words, $7^{2n}+2^{3(n-1)}. 3^{n-1}$ is divisible by $25$ for all natural numbers n.

 

Problem 7: For an odd positive integer, using mathematical induction prove that $x^n+y^n$ is always divisible by $x+y.$

Solution: Let P(n) denote the statement: $x^n+y^n$ is always divisible by $x+y$ for odd positive integers $n.$ As $n$ is odd, we write $n=2m+1.$ 

Let P(m) denote the statement: $x^{2m+1}+y^{2m+1}$ is divisible by $x+y$ for all integers $m \geq 0.$ To show P(n) is true it is enough to show that P(m) is true. Thus, we will prove P(m) by mathematical induction

Base case: For $m=0,$ see that $x^{2m+1}+y^{2m+1}$ is divisible by $x+y.$ So P(1) is true.

Induction hypothesis: Assume that P(k) is true for some $k \geq 0.$ So $x^{2k+1}+y^{2k+1}$ is divisible by $x+y$ and we have $x^{2k+1}+y^{2k+1}$ $=(x+y)f(x,y)$ for some function $f(x,y).$

$\Rightarrow x^{2k+1}$ $=(x+y)f(x,y)$ $-y^{2k+1}$ $\cdots (\star)$

Induction step: To show P(k+1) is true.

Now, $x^{2(k+1)+1}+y^{2{k+1}+1}$

$=x^2 x^{2k-1}+y^2y^{2k-1}$

$=x^2[(x+y)f(x,y)-y^{2k-1}]$ $+y^2y^{2k-1}$, by $(\star)$

$=x^2(x+y)f(x,y)$ $-y^{2k-1}(x^2-y^2)$

$=(x+y)[x^2f(x,y)-$ $(x-y)y^{2k-1}],$ which is clearly divisible by $x+y$

It means that P(k+1) is true.

Conclusion: We have shown that P(1) is true and P(k) implies P(k+1). Thus by mathematical induction, we conclude that P(m) is true for all integers $m \geq 0.$ This implies that P(n) is true, that is, $x^n+y^n$ is always divisible by $x+y$ for all odd positive numbers n.

 

Problem 8: Prove that $\frac{n^5}{5}+$ $\frac{n^3}{3}+$ $\frac{7n}{15}$ is a whole number.

Solution: Let P(n) denote the statement: $\dfrac{n^5}{5}+\dfrac{n^3}{3}+\dfrac{7n}{15}$ is an integer.

Base case: Put $n=1.$ We have

$\dfrac{1^5}{5}+\dfrac{1^3}{3}+\dfrac{7.1}{15}$

$=\dfrac{1}{5}+\dfrac{1}{3}+\dfrac{7}{15}$

$=\dfrac{3+5+7}{15}$

$=1,$ which is an integer.

So P(1) is true.

Induction hypothesis: Assume that P(k) is true for some $k \geq 1.$ So $\dfrac{k^5}{5}+\dfrac{k^3}{3}+\dfrac{7k}{15}$ is an integer. 

Induction step: To show P(k+1) is true.

Now, $\dfrac{(k+1)^5}{5}+\dfrac{(k+1)^3}{3}+\dfrac{7(k+1)}{15}$

$=\frac{1}{5}(k^5+5k^4+10k^3+10k^2+$ $5k+1)+\frac{1}{3}(k^3+3k^2$ $+3k+1)$$+\frac{7}{15}(k+1)$

$=(\frac{k^5}{5}+\frac{k^3}{3}+\frac{7k}{15})$ $+k^4+2k^3+2k^2+k+\frac{1}{5}$ $+k^2+k+\frac{1}{3}+\frac{7}{15}$ 

$=(\frac{k^5}{5}+\frac{k^3}{3}+\frac{7k}{15})$ $+k^4+2k^3+3k^2+2k+1,$ which is an integer (by induction hypothesis).

It means that P(k+1) is true.

Conclusion: It is shown that P(k) implies P(k+1). Thus by mathematical induction, we conclude that P(n) is true for all integers $n \geq 1.$ In other words, $\frac{n^5}{5}+\frac{n^3}{3}+\frac{7n}{15}$ is an integer, for all natural numbers.

 

Problem 9: Using mathematical induction, prove that $2.2+3.2^2+4.2^3+\cdots$ $+(n+1).2^n$ $=n.2^{n+1}$ for all natural numbers $n.$

Solution: Let P(n) denote the statement: $2.2+3.2^2+4.2^3+\cdots$ $+(n+1).2^n$ $=n.2^{n+1}$

Base case: Put $n=1.$ LHS= $(1+1).2^1=4=1.2^{1+1}$=RHS. So P(1) is true.

Induction hypothesis: Assume that P(k) is true for some k $\geq$ 1. So we have $2.2+3.2^2+4.2^3+\cdots$ $+(k+1).2^k$ $=k.2^{k+1}$.

Induction step: To show P(k+1) is true.

Now, $2.2+3.2^2+4.2^3+ \cdots$ $+(k+1).2^k+(k+1+1).2^{k+1}$

$= k.2^{k+1}+(k+1+1).2^{k+1},$ by induction hypothesis.

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

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

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

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

It means that P(k+1) is true.

Conclusion: It is shown that P(k) implies P(k+1). Thus by mathematical induction, we conclude that P(n) is true for all integers n $\geq$ 1. In other words, $2.2+3.2^2+4.2^3+…$ $+(n+1).2^n$ $=n.2^{n+1}$ for all natural numbers n.

 

Problem 10: By mathematical induction prove that $\sin x +\sin 3x +\cdots \sin(2n-1)x$ $=\frac{\sin^2 nx}{\sin x}$ for all natural numbers n.

Solution: Let P(n) denote the statement: sin x +sin 3x+ … +sin(2n-1)x=sin²nx/sin x.

Base case: Put $n=1.$ LHS= $\sin x$ and RHS= $\frac{\sin^2 x}{\sin x}$ $=\sin x.$ So P(1) is true.

Induction hypothesis: Assume that P(k) is true for some $k \geq 1.$ So we have that $\sin x +\sin 3x +\cdots \sin(2k-1)x$ $=\frac{\sin^2 kx}{\sin x}.$

Induction step: To show P(k+1) is true.

Now, $\sin x +\sin 3x +\cdots \sin(2k-1)x$ $+\sin(2(k+1)-1)$

$=[\sin x +\sin 3x +\cdots$ $\sin(2k-1)x]$ $+\sin(2k+1)x$

$=\dfrac{\sin^2 kx}{\sin x}+\sin(2k+1)x$, by induction hypothesis

$=\dfrac{\sin^2 kx+\sin (2k+1)x \sin x}{\sin x}$

$={\large \frac{2\sin^2 kx+2\sin (2k+1)x \sin x}{2\sin x}  }$

$=\frac{1}{2\sin x}[(1-\cos 2kx)+$ $\cos 2kx -\cos (2k+2)x]$ 

[$\because 2\sin^2a=1-\cos 2a$, $2\sin a \sin b$ $=\cos(a-b)-\cos(a+b)$]

$=\dfrac{1-\cos (2k+2)x}{2\sin x}$

$=\dfrac{2\sin^2(k+1)x}{2\sin x}$

$=\dfrac{\sin^2(k+1)x}{\sin x}$

It means that P(k+1) is true.

Conclusion: We have shown that P(k) implies P(k+1). Thus by mathematical induction, we conclude that P(n) is true for all integers $n \geq 1.$ In other words, $\sin x +\sin 3x +\cdots \sin(2n-1)x$ $=\frac{\sin^2 nx}{\sin x}$ for all natural numbers n.