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 <= 10 and b <= 10 (i.e., (~(p � (q � r)) � p � ~q � ~r) .  Then,

a * b <= 10 * 10 = 100.

But from assumption, a * b > 100.  Therefore, contradiction.  Therefore, the original proposition is true.

5. (Section 1.6, #4; p. 46)  Using induction, verify the following equation is true for every positive integer n.

12 + 22 + 32 + ... + n2 = [n(n+1)(2n+1)] / 6

ANSWER:  Proof by induction

Basic Step (n = 1):

LHS = 12 = 1
RHS = [1*2*3]/6 = 6/6 = 1.  So LHS = RHS ... (A)

Inductive Step:

Assume 12 + 22 + 32 + ... + n2 = [n(n+1)(2n+1)] / 6  for n >= 1.
Show 12 + 22 + 32 + ... + n2 + (n+1)2 = [(n+1)(n+2)(2n+3)] / 6

LHS = 12 + 22 + 32 + ... + n2 + (n+1)2
           n(n+1)(2n+1)
        = ------------- + (n+1)2   ... by inductive hypothesis
                   6
           (n+1)[n(2n+1)+6(n+1)]
        = ------------------------
                        6
           (n+1)(2n2 + n + 6n + 6)
        = ------------------------
                        6
           (n+1)(2n2 + 7n + 6)
        = --------------------
                        6
            (n+1)(2n + 3)(n + 2)
        = ---------------------- = RHS     ... (B)
                        6

By (A) and (B), the theorem is true.

6. (Section 1.6, #17; p. 47)  Using induction, verify the following inequality.

(1 + x)n >= 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 <= i <= n) is an integer.

ANSWER:

procedure count_even(s, n)
1. count := 0
2. i := 1
3. while (i <= n)
4.   begin
5.   if (si mod 2 = 0) then
6.     count := count + 1
7.   i := i + 1
8.   end
9. return count
end count_even

9. Use the Euclidean algorithm to find the greatest common divisor of 527 and 62.  Show the values of variables a, b and r in each iteration.

ANSWER: The gcd of 527 and 62 is 31, as shown in the following table.

iteration		a	b	r
1	gcd(527, 62)	527	62	31
2	gcd(62, 31)	62	31	0
3	gcd(31, 0)	31	0

How many integers less than 100 are divisible by either 2/3 or 5?

How many positive numbers less than 100 which is multiple of 2 or 5?

How many positive integers not exceeding 100 and are divisible by neither 3 nor 5?

What is the sum of all positive integers less than or equal to 100?