Mathematical Induction

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 SS be a set of positive integers with the following properties:
(1) The integer 1 belongs to the set.
(2) Whenever the integer kk is in SS, then the next integer k+1k+1 must also be in SS.
Then SS 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 PnP_{n} be the proposition Induction Hypothesis, for nn in Domain.

Base Case: Consider Base Case.
LHS=LHS
RHS=RHS
Since LHS=RHS, thus Base Case is true.

Induction step: Assume PkP_{k} is true for some kk in Domain. Consider Pk+1P_{k+1}.
LHS Pk+1P_{k+1} =use Induction Hypothesis =RHS Pk+1P_{k+1}.
Hence PkP_{k} is true implies that Pk+1P_{k+1} is true.

Conclusion: By Mathematical Induction, since Base Case is true and PkP_{k} is true implies Pk+1P_{k+1} is true, thus PnP_{n} is true for all nn in Domain. \square

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.

Worked Examples

1. Show that for all positive integers nn,

i=1ni2=n(n+1)(2n+1)6. \sum_{i=1} ^n i^2 = \frac {n(n+1)(2n+1)} {6}.

Solution: This is a well known statement about the sum of the first nn squares, and we will show this via induction.

Statement: Let PnP_{n} be the proposition that i=1ni2=n(n+1)(2n+1)6 \sum_{i=1} ^n i^2 = \frac {n(n+1)(2n+1)} {6}, 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 n=1n=1.
LHS= i=1112=1 \sum_{i=1} ^ 1 1^2 = 1 .
RHS= 1×(1+1)×(2+1)6=1 \frac{ 1 \times (1+1) \times (2 + 1) } {6} = 1 .
Since LHS=RHS, thus the Base Case is true.

[We have identified the Base Case, and shown that it is true.]

Induction Hypothesis: Assume PkP_k is true for some positive integer kk. Consider Pk+1P_{k+1} .
LHS Pk+1=i=1k+1i2=(i=1ki2)+(k+1)2=k(k+1)(2k+1)6+(k+1)2=(k+1)(2k2+k6+6(k+1)6)=(k+1)2k2+7k+66=(k+1)(k+2)(2k+3)6=RHS Pk+1\begin{aligned} \mbox{LHS } P_{k+1} & = \sum_{i=1}^{k+1} i^2 \\ & = \left( \sum_{i=1}^k i^2 \right) + (k+1) ^2 \\ & = \frac{ k(k+1)(2k+1) } { 6} + (k+1) ^2 \\ & = (k+1) \left( \frac{ 2k^2 + k } { 6} + \frac{ 6 (k+1) } { 6} \right) \\ & = (k+1) \frac{ 2k^2 + 7k + 6 } { 6} \\ & = \frac { (k+1) (k+2) ( 2k + 3) }{6} \\ & = \mbox{RHS } P_{k+1} \\ \end{aligned} Hence PkP_{k} is true implies that Pk+1P_{k+1} 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 P1P_1 is true and PkP_{k} is true implies Pk+1P_{k+1} is true, thus PnP_{n} is true for all positive integer nn. \square

[We now sit back and drink a cup of coffee.]

 

2. Show that for all positive integers nn, 32n+1+40n33^{2n+1}+40n-3 is a multiple of 64.

Solution: Statement: Let PnP_n be the proposition that 32n+1+40n33^{2n+1}+40n-3 is a multiple of 64, for all positive integers nn.

Base Case: Consider n=1n = 1 .
Since 33+403=64 3^{3} + 40 - 3 = 64 , it is a multiple of 64.
Hence, the Base case is true.

Induction Hypothesis: Assume PkP_k is true for some positive integer kk. Consider Pk+1P_{k+1} .
32k+3+40(k+1)3=9×(32k+1+40k3)320k+64 3^{2k+3} + 40(k+1) - 3 = 9 \times ( 3^{2k+1} + 40k - 3 ) -320k + 64 . Since 320k+64=64(5k+1) -320k+ 64 = 64 ( -5k + 1) 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 6464.
Hence PkP_{k} is true implies that Pk+1P_{k+1} is true.

Conclusion: By Mathematical Induction, since P(1)P(1) is true and PkP_{k} is true implies Pk+1P_{k+1} is true, thus PnP_{n} is true for all positive integer nn. \square

#Algebra #MathematicalInduction #ProofTechniques #Olympiad

Note by Calvin Lin
7 years, 2 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

Nice note!BTW how to add these white boxes or blockquotes in notes?

Calvin Edit. You just add a ">" at the start. thanks

Gautam Sharma - 6 years, 2 months ago

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.

Calvin Lin Staff - 6 years, 2 months ago

Thanks Sir! This is my first introduction to induction.

User 123 - 6 years, 2 months ago

Log in to reply

For more information, check out the Induction wikis

Calvin Lin Staff - 6 years, 2 months ago

Log in to reply

Going through them, Sir.

User 123 - 6 years, 2 months ago

Sir, could I copy content from this Note to show the format of a proof by Induction here?

User 123 - 6 years, 2 months ago

Log in to reply

@User 123 yes i think you can as you are filling a wiki.Good luck

Gautam Sharma - 6 years, 2 months ago

Log in to reply

@Gautam Sharma Did you made a new wiki or it existed previously? If you made a new one, then i have to say there is one here which contains your topic i think.

Gautam Sharma - 6 years, 2 months ago

Log in to reply

@Gautam Sharma Didn't understand. As in the topic was there as part of the constituent wikis under Induction, but it is empty.

User 123 - 6 years, 2 months ago

Log in to reply

@User 123 So it existed previously then go ahead and complete your wiki. You can also write on Proof of mathematical induction wiki.

Gautam Sharma - 6 years, 2 months ago

You didn't study it in 11?

Gautam Sharma - 6 years, 2 months ago

Log in to reply

I'll be going to class 11 this April.

User 123 - 6 years, 2 months ago

Log in to reply

@User 123 Oh sorry i thought you were in 11 as your age shown here is 16.

Gautam Sharma - 6 years, 2 months ago

Log in to reply

@Gautam Sharma I am 16. But I grew up in Calcutta till Class 3 and there, when one is 17, one is in Class 11. When I came to Delhi, I obviously could not skip Class 4 and directly go to Class 5.

User 123 - 6 years, 2 months ago

Log in to reply

@User 123 Haaha you will be surprised to know I skipped class 6 .I was admitted in school 1 yr later than other kids but i skipped 6 hence we were at same stage again.

Gautam Sharma - 6 years, 2 months ago

Log in to reply

@Gautam Sharma Wow!

User 123 - 6 years, 2 months ago
×

Problem Loading...

Note Loading...

Set Loading...