[SOLVED] MATH 127 Sample Final Exam B Python

MATH 127: Sample Final Exam B

1.  Consider the following proposition.

∀n ∈ N, ∃p ∈ N, ((p > n)∧ ∀k ∈ N, (k | p → (k = 1 ∨ k = p))).

(a)  Determine whether this statement is true or false.  Justify your answer with a sentence or two.  (A full proof is  not necessary.)                 [4 pts]

(b)  Regardless of the truth value, write the logical negation of this statement in maximally negated form.             [5 pts]

2.  Define a sequence ⟨an  |  n ∈ N⟩ recursively as follows:

Prove that for all n ∈ N, an  and an+1  are coprime.                                                                       [10 pts]

3. Let n ∈ Z with n ≥ 2. Prove that

using a “counting in two ways” argument.                                                                                     [12 pts]

• Use the exact form of the equation as given; do not simplify it algebraically.

• If your argument involves constructing partitions, justify that your construction defines a valid partition.

4.  For the following problems, provide  an appropriate counting argument to justify your answer.

You may leave  answers  as products, sums  of integers, factorials,  or binomial coefficients.

Let S be the set of strings (arrangements with repetition) of length 8 formed from the 26 letters of the English alphabet, and let T ≤ S be the subset consisting of strings with all distinct letters.

(a)  Determine the cardinalities of S and T.                                                                                 [3 pts]

(b)  How many elements of S contain the letters A, B, and C?                                                       [6 pts]

(c)  How many elements of T contain the letters G and J such that G appears somewhere to the left of J in the string?       [6 pts]

5.   (a)  Let m ∈ Z+ and Fm = {f : N → N | ∀n ≥ m,f(n) = 0}.  Define a bijection between Fm and Nm  and prove that it is a bijection.       [10 pts]

(b)  Prove that

F = {f : N → N | f(n) ≠ 0 for only finitely many values of n}

is countably infinite.                                                                                                               [6 pts]

6. Let A and B be non-empty sets, and let f : A → B be an arbitrary function.  Prove that f

is injective if and only if

∀X ∈ P(A),    Imf(X) ⊆ Imf(X).

Note:  X denotes the complement of X in A, and Imf(X) denotes the complement of Imf(X) in B.                         [12 pts]

7. A relation R on a non-empty set S is called Euclidean if and only if R satisfies the following

property:

∀a, b, c ∈ S, (((a, b) ∈ R ∧ (a, c) ∈ R) → (b, c) ∈ R).

Prove that a relation R is an equivalence relation on S if and only if R is both Euclidean and reflexive.         [10 pts]

8. For any x ∈ R, define the function frac(x) = x – lx」.  Let α ∈ R and n ∈ Z+  be arbitrary and fixed. Prove that there exist i,j ∈ {0} U [n], with i ≠ j, such that                                      [8 pts]

|frac(iα) – frac(jα)| < n/1 .

9.  Determine, with proof, the set of all integers that leave a remainder of 4 when divided by 5 and a remainder of 6 when divided by 13.          [8 pts]