Mathematical deduction and mathematical induction

Name: Espera Pax
Who is asking: Student
Level: Secondary

Question:
What are mathematical deduction and mathematical induction, and what is the difference between them?

Hi Espera,

Deduction is drawing a conclusion from something known or assumed. This is the type of reasoning we use in almost every step in a mathematical argument. For example to solve 2x = 6 for x we divide both sides by 2 to get 2x/2 = 6/2 or x = 3. What we know or assume is that 2x = 6 and that you can divide both sides of an equation by any non-zero number and the equation is still valid. From these two facts we deduce that x = 3.

Mathematical induction is a particular type of mathematical argument. It is most often used to prove general statements about the positive integers. For example you could use mathematical induction to prove that for every positive integer n,

1 + 2 + 3 + ... + n = n(n + 1)/2

or that for every positive integer n,

7 divides 11ⁿ - 4ⁿ

To illustrate a proof by induction I want to prove the second statement above.

The first thing I would do, before starting a proof, is to experiment to see if the statement is reasonable.

When n = 1, 11ⁿ - 4ⁿ = 11 - 4 = 7 which is certainly divisible by 7
When n = 2, 11² - 4² = 121 - 16 = 105 = 7*15
When n = 3, 11³ - 4³ = 1331 - 64 = 1267 = 7*181

Mathematical induction is a way show how to "keep going".

Proof by mathematical induction proceeds in two steps.

Step 1 Show the statement "7 divides 11ⁿ - 4ⁿ" is true when n = 1. That we have already done, when n = 1, 11ⁿ - 4ⁿ = 11 - 4 = 7 which is certainly divisible by 7 Step 2 (this is called the inductive step) Suppose that the statement "7 divides 11ⁿ - 4ⁿ" is true for some particular value of n. What you need to show is that it is also true for the next value of n. So suppose that the statement is true for the value n = k, that is suppose that 7 divides 11^k - 4^k. You have to prove that 7 divides 11^k+1 - 4^k+1.

       11^k+1 - 4^k+1
   = 11*11^k - 4*4^k
   = (7 + 4)*11^k - 4*4^k
   = 7*11^k + 4*11^k - 4*4^k
   = 7*11^k + 4(11^k - 4^k)

7 divides 7*11^k and, by assumption, 7 divides 11^k - 4^k, thus 7 divides 11^k+1 - 4^k+1

It follows that for any positive integer n, 7 divides 11ⁿ - 4ⁿ

I hope this helps,
Harley Go to Math Central