Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

In strong induction, the inductive hypothesis assumes that for all k, P(k) is true. A lot of the proofs I've come across just take this as an assumption.

Why then, in some other cases, is it necessary to provide several base cases instead of just assuming that P(k) is true in each of those base cases?

For instance, the claim, every amount of postage that is at least 12 cents can be made from 4-cent and 5-cent stamps. Why is it necessary to show the base cases up to 16 cents rather than just starting at P(k=16) and saying suppose 12 <= k is all true?

share|improve this question

2 Answers 2

Strong induction is often used where there is a recurrence relation, i.e. $a_{n} = a_{n-1}-a_{n-2}$. In this situation, since 2 different steps are needed to work with the given formula, you need to have at least 2 base cases to avoid any holes in your proof. Proving it works for $n=1$ doesn't help since if you try to use the relation for $n=2$ you get an undefined $a_{-1}$ term.

share|improve this answer

For the example given only normal vanilla “weak” induction is needed. Normal induction does not have to start from zero or 1, but can prove a proposition upward from any integer, for example n! > 2^n for n> 3: assume true then (n+1)! = (n+1).n! > 2.n! (for n > 3) > 2.2^n (by assumption) = 2^n+1. So, if the proposition is true for n (>3) then it is true for n+1. The base case here is n=4 and 24 > 16 so the base case is true, induction applies and the proposition is therefore true for all n > 3.

In your example, induction can easily be used to prove that for n > 14 we can express n as a combination of 4’s and 5’s: assume true then if n contains a 4 in its expression we can change it to a 5 to express n+1; otherwise n is expressed only in 5’s and must contain 3 of them at least, so we can change three 5’s to four 4’s to express n+1. The base case here is 15 which is expressed as exactly three 5’s so the base case is true, induction applies and the proposition is therefore true for n > 14. By examination of individual cases, we can extend the range: 14 = 5 + 5 + 4, 13 = 4 + 4 + 5; 12 = 4 + 4 + 4; 11 is not expressible as a combination of 4’s and 5’s.

So, any number from 12 up is expressible as a combination of 4’s and 5’s where we provide specific proofs for 12, 13, 14, and 15 (the base case) and an inductive proof for anything greater. You could use “strong induction” to prove this but it would come to the same thing. Strong induction can also start from numbers other than zero or 1. Here we need to prove that for all numbers n > 11 if all numbers (> 11) up to n n can be expressed as a combination of 4’s and 5’s then so can n+1. The obvious way to do this is to split the proof for n > 14 and separately for n = 12, 13, 14 and proceed as above.

The favourite example for strong induction is that all integers (> 1) can be expressed as a product of primes. This is true for 2 (base case): suppose true for all integers up to n, then either n + 1 is prime or consists of two factors which are < n and in which case n + 1 is the product of two sets of primes and so always n + 1 can be expressed as a product of primes. This proof actually uses the power of strong induction in factoring n + 1 in to ANY two numbers < n, not just relying on the truth of the proposition for n itself.

share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.