Wanna practice Induction ?

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

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

(ii)(ii) Whenever the integer kk is in the set, then k+1k+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)(ii) on (i)(i), you can say that 22 is in the set. Then again applying the statement (ii)(ii) for 22, we say that (3)(3) will be in the set, so on.

Thus if you prove a certain result for 1\color{#3D99F6}{\textbf{Thus if you prove a certain result for 1}} , and then assume that the result is true\color{#3D99F6}{\textbf{and then assume that the result is true}} for kk, just prove that it is true for k+1k+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 nN\forall n \in \mathbb{N}

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

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

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

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

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

(f)12+23+34+....+n(n+1)=n(n+1)(n+2)3(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... Isn’t this a good revision ?\color{#20A900}{\text{Isn't this a good revision ?}}

Note by Aditya Raut
5 years, 4 months ago

No vote yet
1 vote

  Easy Math Editor

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.
  • Stay on topic — we're all here to learn more about math and science, not to hear about your favorite get-rich-quick scheme or current world events.

MarkdownAppears as
*italics* or _italics_ italics
**bold** or __bold__ bold

- bulleted
- list

  • bulleted
  • list

1. numbered
2. 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 1

paragraph 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×3 2 \times 3
2^{34} 234 2^{34}
a_{i-1} ai1 a_{i-1}
\frac{2}{3} 23 \frac{2}{3}
\sqrt{2} 2 \sqrt{2}
\sum_{i=1}^3 i=13 \sum_{i=1}^3
\sin \theta sinθ \sin \theta
\boxed{123} 123 \boxed{123}

Comments

Sort by:

Top Newest

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

Abhinav Raichur - 5 years, 4 months ago

Log in to reply

Here is some additional problems I found on the internet: http://staffhome.ecm.uwa.edu.au/~00021149/Academy/1995/inductionprobs.pdf

Daniel Liu - 5 years, 3 months ago

Log in to reply

Thanks - they look like a good selection of induction problems

Curtis Clement - 4 years, 10 months ago

Log in to reply

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

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

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

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

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

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

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

=24n+24k = 24n + 24k for some nn

Samuraiwarm Tsunayoshi - 5 years, 3 months ago

Log in to reply

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

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

2n+11=32^{n+1} - 1 = 3

True.

Propose it is true nN\forall n \in N

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

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

Substituting the value from our proposal,

k=0n2k+2n+1=2n+11+2n+1=2n+21\sum_{k = 0}^{n}2^{k} + 2^{n+1} = 2^{n+1} - 1 + 2^{n+1}= 2^{n+2} - 1

Thus, LHS=RHSLHS = RHS

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

Sorry for ugly arrangement.

Sanchayapol Lewgasamsarn - 5 years, 3 months ago

Log in to reply

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

Calvin Lin Staff - 5 years, 1 month ago

Log in to reply

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

Priyansh Sangule - 5 years, 3 months ago

Log in to reply

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

Niranjan Khanderia - 5 years ago

Log in to reply

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

Aditya Raut - 5 years ago

Log in to reply

Thanks.

Niranjan Khanderia - 5 years ago

Log in to reply

And e) means prove that for all positive integers nn, (27n+35n5)(2\cdot 7^n + 3\cdot 5^n -5) is divisible by 2424.

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

Latex code for the symbol \mid is "\mid"

Aditya Raut - 5 years ago

Log in to reply

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

Niranjan Khanderia - 5 years ago

Log in to reply

/(good/)

samuel ayinde - 4 years, 10 months ago

Log in to reply

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

Gautam Sharma - 4 years, 7 months ago

Log in to reply

×

Problem Loading...

Note Loading...

Set Loading...