Answers to the final exam

You can view the questions and answers here.

Answers, and what to bring to the final

One twist:
To the final you may bring one double-sided sheet of handwritten notes, and your midterms. One question from the midterms will make a surprise appearance!


1a. Let a,b be integers such that a² = b³.
Is b necessarily a square?
If yes, prove it, otherwise, give a counterexample (a pair {a,b}).

ANSWER. Yes, it's true. Write out the prime factorizations, and look at the power of a prime p occurring in the equation: 2a_p = 3b_p. Hence each b_p must be even. Then the product over all p of p^(b_p/2) is an integer, and a square root of b.

1b. Let a,b be integers such that a¹⁰ = b¹⁵.
Is b necessarily a 10th power?
If yes, prove it, otherwise, give a counterexample (a pair {a,b}).

ANSWER. No. In fact this equation is just the 5th power of the one above! For a small solution to the equation above, take b = 2² = 4, a = 2³ = 8. Then this second equation holds but b=4 is not a 10th power of an integer.

1c. Let a,b be integers such that a³²³ = b³⁹¹.
Then a,b are both powers of some other integer. What are those powers?

ANSWER. Follow the same analysis as in 1a to get 323a_p = 391b_p. To simplify this equation, divide by the gcd of 323 and 391, which we can calculate with Euclid's algorithm. 391-323 = 68, 323-4*68 = 323-272 = 51, 68-51 = 17, 51-3*17 = 0. So 17 is the gcd, and dividing we get 19a_p = 23b_p. Hence each b_p is a multiple of 19, and b is a 19th power of some guy, where a is the 23rd power of that same guy.

2. Prove by induction that sum_i=1...n 1/i(i+1) = 1 - 1/(n+1).

ANSWER. The easiest base case is n=0, where this says 0=0. (If you wanted to do the base case n=1 where this says 1/1*2 = 1 - 1/2, that's not so hard either, but it is harder.)

Then for n>0, the LHS can be rewritten as (sum_i=1...n-1 1/i(i+1)) + 1/n(n+1) by separating out the last term. (When n=0, there is no term at all, much less a last term.) By induction, the first part of that adds up to 1-1/n. Then we check that
1-1/n + 1/n(n+1) = 1 - 1/(n+1)
which is easy.

3. Let k,n be natural numbers, such that n! > kⁿ. Show that for all N > n, N! > k^N.

ANSWER. By induction on N. The base case is N=n, which is given to us. (So in fact we're going to show it for all N greater than or equal to n.)

Now we can assume that it's true for N, and wish to prove it for N+1. Look first at (N+1)! = (N+1) N! > (N+1) k^N. We would like for that to be > k^N+1, i.e. we would like N+1 > k.

We know N+1 > n. Do we know n > k? If not, then n is less than or equal to k, in which case n! is a product of n numbers less than or equal to k, and this product is therefore less than or equal to kⁿ. But we were told that isn't true.

Having reached that contradiction, we learn n > k, so N+1 > k, which was the remaining step in showing that (N+1)! > k^N+1. This completes the induction step.

4. Let R,S be two equivalence relations on the same set X.

a. Show that R intersect S is an equivalence relation (where "intersect" means as sets of ordered pairs).

ANSWER. Let x,y,z denote elements of X.
Reflexive: since R,S are reflexive, (x,x) is in R and S, hence in the
intersection.
Symmetric: if (x,y) is in R intersect S, it's in both R and S. Since R and S are symmetric, that implies (y,x) is in both R and S. Hence it's in the intersection.
Transitive: same deal as symmetric. If (x,y) and (y,z) are in R intersect S, they're in both R and S. Since R and S are transitive, (x,z) is in both R and S. Hence it's in the intersection.

b. Let RuS denote the union of R and S. Of the three conditions required of an equivalence relation, which ones does RuS automatically satisfy? For each condition {reflexive, symmetric, transitive}, either show that RuS satisfies it, or give an example of X,R,S where RuS doesn't satisfy it.

Reflexive. Yes. Since for any x we know (x,x) is in R, it's in RuS.
Symmetric. Yes. Say (x,y) is in RuS. Then it's in either R or S. If it's in R, then (y,x) is in R since R is symmetric, so (y,x) is in RuS. Same proof for "in S".
Transitive. No. Say X has three elements {x,y,z}, and R has the associated partition { {x,y}, {z} }, whereas S has the associated partition { {x}, {y,z} }. Then (x,y) is in R, and (y,z) is in S, so both elements are in RuS, but (x,z) is not in RuS.

5. "Let b,c,n be integers, such that bⁿ > cⁿ. Then for all N>n, b^N > c^N." State the negation of this statement and prove that.

ANSWER. Rewrite with quantifiers explicit:
"For all b,c,n integers, such that bⁿ > cⁿ, for all N>n, b^N > c^N."
To negate:
"There exists b,c,n integers, such that bⁿ > cⁿ,
and there exists N>n, where b^N is less than or equal to c^N."
Proof: let n=2, b=-3, c=2, N=3. Then (-3)² > 2², but (-3)³ is less than 2³.

Basically a trick question, in that it had silly negative numbers to confuse you, but at least it wasn't a "Prove or disprove" gotcha question.

Office hours and practice final

I will be available for office hours from 10-1 on Tuesday and Wednesday. HOWEVER these are not drop-in times -- if you want to see me, email me (ideally the night before, or at least half an hour in advance).

I will be putting up practice final questions tonight, with answers posted tomorrow night. Here are the first few:

1a. Let a,b be integers such that a² = b³.
Is b necessarily a square?
If yes, prove it, otherwise, give a counterexample (a pair {a,b}).

1b. Let a,b be integers such that a¹⁰ = b¹⁵.
Is b necessarily a 10th power?
If yes, prove it, otherwise, give a counterexample (a pair {a,b}).

1c. Let a,b be integers such that a³²³ = b³⁹¹.
Then a,b are both powers of some other integer. What are those powers?

2. Prove by induction that sum_i=1...n 1/i(i+1) = 1 - 1/(n+1).

3. Let k,n be natural numbers, such that n! > kⁿ. Show that for all N > n, N! > k^N.

4. Let R,S be two equivalence relations on the same set X.

a. Show that R intersect S is an equivalence relation (where "intersect" means as sets of ordered pairs).

b. Let RuS denote the union of R and S. Of the three conditions required of an equivalence relation, which ones does RuS automatically satisfy? For each condition {reflexive, symmetric, transitive}, either show that RuS satisfies it, or give an example of X,R,S where RuS doesn't satisfy it.

5. "Let b,c,n be integers, such that bⁿ > cⁿ. Then for all N>n, b^N > c^N." State the negation of this statement and prove that.