Mathematical Induction is a method of proof typically used to establish that a given statement is true for all natural numbers. This is often the first type of proof statement seen by a high school student.
First Principle of Finite Induction
Let be a set of positive integers with the following properties:
(1) The integer 1 belongs to the set.
(2) Whenever the integer is in , then the next integer must also be in .
Then is the set of all positive integers.
This statement seems almost immediately obvious, and it can be proved by contradiction. Often, an analogy is drawn with a sequence of falling dominos; if the first domino falls, and each subsequent domino pushes it's neighbor, then all dominos in this sequence must eventually fall. For now, we will focus on how to prove statements by induction. These proofs often have a standard format that can be followed, as shown below:
Statement: Let be the proposition Induction Hypothesis, for in Domain.
Base Case: Consider Base Case.
LHS=LHS
RHS=RHS
Since LHS=RHS, thus Base Case is true.Induction step: Assume is true for some in Domain. Consider .
LHS =use Induction Hypothesis =RHS .
Hence is true implies that is true.Conclusion: By Mathematical Induction, since Base Case is true and is true implies is true, thus is true for all in Domain.
There are 4 main components in the proof, and you have to fill in the details of the various parts left in italics. Let us work through a specific example, to get a better sense of how this works.
1. Show that for all positive integers ,
Solution: This is a well known statement about the sum of the first squares, and we will show this via induction.
Statement: Let be the proposition that , for all positive integers.
[We have stated what the Induction Hypothesis is, and specified the domain in which the statement is true.]
Base Case: Consider .
LHS= .
RHS= .
Since LHS=RHS, thus the Base Case is true.[We have identified the Base Case, and shown that it is true.]
Induction Hypothesis: Assume is true for some positive integer . Consider .
Hence is true implies that is true.[We successfully used the induction hypothesis (in the 3rd equation) along with algebraic manipulation to show that the next statement is true.]
Conclusion: By Mathematical Induction, since is true and is true implies is true, thus is true for all positive integer .
[We now sit back and drink a cup of coffee.]
2. Show that for all positive integers , is a multiple of 64.
Solution: Statement: Let be the proposition that is a multiple of 64, for all positive integers .
Base Case: Consider .
Since , it is a multiple of 64.
Hence, the Base case is true.Induction Hypothesis: Assume is true for some positive integer . Consider .
. Since is a multiple of 64, and the first term is a multiple of 64 by the Induction Hypothesis, hence the LHS is a multiple of .
Hence is true implies that is true.Conclusion: By Mathematical Induction, since is true and is true implies is true, thus is true for all positive integer .
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:
*italics*
or_italics_
**bold**
or__bold__
paragraph 1
paragraph 2
[example link](https://brilliant.org)
> This is a quote
\(
...\)
or\[
...\]
to ensure proper formatting.2 \times 3
2^{34}
a_{i-1}
\frac{2}{3}
\sqrt{2}
\sum_{i=1}^3
\sin \theta
\boxed{123}
Comments
Nice note!BTW how to add these white boxes or blockquotes in notes?
Log in to reply
Simply add a ">" to the start of the paragraph. I've edited your comment so you can use that as a reference. If you click on "Edit", you can see how it's done.
Thanks Sir! This is my first introduction to induction.
Log in to reply
For more information, check out the Induction wikis
Log in to reply
Going through them, Sir.
Sir, could I copy content from this Note to show the format of a proof by Induction here?
Log in to reply
Log in to reply
here which contains your topic i think.
Did you made a new wiki or it existed previously? If you made a new one, then i have to say there is oneLog in to reply
Log in to reply
You didn't study it in 11?
Log in to reply
I'll be going to class 11 this April.
Log in to reply
Log in to reply
Log in to reply
Log in to reply