×

# Wanna practice Induction ?

The principle of mathematical induction is a very very useful tool in many proofs, and also in proving some useful formulas. $$\color{Red}{\text{The principle states that any given set of positive integers}}$$ has ALL natural numbers if it follows the following conditions -

$$(i)$$ The first natural number, i.e. $$1$$ is in the set.

$$(ii)$$ Whenever the integer $$k$$ is in the set, then $$k+1$$ is also in the set.

This looks so obvious, see that if you have been given the two statements simultaneously, then by using $$(ii)$$ on $$(i)$$, you can say that $$2$$ is in the set. Then again applying the statement $$(ii)$$ for $$2$$, we say that $$(3)$$ will be in the set, so on.

$$\color{Blue}{\textbf{Thus if you prove a certain result for 1}}$$ , $$\color{Blue}{\textbf{and then assume that the result is true}}$$ for $$k$$, just prove that it is true for $$k+1$$ and you're done !

Same thing you can do for 0, then prove for whole numbers !!!

Problems for practice:-

Prove that the following results hold $$\forall n \in \mathbb{N}$$

$$(a) \displaystyle \sum_{k=0} ^n 2^k = 2^{n+1}-1$$

$$(b) \displaystyle \sum_{k=1} ^n k = \dfrac{n(n+1)}{2}$$

$$(c) \displaystyle \sum_{k=1} ^n k^2 = \dfrac{n(n+1)(2n+1)}{6}$$

$$(d) \displaystyle \sum_{k=1}^n k^3 = \biggl( \sum_{k=0} ^n k \biggr) ^2$$

$$(e) \displaystyle 24 \mid 2\cdot 7^n + 3\cdot 5^n -5$$

$$(f) \displaystyle 1\cdot 2+2\cdot 3+3\cdot 4+ .... + n(n+1) = \dfrac{n(n+1)(n+2)}{3}$$

I felt like sharing because though it's very well known to all, I am willing to find some good level problems for practicing this foundation builder concept once more... $$\color{Green}{\text{Isn't this a good revision ?}}$$

Note by Aditya Raut
2 years, 8 months ago

Sort by:

I actually haven't tried $$(d)$$ and $$(f)$$ before since doing math XD

Here's the solution for $$(e)$$ if someone got stuck.

$$2\times 7^{m+1} + 3 \times 5^{m+1} - 5$$

$$= 2\times 7^{m}\times 7 + 3\times 5^{m}\times 5 - 5$$

$$= 14\times 7^{m} + 15 \times 5^{m} - 5$$

$$= 12\times 7^{m} + 12\times 5^{m} + 2\times 7^{m} + 3\times 5^{m} - 5$$

$$= 12(7^{m} + 5^{m}) + 24k$$ for some $$k$$

$$= 24n + 24k$$ for some $$n$$ · 2 years, 8 months ago

@Aditya Raut this is really a nice note for practice...... could you please add more divisibility kinda problems to give a more diverse experience to readers? ........ thanks :) · 2 years, 8 months ago

Here is some additional problems I found on the internet: http://staffhome.ecm.uwa.edu.au/~00021149/Academy/1995/inductionprobs.pdf · 2 years, 8 months ago

Thanks - they look like a good selection of induction problems · 2 years, 2 months ago

@Aditya Raut Can you add these to the Induction Wiki page? Thanks! Staff · 2 years, 5 months ago

$$(a)$$ Base Case $$n = 1$$

$$\displaystyle \sum_{k = 0}^{1}2^{k} = 3$$

$$2^{n+1} - 1 = 3$$

True.

Propose it is true $$\forall n \in N$$

Then it must be true for $$n + 1$$

$$\displaystyle\sum_{k = 0}^{n+1}2^{k} = \sum_{k = 0}^{n}2^{k} + 2^{n+1}$$

Substituting the value from our proposal,

$$\sum_{k = 0}^{n}2^{k} + 2^{n+1} = 2^{n+1} - 1 + 2^{n+1}= 2^{n+2} - 1$$

Thus, $$LHS = RHS$$

Thus, $$LHS = RHS \forall n \in N$$

Sorry for ugly arrangement. · 2 years, 8 months ago

A good level problem is here: Fro every positive integer $$n$$, prove that $$\sqrt{(4n+1)}<\sqrt n +\sqrt{(n+1)}<\sqrt{(4n+2)}$$. Hence or otherwise, prove that [$$\sqrt{n}+\sqrt{n+1}$$]=[$$\sqrt{4n+1}$$] where [.] denotes floor function. It is an IITJEE problem. · 1 year, 12 months ago

/(good/) · 2 years, 2 months ago

What is e) ?... in d) second summation is it k=0 or k=1 ? Nice collection. · 2 years, 5 months ago

And e) means prove that for all positive integers $$n$$, $$(2\cdot 7^n + 3\cdot 5^n -5)$$ is divisible by $$24$$.

$$a\mid b$$ is the symbol of "a divides b" or "b is divisible by a".

Latex code for the symbol $$\mid$$ is "\mid" · 2 years, 5 months ago

Thanks. I did not get it since I did not assume the parenthesis. · 2 years, 5 months ago

Thanks, but Just think ! Will adding $$0$$ make any change? In that summation, starting from $$k=0$$ will yield same thing as starting with $$k=1$$, won't it ? @Niranjan Khanderia · 2 years, 5 months ago

Thanks. · 2 years, 5 months ago