# 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{#D61F06}{\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{#3D99F6}{\textbf{Thus if you prove a certain result for 1}}$ , $\color{#3D99F6}{\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{#20A900}{\text{Isn't this a good revision ?}}$

5 years, 4 months ago

This discussion board is a place to discuss our Daily Challenges and the math and science related to those challenges. Explanations are more than just a solution — they should explain the steps and thinking strategies that you used to obtain the solution. Comments should further the discussion of math and science.

When posting on Brilliant:

• Use the emojis to react to an explanation, whether you're congratulating a job well done , or just really confused .
• Ask specific questions about the challenge or the steps in somebody's explanation. Well-posed questions can add a lot to the discussion, but posting "I don't understand!" doesn't help anyone.
• Try to contribute something new to the discussion, whether it is an extension, generalization or other idea related to the challenge.

MarkdownAppears as
*italics* or _italics_ italics
**bold** or __bold__ bold
- bulleted- list
• bulleted
• list
1. numbered2. list
1. numbered
2. list
Note: you must add a full line of space before and after lists for them to show up correctly
paragraph 1paragraph 2

paragraph 1

paragraph 2

[example link](https://brilliant.org)example link
> This is a quote
This is a quote
    # I indented these lines
# 4 spaces, and now they show
# up as a code block.

print "hello world"
# I indented these lines
# 4 spaces, and now they show
# up as a code block.

print "hello world"
MathAppears as
Remember to wrap math in $$ ... $$ or $ ... $ to ensure proper formatting.
2 \times 3 $2 \times 3$
2^{34} $2^{34}$
a_{i-1} $a_{i-1}$
\frac{2}{3} $\frac{2}{3}$
\sqrt{2} $\sqrt{2}$
\sum_{i=1}^3 $\sum_{i=1}^3$
\sin \theta $\sin \theta$
\boxed{123} $\boxed{123}$

Sort by:

@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 :)

- 5 years, 4 months ago

- 5 years, 3 months ago

Thanks - they look like a good selection of induction problems

- 4 years, 10 months ago

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$

- 5 years, 3 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.

- 5 years, 3 months ago

@Aditya Raut Can you add these to the Induction Wiki page? Thanks!

Staff - 5 years, 1 month ago

Nice! I'm too into creating notes and problems set for inequality :) Why not take a look at it @Aditya Raut ? :D

- 5 years, 3 months ago

What is e) ?... in d) second summation is it k=0 or k=1 ? Nice collection.

- 5 years 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

- 5 years ago

Thanks.

- 5 years 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"

- 5 years ago

Thanks. I did not get it since I did not assume the parenthesis.

- 5 years ago

/(good/)

- 4 years, 10 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.

- 4 years, 7 months ago