Mathematical Induction

Summary

LearnNext Video

Table of Contents[Show]

A statement that has a definite truth value that is, true or false, is called a mathematical statement.

Deductive reasoning involves logical steps to arrive upon a particular case from a general case. Inductive reasoning is the counter-part of deductive reasoning.

This is commonly used in mathematics, where collecting and analysing data is the norm.

This is a process of establishing general principles from particular cases.

In mathematics, we come across many mathematical statements, formulae and theorems that cannot be proved directly.

The principle used to prove mathematical statements, formulae and results involving positive integers, is called the principle of mathematical induction.

To prove mathematical statements through the induction method, certain principles have to be followed. The basic principle behind mathematical induction is that if a statement is true, then the statement that follows the first statement is also true, and so on.

Let P(n) be a statement, where n is a natural number, such that:

The statement is true for n = 1 or P(n) is true.

If the statement is true for n = k, where k is a positive integer, then the statement is also true for n = k + 1.

P(k) is true ⇒ P(k + 1) is true. This is also referred as the inductive step.

Assuming the statement is true for n = k in the inductive step is called inductive hypothesis.

Then, P(n) is true for all natural numbers n.

Principle one is a statement of fact, while principle two is a condition.

If P(n) is true for all n ≥ 2, then step 1 starts from n = 2 and we verify the result of P(2).

If the second principle is true for n = k, then it is also true for n = k + 1.

Ex:

1 + 3 + 5 + ........ + (2n-1) = n²

P(n): 1 + 3 + 5 + ........... + (2n-1) = n²

n = 1,2,3,....

P(1):1 = 1²

Thus, P(1) is true.

This statement can be considered as a fact.

Now, take n equal to two.

P(2):1 + 3 = 4 = 2²

Thus, P(2) is true.

Next, consider n = 3.

P(3): 1 + 3 + 5

= 9 = 3²

Thus, P(3) is true.

Consider P(k) is true.

Need to prove P(k + 1) is true.

1 + 3 + 5 +.........+(2k - 1) ------- (1)

1 + 3 + 5 +.........+ (2k - 1) + [(2k + 1) - 1] = k² + [(2k + 1) - 1]

= k² + 2k + 1

=(k + 1)²

=P(k + 1)

∴ P(k + 1) is true.

Hence, P(n) is true for all natural numbersLet's begin with an example.

Example: A Sum Formula

Theore. For any positive integer n, 1 + 2 + ... + n = n(n+1)/2.

Proof. (Proof by Mathematical Induction) Let's let P(n) be the statement "1 + 2 + ... + n = (n (n+1)/2." (The idea is that P(n) should be an assertion that for any n is verifiably either true or false.) The proof will now proceed in two steps: the initial step and theinductive step.

Initial Step. We must verify that P(1) is True. P(1) asserts "1 = 1(2)/2", which is clearly true. So we are done with the initial step.

Inductive Step. Here we must prove the following assertion: "If there is a k such that P(k) is true, then (for this same k) P(k+1) is true." Thus, we assume there is a k such that 1 + 2 + ... + k = k (k+1)/2. (We call this the inductive assumption.) We must prove, for this same k, the formula 1 + 2 + ... + k + (k+1) = (k+1)(k+2)/2.

This is not too hard: 1 + 2 + ... + k + (k+1) = k(k+1)/2 + (k+1) = (k(k+1) + 2 (k+1))/2 = (k+1)(k+2)/2. The first equality is a consequence of the inductive assumption.

The Math Induction Strategy

Mathematical Induction works like this: Suppose you want to prove a theorem in the form "For all integers n greater than equal to a, P(n) is true". P(n) must be an assertion that we wish to be true for all n = a, a+1, ...; like a formula. You first verify the initial step. That is, you must verify that P(a) is true. Next comes the inductive step. Here you must prove "If there is a k, greater than or equal to a, for which P(k) is true, then for this same k, P(k+1) is true."

Since you have verified P(a), it follows from the inductive step that P(a+1) is true, and hence, P(a+2) is true, and hence P(a+3) is true, and so on. In this way the theorem has been proved.

Example: A Recurrence Formula

Math induction is of no use for deriving formulas. But it is a good way to prove the validity of a formula that you might think is true. Recurrence formulas are notoriously difficult to derive, but easy to prove valid once you have them. For example, consider the sequence a₀, a₁, a₂, ... defined by a₀ = 1/4 and a_n+1 = 2 a_n(1-a_n) for n ≥ 0.

Theorem. A formula for the sequence a_n defined above, is a_n = (1 - 1/2^2ⁿ)/2 for all n greater than or equal to 0.

Proof. (By Mathematical Induction.)

Initial Step. When n = 0, the formula gives us (1 - 1/2^2ⁿ)/2 = (1 - 1/2)/2 = 1/4 = a₀. So the closed form formula ives us the correct answer when n = 0.

Inductive Step. Our inductive assumption is: Assume there is a k, greater than or equal to zero, such that a_k = (1 - 1/2^{2^k})/2. We must prove the formula is true for n = k+1.

First we appeal to the recurrsive definition of a_k+1 = 2 a_k(1-a_k). Next, we invoke the inductive assumption, for this k, to get

a_k+1 = 2 (1 - 1/2^{2^k})/2 (1 - (1 - 1/2^{2^k})/2) = (1 - 1/2^{2^k})(1 + 1/2^{2^k})/2 = (1 - 1/2^{2^k+1})/2. This completes the inductive step.

Exercises

Prove each of the following by Mathematical Induction.

For all positive integers n, 1² + 2² + ... + n² = (n)(n+1)(2n+1)/6.

Define a sequence a₀, a₁, a₂ by the recurrsive formula a_n+1 = 2 a_n - a_n². Then, a closed form formula for a_n is a_n = 1 - (1 - a₀)^2ⁿ for all n = 0, 1, 2, ..

MATHEMATICAL INDUCTION

The principle of mathematical induction

THE NATURAL NUMBERS are the counting numbers: 1, 2, 3, 4, etc.Mathematical induction is a technique for proving a statement -- a theorem, or a formula -- that is asserted about every natural number.

By "every", or "all," natural numbers, we mean any one that we might possibly name.

For example,

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

This asserts that the sum of consecutive numbers from 1 to n is given by the formula on the right. We want to prove that this will be true forn = 1, n = 2, n = 3, and so on. Now we can test the formula for any givennumber, say n = 3:

1 + 2 + 3 = ½· 3· 4 = 6

-- which is true. It is also true for n = 4:

1 + 2 + 3 + 4 = ½· 4· 5 = 10.

But how are we to prove this rule for every value of n?

The method of proof is the following. It is called the principle of mathematical induction.

If

	1)	when a statement is true for a natural number n = k, then it will also be true for its successor, n = k + 1;

and

	2)	the statement is true for n = 1;

then the statement will be true for every natural number n.

To prove a statement by induction, we must prove parts 1) and 2) above. For, when the statement is true for n = 1, then according to 1), it will also be true for 2. But that implies it will be true for 3; which implies it will be true for 4. And so on. It will be true for any natural number that we might name.

The hypothesis of Step 1) -- "The statement is true for n = k" -- is called the induction assumption, or the induction hypothesis. It is what weassume when we prove a theorem by induction.

Example 1. Prove that the sum of the first n natural numbers is given by this formula:

1 + 2 + 3 + . . . + n

n(n + 1)
2

Proof. We will do Steps 1) and 2) above. First, we will assume that the formula is true for n = k; that is, we will assume:

1 + 2 + 3 + . . . + k

k(k + 1)
2

. (1)

This is the induction assumption. Assuming this, we must prove that the formula is true for its successor, n = k + 1. That is, we must show:

1 + 2 + 3 + . . . + (k + 1)

(k + 1)(k + 2)
2

. (2)

To do that, we will simply add the next term (k + 1) to both sides of the induction assumption, line (1):

This is line (2), which is the first thing we wanted to show.

Next, we must show that the formula is true for n = 1. We have:

1 = ½· 1· 2

-- which is true. We have now fulfilled both conditions of the principle of mathematical induction. The formula is therefore true for every natural number.

(In the Appendix to Arithmetic, we will establish that formula directly.)

Example 2. Prove that this rule of exponents is true for every natural number n:

(ab)n = anbn.

Proof. Again, we begin by assuming that it is true for n = k; that is, we assume:

(ab)k = akbk . . . . . . . . (3)

With this assumption, we must show that the rule is true for its successor, n = (k + 1). We must show:

(ab)k + 1 = ak + 1bk + 1. . . . . . . (4)

(When using mathematical induction, the student should always write exactly what is to be shown.)

Now, given the assumption, line (3), how can we produce line (4) from it ?

Simply by mu

Mathematical Induction

Mathematical Induction (MI) is an extremely important tool in Mathematics.

First of all you should never confuse MI with Inductive Attitude in Science. The latter is just a process of establishing general principles from particular cases.

MI is a way of proving math statements for all integers (perhaps excluding a finite number) [1] says:

Statements proved by math induction all depend on an integer, say, n. For example,

(1) 1 + 3 + 5 + ... + (2n - 1) = n²
(2) If x₁, x₂, ..., x_n > 0 then (x₁ + x₂ + ... + x_n)/n ≥ (x₁·x₂·...·x_n)^1/n

etc. n here is an "arbitrary" integer.

It's convenient to talk about a statement P(n). For (1), P(1) says that 1 = 1² which is incidently true. P(2) says that 1 + 3 = 2², P(3) means that 1 + 3 + 5 = 3². And so on. These particular cases are obtained by substituting specific values 1, 2, 3 for n into P(n).

Assume you want to prove that for some statement P, P(n) is true for all n starting with n = 1. ThePrinciple (or Axiom) of Math Induction states that, to this end, one should accomplish just two steps:

Prove that P(1) is true.
Assume that P(k) is true for some k. Derive from here that P(k+1) is also true.

The idea of MI is that a finite number of steps may be needed to prove an infinite number of statements P(1), P(2), P(3), ....

Let's prove (1). We already saw that P(1) is true. Assume that, for an arbitrary k, P(k) is also true, i.e. 1 + 3 + ... + (2k-1) = k². Let's derive P(k+1) from this assumption. We have

1 + 3 + ... + (2k-1) + (2k+1)	= [1 + 3 + ... + (2k-1)] + (2k+1)
	= k² + (2k+1)
	= (k+1)²

Which exactly means that P(k+1) holds. (For 2k+1 = 2(k+1)-1.) Therefore, P(n) is true for all n starting with 1.

Intuitively, the inductive (second) step allows one to say, look P(1) is true and implies P(2). Therefore P(2) is true. But P(2) implies P(3). Therefore P(3) is true which implies P(4) and so on. Math induction is just a shortcut that collapses an infinite number of such steps into the two above.

In Science, inductive attitude would be to check a few first statements, say, P(1), P(2), P(3), P(4), and then assert that P(n) holds for all n. The inductive step "P(k) implies P(k + 1)" is missing. Needless to say nothing can be proved this way.

Remark

Often it's impractical to start with n = 1. MI applies with any starting integer n₀. The result is then proved for all n from n₀ on.
Sometimes, instead of 2., one assumes 2':
Assume that P(m) is true for all m < (k + 1).

Derive from here that P(k+1) is also true. The two approaches are equivalent, because one may consider statement Q: Q(n) = P(1) and P(2) and ... and P(n), so that Q(n) is true iff P(1), P(2), ..., P(n) are all true.

This variant goes by the name of Complete Induction or Strong Induction.

In problem Strong inductions differ from valid deductions in one important way: in the induction, the conclusion contains information that was not contained in the premises. This is the source of the uncertainty of inductions. (Conversely, deductions are certain because they tautologously restate their premises.) Inductions are strengthened as confirming instances pile up. But they can never bring certainty unless every possible case is actually examined, in which case they become deductions. Despite our experience with 100 greasy coffee shop burgers, the next one might be dry and rubbery.

"Mathematical induction" is unfortunately named, for it is unambiguously a form of deduction. However, it has certain similarities to induction which very likely inspired its name. It is like induction in that it generalizes to a whole class from a smaller sample. In fact, the sample is usually a sample of one, and the class is usually infinite. Mathematical induction is deductive, however, because the sample plus a rule about the unexamined cases actually gives us information about every member of the class. Hence the conclusion of a mathematical induction does not contain more information than was latent in the premises. Mathematical inductions therefore conclude with deductive certainty.

You are probably quite sure that every even number is divisible by 2. But you have never examined every even number, and nobody else has either. So how do you know that some very big even number won't violate this rule? Why isn't the situation analogous to the coffee shop burgers? In both cases, aren't we moving from known cases to unknown cases?

The reason why the even numbers are decisively different from coffee shop burgers lies in the logic of mathematical induction. We can prove that the smallest even number (namely, 2) is divisible by 2. This is our very small sample. And we can prove that the next even number after every number divisible by 2 will also be divisible by 2. This is our rule about the unexamined cases. That is enough to imply that the successor of 2, namely 4, will be divisible by 2, and its successor, 6, and its successor 8... and so on ad infinitum. This is how a small sample and a rule about unexamined cases can give us information about every case. This is how our knowledge of an infinite set of unexamined cases can be as certain as the conclusion of a valid deduction, quite unlike the conclusion of an ordinary induction.

The large-scale structure of a proof by mathematical induction is fairly simple.

The theorem is true of the sample. (This requires a separate proof.)
A rule tells us that if it is true of the sample, then it is true of the unexamined members of a certain class. (This rule requires a separate proof.)
Therefore, the theorem is true of all the members of a certain class.

Here's how the inference looks when described in the special terminology of mathematical induction.

Basis. Prove that the theorem holds for the minimal case.
Induction step. Prove that the property of complying with the theorem is "hereditary" and extends to all the successors of the minimal case.
- The induction step is the proof of a conditional statement, namely, "if the theorem is true of the ancestor case, then it is true of the descendant cases." The if-clause of this conditional statement, asserting that the theorem is true of the ancestor case, is called the induction hypothesis.
Conclusion. Together, #1 and #2 imply that the theorem holds for all possible cases, i.e., the minimal case and all its successors. If you didn't use the true minimal case in step #1, then you prove only that the

indian economy

Tuesday, 6 January 2015