What is wrong with the following \"proof\" by mathematical induction? (Proof) We

Question

What is wrong with the following "proof" by mathematical induction?

(Proof)

We will prove that all computers are built by the same manufacturer. In particular we will prove that in any collection of n computers where n is a positive integer, all the computers are built by the same manufacturer. We first prove P(1), a trivial proccess, because in any collection consisting of one computer, there is only one manufacturer. No we assume P(k); that is, in any collection of k computers, all the computers were built by the same manufacturer. To prove P(k+1), we consider any collection of k + 1 computers. Pull one of these k+1 computers (call it HAL) out of the collection. By our assumption, the remaining k computers all have the same manufacturer. Let HAL change places with one of these k computers. In the new group of k computers, all have the same manufacturer. Thus, HAL's manufacturer is the same one that produced all the other computers, and all k+1 computers have the same manufacturer.

(This proof is so conveluted and long idk what the mistake is...)

Explanation / Answer

Problem in proof lies in inductive step.

Assume P(k) is true for some k>=1 is fine

But while proving P(k+1) we have the problem. For k>1 the proof works but what happens for k=1

k+1=2 ie only two computers

P(1) is true so 1 computer built by say X manufacturer and other 1 computer is built by Y manufacturer so the two are not built by same manufacturer

For k>1

k+1>2

So we can first take first k computers which are at least 2 in number and are built by same manufacturer since ,P(k) is true and then take last k computers and again they are built by same manufacturer. So the reasoning works for k>1 but not for k=1. THat is where the proof fails.

Related Questions

Navigate

• Browse (All)
• Browse W
• Subjects

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.