SEARCH HOME
Math CentralQuandaries & Queries

search

Question from iris, a student:

we have some confusion in our problem. Please help us.
We would like to know "the principle of mathematical induction"
(i) for n=1, p(1) is true.
(ii) assume that for n=k>=1, p(k) is true we have to prove p(k+1) is true. Here (Is n=k>=1 true? or Is n=k.1 true?)
Thanks.

We have two responses for you

The statement of your questions may have a misleading misprint in it, however, you are assuming that for some k ≥ 1 that you know p(k) is true. In essence that you have checked out p(n) for n = 1 all the way up to n = k, and now you want to use that information (that p(k) is true) to deduce the truth of the statement for n = k+1. The most common error I see from students is a statement like " we've checked p(1) is true, now assume p(n) is true for n ≥ 1"; that says assume that it's true for all n, which is what you're trying to prove.

Penny

 

Iris,

The Principle of Mathematical Induction is a theorem. It goes like this.

Suppose you have a statement that involves the integer n. Let's call it p(n).
If you know:

  1. that the statement is true is true when n=1 (that is p(1) is true), and

  2. that for every k >= 1, IF the statement is true when n=k then it is also true when n=k+1 (that is if p(k) is true then p(k+1) is true),

then you can conclude that the statement is true for every integer n greater than or equal to 1.

Normally a proof by induction has four main parts:

  1. Basis. Here you check that the statement is true when n=1.

  2. Induction Hypothesis. Here you write down that you are assuming the statement is true when n=k, for SOME k >= 1.

  3. Induction Step. Here you argue that if the induction hypothesis is true then the statement is also true when n=k+1.

  4. Conclusion. Here you say that having carried out the three steps above, the Principle of Mathematical Induction implies that the statement is true for all integers n >= 1.

For a longer explanation and some examples, try looking at
http://www.math.uvic.ca/faculty/gmacgill/guide/induction.pdf

Victoria

About Math Central
 

 


Math Central is supported by the University of Regina and The Pacific Institute for the Mathematical Sciences.
Quandaries & Queries page Home page University of Regina PIMS