Induction proof

Question

Suppose a store sells cans of soda in packs of three and packs of four. Prove

by induction on n that for every integer n ≥ 6, it is possible to buy n cans of

soda via some number of 3-packs and some number of 4-packs

Answer 1

Think about (play with) this before you begin the proof to get a feel for the pattern. Once you have a pattern, you can use this to do an induction proof.

We have n>=6 that is divisible by three (n = 3a) or four (n = 4b) or some combination of (n = 3a + 4b) from the problem. There is a number, say m<n, such that m is divisible by 3, m + 1, m + 2, and then m + 3 also divisible by 3 and this pattern will repeat until we reach n. If n is divisible by 3 then we can definitely buy n sodas in 3-packs; if n is a m +1 then we replace a 3-pack by a 4-pack and for n = m + 2 we replace two 3-packs with two 4-packs.Every n is a m (divisible by 3), m + 1, or m + 2.

For proof by induction you prove the base case or in this example, n = 6. 6 is divisible by 3 so we would buy two 3-packs. Per the above, n = 7 is buy one 3-pack and one 4-pack and n = 8 is buy two 4-packs.

For an induction proof, you then assume it works for some arbitrary number. Let n = k, called the inductive hypothesis, and show it works for n +1, the inductive step.

Assume k is divisible by 3 or n = k = 3t and that we can supply n sodas by buying t number of 3-packs, for some integer t >= 2; n = k + 1 = 3t + 1; and n = k + 2 = 3t + 2.

Then for the inductive step, n = k + 1 = 3t +1 (assumed true by the inductive hypothesis); which is n cans of soda purchased as (t - 1) 3-packs and a 4-pack.

n +1 = (k + 1) + 1 = 3t + 2; which is purchased as (t - 2) 3-packs and two 4-packs.

n + 2 = (k + 1) + 2 = 3t + 3 = 3(k + 1) = 3n which is divisible by 3 so is purchased as (t + 1) 3-packs.

Proof by induction can seem like circular reasoning, but it does work.