Wednesday, December 06, 2006
Tuesday, December 05, 2006
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 a2 = b3.
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: 2ap = 3bp. Hence each bp must be even. Then the product over all p of p(bp/2) is an integer, and a square root of b.
1b. Let a,b be integers such that a10 = b15.
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 = 22 = 4, a = 23 = 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 a323 = b391.
Then a,b are both powers of some other integer. What are those powers?
ANSWER. Follow the same analysis as in 1a to get 323ap = 391bp. 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 19ap = 23bp. Hence each bp 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 sumi=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 (sumi=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! > kn. Show that for all N > n, N! > kN.
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) kN. We would like for that to be > kN+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 kn. 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)! > kN+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 bn > cn. Then for all N>n, bN > cN." State the negation of this statement and prove that.
ANSWER. Rewrite with quantifiers explicit:
"For all b,c,n integers, such that bn > cn, for all N>n, bN > cN."
To negate:
"There exists b,c,n integers, such that bn > cn,
and there exists N>n, where bN is less than or equal to cN."
Proof: let n=2, b=-3, c=2, N=3. Then (-3)2 > 22, but (-3)3 is less than 23.
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.
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 a2 = b3.
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: 2ap = 3bp. Hence each bp must be even. Then the product over all p of p(bp/2) is an integer, and a square root of b.
1b. Let a,b be integers such that a10 = b15.
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 = 22 = 4, a = 23 = 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 a323 = b391.
Then a,b are both powers of some other integer. What are those powers?
ANSWER. Follow the same analysis as in 1a to get 323ap = 391bp. 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 19ap = 23bp. Hence each bp 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 sumi=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 (sumi=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! > kn. Show that for all N > n, N! > kN.
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) kN. We would like for that to be > kN+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 kn. 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)! > kN+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 bn > cn. Then for all N>n, bN > cN." State the negation of this statement and prove that.
ANSWER. Rewrite with quantifiers explicit:
"For all b,c,n integers, such that bn > cn, for all N>n, bN > cN."
To negate:
"There exists b,c,n integers, such that bn > cn,
and there exists N>n, where bN is less than or equal to cN."
Proof: let n=2, b=-3, c=2, N=3. Then (-3)2 > 22, but (-3)3 is less than 23.
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.
Monday, December 04, 2006
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 a2 = b3.
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 a10 = b15.
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 a323 = b391.
Then a,b are both powers of some other integer. What are those powers?
2. Prove by induction that sumi=1...n 1/i(i+1) = 1 - 1/(n+1).
3. Let k,n be natural numbers, such that n! > kn. Show that for all N > n, N! > kN.
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 bn > cn. Then for all N>n, bN > cN." State the negation of this statement and prove that.
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 a2 = b3.
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 a10 = b15.
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 a323 = b391.
Then a,b are both powers of some other integer. What are those powers?
2. Prove by induction that sumi=1...n 1/i(i+1) = 1 - 1/(n+1).
3. Let k,n be natural numbers, such that n! > kn. Show that for all N > n, N! > kN.
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 bn > cn. Then for all N>n, bN > cN." State the negation of this statement and prove that.
Subscribe to:
Posts (Atom)