Prove that 2n > n2 for n > 5 6 N What is wrong with the following \"proof\'? Sho

Question

Prove that 2n > n2 for n > 5 6 N What is wrong with the following "proof'? Show that "all horses are the same color". Let P(ri) = a set of n horses being the same color Basis step: P(1) is true because one horse is the same color Assume P(k) is true, i.e., all the horses in any set of k horses are the same color Show that P(k + 1) is true: Let h_1 h_2,..., h_k, be k + 1 horses in a set By inductive hypothesis {h_lt h_2,..., h_k} has the same color and {h_2, h_2,.... have the same color. Therefore {h_1, h_2, h_3,..., h_k+1} has the same color.

Explanation / Answer

Prove 2^n n^2

Answer

Now assume that it holds for n, i.e.

2^n n^2

Let's try n+1

2^(n+1) = 2*2^n 2*n^2 = n^2 + n^2

Now since n 4,

n^2 4n = 2n + 2n

and 2n > 1

So n^2 > 2n + 1

Thus 2n^2 > n^2 + 2n + 1 = (n+1)^2

Thus 2^(n+1) = 2*2^n > (n+1)^2

Question 2

Answer

False theorem: All horses are the same color.

Proof by induction:

Base Case or P(1):Base Case or P(1): One horse is the same color as itself. This is true by inspection.

Induction Step:Induction Step: Assume P(k)P(k) for some k1k1.

Proof of P(k+1):Proof of P(k+1):

Since {H1,H2,...,Hn}{H1,H2,...,Hn} is a set of nn horses, the induction hypothesis applies to this set. Thus, all the horses in this set are the same color.

Since {H2,H3,...,Hn+1}{H2,H3,...,Hn+1} is also a set of nn horses, the induction step likewise holds for set. Thus, all the horses in this set are the same color too.

Therefore, all n+1n+1 horses in {H1,H2,H3,...,Hn,Hn+1}{H1,H2,H3,...,Hn,Hn+1} are the same color.

Related Questions

Navigate

• Browse (All)
• Browse P
• Subjects

---

---

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