Find number of positive integers n less than 100 for which 3 n n 2 is divisible by 5

415 Review for Midterm

1. For propositions P and Q below, state whether or not P � Q.  Write a truth table to justify your answer.

P:   p � q � r
Q:  [p � r] � [q � r]

ANSWER:  P � Q.  Truth table is as follows.

p	q	r	p � q �  r	[p � r] � [q � r]
T	T	T	T	T
T	T	F	F	F
T	F	T	T	T
T	F	F	F	F
F	T	T	T	T
F	T	F	F	F
F	F	T	T	T
F	F	F	T	T

2. Determine the truth value of the following proposition.  If it is true, prove it using direct proof.  If it is false, state the negation explicitly and give a counterexample.

Proposition: The sum of any three consecutive integers is divisible by 3.

ANSWER:  True.

Proof:  Let three consecutive integers a, b, c be [n+1], [n+2] and [n+3] respectively.  Then,

a + b + c = [n+1] + [n+2] + [n+3]
               = 3n + 6
               = 3[n+2]

Since n+2 is an integer, 3[n+2] is divisible by 3.

3. Determine the truth value of the following proposition.  If it is true, prove it using direct proof.  If it is false, state the negation explicitly and give a counterexample.

Proposition: "a"b such that a, b are real numbers, sqrt[a+b] = sqrt[a] + sqrt[b].

ANSWER:  False.

Negation of the proposition is $a$b such that a, b are real numbers, sqrt[a+b] != sqrt[a] + sqrt[b].  Examples of such a, b are a =1 and b = 2.

4. Prove the following proposition by using proof by contradiction.

Proposition:  If a product of two positive real numbers is greater than 100, then at least one of the numbers is greater than 10.

ANSWER:  Proof by contradiction.

The proposition states that, "a"b. such that a, b are real numbers, if a * b > 100, then a > 10 or b > 10.  We show this by contradiction.

[Negation of the proposition] Suppose not, that is, $a$b. such that a, b are real numbers, a * b > 100 and a = 1 + nx, for x >= -1 and n = 1,2,...

ANSWER:  Proof by induction

Basic Step [n = 1]:

LHS = 1+x
RHS = 1+x     So, LHS >= RHS ... [A]

Inductive Step:

Assume [1 + x]n >= 1 + nx, for n >= 1.
Show [1 + x]n+1 >= 1 + [n+1]x

LHS = [1 + x]n+1 = [1 + x][1 + x]n
                            >= [1 + x] [1 + nx]       by inductive hypothesis
                            = 1 + [n + 1]x + nx2
                            >= 1 + [n + 1]x             since nx2 >= 0
                            = RHS       
So, LHS >= RHS  ... [B]

By [A] and [B], the theorem is true.

7. [Section 1.6, #22; p. 47]  By experimenting with small values of n, guess a formula for the given sum:

 1     1           1
--- + --- + .. + -----
1*2   2*3        n[n+1]

then use induction to verify your formula.

ANSWER:

First we claim that

 1     1           1       n
--- + --- + .. + -----  = ---
1*2   2*3        n[n+1]   n+1

for n = 1, 2, ...

Proof:  by induction.

Basic Step [n = 1]:

LHS = 1/2
RHS = 1/2       So, LHS = RHS ... [A]

Inductive Step:

Assume 

 1     1           1       n
--- + --- + .. + -----  = ---
1*2   2*3        n[n+1]   n+1

Show

 1     1           1         1         n
--- + --- + .. + ----- + ---------- = ---
1*2   2*3        n[n+1]  [n+1][n+2]   n+1

LHS

 1     1           1         1     
--- + --- + .. + ----- + ----------
1*2   2*3        n[n+1]  [n+1][n+2]

   n        1
= --- + ----------
  n+1   [n+1][n+2]

  n[n+2] + 1
= ----------
  [n+1][n+2]

  n^2 + 2n + 1
= ------------
  [n+1][n+2]

   [n+1]^2
= ----------
  [n+1][n+2]

  n+1
= --- 
  n+2

= RHS         So, LHS = RHS ... [B]

By [A] and [B], the formula is true.

8. Write an algorithm that counts the number of even numbers in a sequence s = {s1, s2, .., sn}, where si [1