Analyzing Induction Proof: Correct or Not?

• ryou00730

Homework Statement

Consider the following induction proof.
Discuss whether the proof is correct or not, and if not, explain precisely why
not.
Theorem: Every cpu is made by the same manufacturer.
Proof: We prove this by induction. Let P(n) mean that for any set of n
cpu’s , they are all made by the same manufacturer.
Base case: P(1) means that any set of a single cpu is made by a same
manufacturer. But this is obviously true, since a single cpu can only be made
by a single manufacturer.
Induction step: Assume as an induction hypothesis that for any set of k
cpu’s, they must all be made by the same manufacturer. We now prove that
this implies that any set of k + 1 cpu’s are made by the same manufacturer.
Let S = {c1, c2..., ck, ck+1} be any set of k+1 cpu’s. We will show that we
can prove all these cpu’s are made by the same manufacturer, assuming the
induction hypothesis. Consider the set S − {ck+1}. This is a set of k cpu’s,
so by the induction hypothesis they are all made by the same manufacturer,
say M. Thus c1 and ck are both made by M. Now consider the set S −{ck},
which is also a set of k cpu’s. Again by the induction hypothesis the cpu’s
are all made by the same manufacturer, so c1 and ck+1 are made by the same
manufacturer. As c1 is made by M, then ck+1 is also made by M. Thus M
makes all the cpu’s in S. qed.

I think that the flaws in this are that they should be assuming n, and proving n+1, not assuming k, and prooving n+1. I also think that they should have stated somewhere a relationship between the set S, and P(n), because it doesn't really define P(n) to be anything to do with the set S = ... Does anyone see what I should be pointing out?

Who is this "the same manufacturer" character?

I'm not really certain. I feel like he would need another base case as well.. like base of P(2), because just because one cpu is made by this "same manufacturer" doesn't mean that 2 are, or all are for that matter. I'm not really sure here what's wrong though, or what I'm suppose to be doing.

In order for induction to work, one has to prove the P(k)->P(k+1) for all k greater than or equal to a base case.

Now in this proof, they used the base case of P(1), which was fine. Then they claimed that P(k) implies P(k+1) for all k $\geq$ 1. Try to verify their proof for k=1.

I don't exactly follow what you want me to do. So you want me to verify in the proof for k=1? So you mean you want me to verify that it works for P(2) or? Now that I look at it, the proof looks correct, or is there something in there actually completely wrong?

Let's go through the induction step for P(k)->P(k+1). Then we'll fill in 1 for k, and see how that works out.

Claim.
Assume that P(k) is true. All sets of k cpus are made by a single manufacturer.
Then this implies that P(k+1) is true; all sets of k+1 cpus are made by a single manufacturer.

Proof.
Let S={c1,c2,...,ck,ck+1}.
Consider the set S-{ck+1}. This set consists of k cpu, so it is made by a single manufacturer M because we assume P(k) is true. Then c1 and ck are made by M.
Next consider the set S-{ck}. This set consists of k cpu also, so it is made by a single manufacturer as well. So c1 and ck+1 are made by the same manufacturer.

Now fill in 1 for k.

Claim.
Assume that P(1) is true. All sets of 1 cpu are made by a single manufacturer.
Then this implies that P(2) is true; all sets of 2 cpus are made by a single manufacturer.

Proof.
Let S={c1,c2}.
Consider the set S-{c2}={c1}. This set consists of 1 cpu, so it is made by a single manufacturer M because we assume P(1) is true. Then c1 and c1 are made by M.
Next consider the set S-{c1}={c2}. This set consists of 1 cpu also, so it is made by a single manufacturer as well. So c1 and c2 are made by the same manufacturer.

OOPS! False claim. Why?

Mistake: The inductive step fails from n=1 to n=2. If we assume S=(c1, c2..., ck, ck+1) is a set of k+1 cpus, then when k=2, S=(c1, c2). If we take S-c1 then this is a set of k cpus and we get S-c1 = (c2) should be a set of k cpus (specifically k=1), but we already showed k=1 is P(1) = (c1). So we have a contradiction here, which means since the inductive step fails from n=1 to n=2, the statement is not proved.
Does this seem correct? Or would you be able to help me better word it?

Oh I didn't notice you posted a reply. So this is a false claim because P(1)= (c1), and we did not prove that it could also equal (c2)?

OK, no. P(1) is the statement that any set of 1 cpu is made by a single manufacturer. This is obviously true. P(2) is the statement that any set of 2 cpus is made by a single manufacturer.

Now their proof tries to work like this:

They pick a k-sized subset of k+1 cpus which include c1 and ck+1. By their assumption that any k-sized set is made by a single manufacturer, c1 and ck+1 are made by some manufacturer M.
Then they pick a different k-sized subset which includes c1 through ck. Again by the assumption than any k-sized set is made by a single manufacturer, c1 and ck are made by the same manufacturer. Since c1 is made by M from the first part, c1 through ck are made by M, and so all the cpus are made by M. So any set of size k+1 is made by M.

But when k is 1, this all fails, because a 1-sized subset can't include both c1 and ck+1, which means you can't link up the manufacturer of ck+1 to the other cpus. Does that make sense?

hmmm, not entirely. I follow most of it, just the part where you get down to a 1 size subset. Why does when k=1 necessarily have to have c1 and ck+1 in the size one subset? I thought it was okay to have just c1 in the size 1 subset as proven in the base step?

Well, you need to have two different cpus in some subset of size k at some point, otherwise there's no "same manufacturer." But if k is one, there can never be two different cpus in a size-k subset.