**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 \(S\) be a set of positive integers with the following properties:

(1) The integer 1 belongs to the set.

(2) Whenever the integer \(k\) is in \(S\), then the next integer \(k+1\) must also be in \(S\).

Then \(S\) 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 \(P_{n}\) be the propositionInduction Hypothesis, for \(n\) inDomain.

Base Case:ConsiderBase Case.

LHS=LHS

RHS=RHS

Since LHS=RHS, thusBase Caseis true.

Induction step:Assume \(P_{k}\) is true for some \(k\) inDomain. Consider \(P_{k+1}\).

LHS \(P_{k+1}\) =use Induction Hypothesis=RHS \(P_{k+1}\).

Hence \(P_{k}\) is true implies that \(P_{k+1}\) is true.

Conclusion:By Mathematical Induction, sinceBase Caseis true and \(P_{k}\) is true implies \(P_{k+1}\) is true, thus \(P_{n}\) is true for all \(n\) inDomain. \( \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 \(n\),

\[ \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 \(n\) squares, and we will show this via induction.

Statement:Let \(P_{n} \) be the proposition that \( \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=1\).

LHS= \( \sum_{i=1} ^ 1 1^2 = 1 \).

RHS= \( \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 \(P_k\) is true for some positive integer \(k\). Consider \(P_{k+1} \).

\(\begin{align} \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{align} \) Hence \(P_{k}\) is true implies that \(P_{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 \(P_1\) is true and \(P_{k}\) is true implies \(P_{k+1}\) is true, thus \(P_{n}\) is true for all positive integer \(n\). \( \square\)[We now sit back and drink a cup of coffee.]

## 2. Show that for all positive integers \(n\), \(3^{2n+1}+40n-3\) is a multiple of 64.

Solution:

Statement:Let \(P_n\) be the proposition that \(3^{2n+1}+40n-3\) is a multiple of 64, for all positive integers \(n\).

Base Case:Consider \(n = 1 \).

Since \( 3^{3} + 40 - 3 = 64 \), it is a multiple of 64.

Hence, the Base case is true.

Induction Hypothesis:Assume \(P_k\) is true for some positive integer \(k\). Consider \(P_{k+1} \).

\( 3^{2k+3} + 40(k+1) - 3 = 9 \times ( 3^{2k+1} + 40k - 3 ) -320k + 64 \). Since \( -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 \(64\).

Hence \(P_{k}\) is true implies that \(P_{k+1}\) is true.

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

## Comments

Sort by:

TopNewestThanks Sir! This is my first introduction to induction. – Ishan Dasgupta Samarendra · 1 year, 9 months ago

Log in to reply

– Gautam Sharma · 1 year, 9 months ago

You didn't study it in 11?Log in to reply

– Ishan Dasgupta Samarendra · 1 year, 9 months ago

I'll be going to class 11 this April.Log in to reply

– Gautam Sharma · 1 year, 9 months ago

Oh sorry i thought you were in 11 as your age shown here is 16.Log in to reply

– Ishan Dasgupta Samarendra · 1 year, 9 months ago

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.Log in to reply

– Gautam Sharma · 1 year, 9 months ago

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.Log in to reply

– Ishan Dasgupta Samarendra · 1 year, 9 months ago

Wow!Log in to reply

Induction wikis – Calvin Lin Staff · 1 year, 9 months ago

For more information, check out theLog in to reply

here? – Ishan Dasgupta Samarendra · 1 year, 9 months ago

Sir, could I copy content from this Note to show the format of a proof by InductionLog in to reply

– Gautam Sharma · 1 year, 9 months ago

yes i think you can as you are filling a wiki.Good luckLog in to reply

here which contains your topic i think. – Gautam Sharma · 1 year, 9 months ago

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

– Ishan Dasgupta Samarendra · 1 year, 9 months ago

Didn't understand. As in the topic was there as part of the constituent wikis under Induction, but it is empty.Log in to reply

– Gautam Sharma · 1 year, 9 months ago

So it existed previously then go ahead and complete your wiki. You can also write on Proof of mathematical induction wiki.Log in to reply

– Ishan Dasgupta Samarendra · 1 year, 9 months ago

Going through them, Sir.Log in to reply

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

– Gautam Sharma · 1 year, 9 months agoLog in to reply

– Calvin Lin Staff · 1 year, 9 months ago

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.Log in to reply