Extra Credit Assignment Let Pn be the statement that 2 divid

Extra Credit Assignment Let P(n) be the statement that 2 divides n^2+n whenever n is a positive integer. What is the statement P(1)? Show that P(l) is true, completing the basis step of the proof. What is the inductive hypothesis? What do you need to prove in the inductive step? Complete the inductive step. Find a formula for 1/2 + 1/4 + 1/8 + middot middot middot + 1/2^n by examining the values of this expression for small values of n. Prove the formula you conjectured in part 8), following the steps outlined in Problem 1. What is wrong with the \"proof\" that all horses have the same color? Let P(n) be the proposition that all the horses in a set of n horses are the same color. Basis step: Clearly, P(l) holds.

Solution

1.

a)

P(1) is the statement that:2|1^1+1

b)

P(1)=1^2+1=2

Hence, 2|P(1)

c)

Inductive hypothesis

Assume it is true for some k>=1

ie P(k) is true

d)

We need to prove ,P(k+1) is true

e)

(k+1)^2+(k+1)=k^2+1+2k+k+1=(k^2+k)+2k+2

2|k^2+k as P(k) is true

2|2k+2

Hence, P(k+1) is true

(2)

1/2+1/4=3/4=(4-1)/4

1/2+1/4+1/8=3/4+1/8=7/8=(8-1)/8

So,

1/2+1/4+...+1/2^n=(2^n-1)/2^n

b)

Let P(n) be statement that:

1/2+1/4+...+1/2^n=(2^n-1)/2^n

base case:

1/2=(2^1-1)/2

Hence, P(1) is true.

Inductive step:

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

We show that: P(k+1) is true

1/2+...+1/2^n+1/2^{n+1}=(1/2+...+1/2^n)+1/2^{n+1}

                                             =(2^n-1)/2^n+1/2^{n+1}

                                             =(2^{n+1}-2+1)/2^{n+1}

                                             =(2^{n+1}-1)/2^{n+1}

Hence, P(n+1) is true.

3.

One statement in Inductive step is:

\".. Because the set of the first k horses and the set of the last k horses overlap..\"

This is wrong because: k>=1 and for k=1 this does not hold true.