Proof by mathematical induction


To do a proof by mathematical induction, follow the following steps exactly as shown and in the order given:






Step # 1:

Show it is true for n = 1, n = 2, .......

Step # 2:

Suppose it is true for n = k

Step # 3:

Prove it is true for n = k + 1

Important notes and explanations about a proof by mathematical induction:

In Step # 1, you are trying to show it is true for specific values. You are free to do this test with just one value or fifty values of your choice or more.

However, showing it is true for one million values or more still does not prove it will be true for all values. This is a very important observation!

In Step # 2, since you have already shown that it is true for one or more values, it is logical to suppose or assume it is true for n =k or generally speaking.

We usually use the asumption that we make here to complete or prove Step # 3

In Step # 3, you finally show it is true for any values. Notice that step #2 did not show it is true for any values.

Example:

Show that for all n, 2 + 4 + 6 + ... + 2n = n ( n + 1)

Step # 1:

Show the equation is true for n = 1, n = 2, .......

There is a pitfall to avoid here.

n = 1 means the first value of the expression on the left side. In this case 2

n = 2 means the first two values of the expression on the left side. In this case 2 + 4

n = 3 means the first three values of the expression on the left side. In this case 2 + 4 + 6

Thus, showing the equation 2 + 4 + 6 + ... + 2n = n ( n + 1) is true for n = 4 means that we have to show that 2 + 4 + 6 + 8 = 4 (4 + 1)

2 + 4 + 6 + 8 = 6 + 6 + 8 = 12 + 8 = 20 and 4 (4 + 1) = 4 × 5 = 20

Since the left side is equal to the right side (20 = 20) , step # 1 is done. It is not necessary to choose other values although you could do it just for fun and to prove to yourself that it will work for other values.



Step # 2:

Suppose the equation is true for n = k

Just replace n by k.

2 + 4 + 6 + ... + 2k = k ( k + 1)

Step # 3:

Prove the equation is true for n = k + 1

This is the toughest part of proof by mathematical induction. Things can get really tricky here. Not in this problem though!

At this point, you need to write down what it means for the equation to be true for n = k + 1

Be careful! Just because you wrote down what it means does not mean that you have proved it. This is another pitfall to avoid when working on a proof by mathematical induction.

Here is what it means:

After you replace k by k+1, you get :

2 + 4 + 6 + ... + 2 × (k + 1) = k+1 ( k + 1 + 1)

2 + 4 + 6 + ... + 2 × ( k + 1) = k+1 ( k + 2)

2 + 4 + 6 + ... + 2 × ( k + 1) = ( k + 1 ) × ( k + 2)

Let's give you a recap because you may have lost tract of what we are trying to do here.

We have not proved anything yet. The equation 2 + 4 + 6 + ... + 2 × ( k + 1) = ( k + 1 ) × ( k + 2) is just what it means for the equation to be true for n = k + 1

We are now ready to complete the proof by mathematical induction by using the hypothesis in step # 2.

starting with the hypothesis, 2 + 4 + 6 + ... + 2k = k ( k + 1)

Say to yourself, " What does the next term look like? "

Since the last term now is 2k, the next term should be 2 × ( k + 1)

Add 2 × ( k + 1) to both sides of the hypothesis

2 + 4 + 6 + ... + 2k + 2 × ( k + 1) = k ( k + 1) + 2 × ( k + 1)

                                                = k2 + k + 2k + 2

                                                 = k2 + 3k + 2

Since 2 = 1 × 2 and 1 + 2 = 3,

k2 + 3k + 2 = ( k + 1) × ( k + 2)

Therefore, 2 + 4 + 6 + ... + 2k + 2 × ( k + 1) = ( k + 1) × ( k + 2) and the proof by mathematical induction is complete!

The above is a well explained and solid proof by mathematical induction. Study it well!





Recent Articles

  1. Linear Parent Function

    Nov 20, 17 11:18 AM

    What is a linear parent function? Crystal clear explanation.

    Read More

New math lessons

Your email is safe with us. We will only use it to inform you about new math lessons.

            Follow me on Pinterest





Recent Lessons

  1. Linear Parent Function

    Nov 20, 17 11:18 AM

    What is a linear parent function? Crystal clear explanation.

    Read More

  Our Top Pages

Formula for percentage

Compatible numbers

Basic math test

Basic math formulas

Types of angles

Math problem solver

Algebra word problems

Surface area of a cube

Finding the average 

Scale drawings

Tough Algebra Word Problems.

If you can solve these problems with no help, you must be a genius!


Everything you need to prepare for an important exam!

K-12 tests, GED math test, basic math tests, geometry tests, algebra tests. 


Real Life Math Skills

Learn about investing money, budgeting your money, paying taxes, mortgage loans, and even the math involved in playing baseball.

 Recommended

Scientific Notation Quiz

Types of Angles Quiz

Graphing Slope Quiz

Adding and Subtracting Matrices Quiz  

Factoring Trinomials Quiz 

Solving Absolute Value Equations Quiz  

Order of Operations Quiz