- #1

- 29

- 0

## 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?