TASK FIVE

Number 1

Show that if n is positive integer

P(n) : 1+2+………..+ n = [n (n+1)]/2

Basis step : let n = 1

1 = [1(1+1)]/2

1 = 1 (PROVE)!!!

Inductive step : let n=k; k= k+1

1 + 2 +…+ n = [n (n+1)]/2

1 + 2 +…+ k= [k (k+1)]/2

1 + 2 +…+ k + (k+1) = (k+1) [(k+1)+1]/2

[k(k+1)]/2 + (k+1) = [(k+1) (k+2)]/2

[k(k+1) +2k+2]/2 = [(k+1) (k+2)]/2

[k ² + k + 2k +2]/2 = [k² + 2k + k+ 2]/2

[k² + 3k+ 2] /2 = [k² + 3k + 2]/2 (PROVE)!!!

Number 2

Basis Step

if P(n) is true then can continue to the next step.

Inductive Step

If P then Q

P is the hyphothesis while Q is conclusion

Thus,

If P(n) is true, Then P(n+1) is true/false

Number 3

#Formulas:

Show that if n is a positive integer, then

1 + 2+…..+n =

Solution: Let P(n) be the proposition that the sum of the first n positive integers, 1+2+…+n=n(n+1)/2. We must do two things to prove that P(n) is true for n = 1, 2, 3, . . .

Namely, we must show that P(1) is true and that the conditional statement P(k) implies P(k + 1) is true for k = 1, 2, 3,…..

BASIS STEP: P(1) is true, because 1 =

(The left-hand side of this equation is 1 because 1 is the sum of the first positive integer. The right-hand side is found by substituting 1 for n in n(n + 1)/2.)

INDUCTIVE STEP: For the inductive hypothesis we assume that P(k) holds for an arbitrary positive integer k. That is, we assume that

1 + 2+· · ·+k =

Under this assumption, it must be shown that P(k + 1) is true, namely, that

1 + 2+· · ·+k + (k + 1) ==

is also true. When we add k + 1 to both sides of the equation in P(k), we obtain

1+2+....+k+(k + 1)=+(k+1)

=

=

This last equation shows that P(k + 1) is true under the assumption that P(k) is true. This completes the inductive step.

We have completed the basis step and the inductive step, so by mathematical induction we know that P(n) is true for all positive integers n. That is, we have proven that 1 + 2+· · ·+n =n(n + 1)/2 for all positive integers n.

#Divisibility properties

Proposition: For any integer n≥1, 7ⁿ - 2ⁿ is divisible by 5. (P(n))

Proof :

1) Basis step:

The statement is true for n=1: (P(1))

7¹ – 2¹ = 7 - 2 = 5 is divisible by 5.

2) Inductive step:

Assume the statement is true for some k≥1 (P(k))

(inductive hypothesis) ;

We are given that

P(k): 7^k - 2^k is divisible by 5. (1)

Then 7^k - 2^k = 5a for some aÎZ . (2)

We need to show:

P(k+1):7^k+1 - 2^k+1 is divisible by 5. (3)

7^k+1 - 2^k+1 = 7·7^k - 2·2^k = 5·7^k + 2·7^k - 2·2^k

= 5·7^k + 2·(7^k - 2^k) = 5·7^k + 2·5a (by (2))

= 5·(7^k + 2a) which is divisible by 5.

Show that it is true for k+1. (P(k+1))

Thus, P(n) is true by induction.

#Inequalities

Theorem: For all integers n≥5, n² < 2ⁿ. (P(n))

Proof (by induction):

1) Basis step:

The statement is true for n=5: (P(5))

5² =25 < 32 = 2⁵.

2)Inductive step:

Assume the statement is true for some k≥5 ; (P(k))

We are given that

P(k): k² < 2^k. (1)

We need to show:

P(k+1): (k+1)² < 2^k+1. (2)

(k+1)² = k²+2k+1 < k² +2^k (since k≥5)

< 2^k + 2^k (based on (1))

= 2·2^k = 2^k+1.

Show that it is true for k+1 . (P(k+1))

Thus, P(n) is true by induction.