Maths Extension 1:Mathematics Induction

From Biki

Contents 1 Mathematical Induction Theory 2 Mathematical Induction Examples 2.1 Equations 2.2 Inequations 2.3 Divisibility Confirmation

Mathematical Induction Theory

Note: Here is a brief summary of the steps. For a full explanation, see below.

Given some result, S(n), 1) Test the result is true for n=1. 2) Assume the result is true for some integer k. 3) Prove the result is true for for k+1, using assumption in step 2. 4) Make a summary statement.

The basic idea behind mathematical induction is to prove that if something works for some integer, k, and that it also works for k+1, then, given that it works for some starting value, usually 1, it works for all integers n, where n 1.

Why? Because if it works for both k and k+1, then letting k=1, we have k=1, k+1=2, thus it also works for 2. So if we let k=2, k+1=3, it also works for 3... etc. This process repeats up to infinity for all positive integers.

Now the question is: How do you prove it works for k and k+1? Well, that's actually the only bit that involves any algebraic manipulation!

Given a statement, S(n), you follow the following steps:

Step One Test to see if S(n) is true for n=1 or 2, or some basic starting value. If it isn't, keep testing higher numbers to find one for which it is true. You shouldn't need to test over n=5.

Step Two Now, assume that the statement S(n) is true for some positive integer, k. We don't know what this integer is, but we will assume that the statement is true just for it. Now write out S(k), which essentially means replace all the n's with k's.

Step Three Now, let us test to see whether the statement, S(n) is true for some positive integer k+1. If it IS true, then ASSUMING S(k) is true, and assuming S(n) is true for some basic starting value (step 1), then we have proven that S(n) is true for all positive integers greater than or equal to the starting value. To do that; to test for k+1, we substitute k+1 for n in the statement S(n).

Typically there is an RHS and an LHS for the statement. You write out the statement which you are looking to prove, with the RHS equating to the LHS, then you split the two sides up and manipulate each side so that eventually the two are identical and you can confidently say that LHS does equal RHS. Now, since this is a proof, you should avoid treating it like an equation. Stay away from performing manipulations on both sides, such as multiplying by (x+1) or taking the square root of both sides, etc.

The last note is that for this to be an inductive proof, you will need to use your assumption in your proof of k+1. If you manage to prove it without this, then you don't even need induction.

Step Four You've done all the hard work. Now you must make a summary paragraph to explain it. These vary from person to person, but something to the effect of "Thus, if S(n) is true for S(k), it is also true for S(k+1), but since it is true for n=1 (or whatever the starting value is), then it must also be true for n=2, 3, 4, 5... etc. Thus S(n) is true for all natural numbers, by the principle of mathematical induction."

Mathematical Induction Examples

Several types of problem exist. For now, I will cover problems involving equations, inequations and multiples of.

Equations

Typically you are given an identity, and asked to prove the it is indeed true.

Inequations

Divisibility Confirmation

Sometimes you will be asked to confirm that an expression will always be divisible by something. Typically 'something' will be a constant, such as 5 or 12. But sometimes 'something' is another expression, such as x+1.

Example One: "Show by mathematical induction that 7ⁿ + 2 is divisible by 3."

1) S(n): 7ⁿ + 2 is divisible by 3. Testing for n=0:

LHS: 7⁰ + 2 = 3, which is a muliple of 3. Thus it works for n=0.

2) Assume that S(n) is true for some positive integer, k:

S(k): 7^k + 2 = 3M [we equate S(k) to some unknown which is a multiple of three, since we are assuming this is so.]

Let us just rearrange this assumption so it is more clear 7^k = 3M - 2

3) Prove that S(k+1) is true, assuming S(k) is true:

7^k+1 + 2 = 7.7^k + 2 = 7.(3M-2) + 2 = 21M - 14 + 2 = 21M - 12 = 3(7M-4) which is divisible by 3.

4) Thus it is true for all n0, by mathematical induction. #

Example Two: "Use mathematical induction to show that for all positive integer values of n, n2, the expression (x+1)ⁿ - nx - 1 is divisible by x²."

1) S(n): (x+1)ⁿ - nx - 1 is divisible by x². Testing for n=2:

LHS: (x+1)² - 2x - 1 = x² + 2x + 1 - 2x - 1 = x², which is divisible by x². Thus it works for n=2.

2) Assume that S(n) is true for some positive integer, k:

S(k): (x+1)^k - kx - 1 = Mx² (x+1)^k = Mx² + kx + 1

3 Prove that S(k+1) is true, assuming S(k) is true:

(x+1)^k+1 - (k+1)x - 1 = (x+1)(x+1)^k - kx - x - 1 = (x+1)(Mx² + kx + 1) - kx - x - 1

(x+1)(Mx² + kx + 1) - kx - x - 1 = Mx³ + kx² + x + Mx² + kx + 1 - kx - x - 1 = Mx³ + kx² + Mx²

Mx³ + kx² + Mx² = x²(Mx + k + M), which is divisible by x².

4) Thus it is true for all n2, by mathematical induction. #

---

This page is a stub and is incomplete.

Why not add to it? Don't be intimidated - we welcome all contributions!