Waste less time on Facebook — follow Brilliant.
×

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, 6 months ago

No vote yet
1 vote

Comments

Sort by:

Top Newest

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\) Samuraiwarm Tsunayoshi · 2 years, 6 months ago

Log in to reply

@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 · 2 years, 6 months ago

Log in to reply

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

Log in to reply

@Daniel Liu Thanks - they look like a good selection of induction problems Curtis Clement · 2 years ago

Log in to reply

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

Log in to reply

\((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. Sanchayapol Lewgasamsarn · 2 years, 6 months ago

Log in to reply

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. Gautam Sharma · 1 year, 9 months ago

Log in to reply

/(good/) Samuel Ayinde · 2 years ago

Log in to reply

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

Log in to reply

@Niranjan Khanderia 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" Aditya Raut · 2 years, 3 months ago

Log in to reply

@Aditya Raut Thanks. I did not get it since I did not assume the parenthesis. Niranjan Khanderia · 2 years, 3 months ago

Log in to reply

@Niranjan Khanderia 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 Aditya Raut · 2 years, 3 months ago

Log in to reply

@Aditya Raut Thanks. Niranjan Khanderia · 2 years, 3 months 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 · 2 years, 6 months ago

Log in to reply

×

Problem Loading...

Note Loading...

Set Loading...