Math 115 HW 1 - imj

Math 115 HW 1
Due Wednesday, October 3
Goals:
• Figure out your reasons for being in this class.
• Learn to prove statements by induction.
• Understand importance of both the base and the step of induction.
• Learn to recognize statements that can be proved inductively; practice formulating the induction hypothesis and performing the inductive step.
• Train proving irrationality of various algebraic numbers.
• Learn to work with an axiomatic system - be able to rigorously deduce new
properties from previous ones, to translate intuitive arguments into formal
proofs.
Total number of possible points: 34.
* (Optional) What is the total time you spent on this homework?
Of which working alone:
Working with other students:
At office hours/tutoring:
Other(specify):
0 (2 points) What is your reason for taking Math 115? What are your goals and
motivations for this class? (It is perfectly fine to say “it was the next one in
the sequence needed for my major” or “my adviser told me to” or something
similar, but perhaps you can then also tell me why do you think it is the next
one in the sequence, or why might your adviser have told you to take it.)
1 (Ross 1.1, 3 points) Prove 12 + 22 + . . . + n2 = 61 n(n + 1)(2n + 1).
2 (Ross 1.11) For each n ∈ N let Pn denote the assertion “n2 + 5n + 1 is an even
integer”.
1
• (2 points) Prove that Pn+1 is true whenever Pn is true.
• (2 points) For which n is Pn actually true? What is the moral of this
exercise?
3 (3 points) Is there a mistake in the following proof:
Proposition. All cats are of the same color.
Proof. We prove that in any set of cats of size n all the cats are of the same
color. The base of induction is n = 1 is true - any set of cats of size one has just
one cat, so all cats in it are of same color. Now we prove the step of induction.
Suppose we have a set of n + 1 cats. Remove one cat (who we will call Tom)
from it, so that remaining set of cats is of size n and so has cats of all the same
color. Hence all cats but Tom are of the same color. Now remove another cat
from the set. We again get a set of size n, which now includes Tom, and where
all cats are of the same color, so Tom has the same color as all other cats, and
so all cats in our initial set have the same color. This completes the induction
step, and so by mathematical induction all cats are of the same color.
If there is a mistake, where is it? If not, why do we observe cats of different
colors? (For videos of cats, please refer to the internet.)
4 (4 points) Prove the following stronger version of induction principle (using
either the well-ordering property or the usual induction principle):
Proposition 0.1. Suppose that for each n ≥ n0 in N we have a statement Pn .
Suppose also we have the following:
(I1 ) Pn0 is true.
(I2 ) Whenever Pk is true, Pk+1 is also true.
Then for any n ≥ n0 in N the statement Pn is true.
5 (Ross 2.4, 3 points) Prove that (5 −
√
1
3) 3 does not represent a rational number.
6 (4 points) Prove 0 < 1 in any ordered field. Hint: You can use all axioms of
an ordered field as well as the items i-iv in Theorem 3.2 in Ross. You will
also need the fact that a field has more than one element, which Ross mentions,
but we did not dwell on in lectures. If you seem to solve this problem without
using the fact that fields have more than one element you are probably missing
something.
2
7 (3 points) Define ≥ by saying that a ≥ b if and only if b ≤ a. Get properties
D1-D5 by replacing ≤ by ≥ in properties O1-O5. Which of the new properties
D1-D5 are true (for all a, b and c)?
8 (3 points) Prove that if a ≤ b and c ≤ d then a + c ≤ b + d.
9 (Ross 3.6)
(a) (2 points) Prove |a+b+c| ≤ |a|+|b|+|c|. Hint: Apply triangle inequality
twice.
(b) (3 points) Prove
|a1 + a2 + . . . an | ≤ |a1 + |a2 | . . . + |an |
by induction.
10 (Optional) What was the most confusing or difficult thing this week? For what
would you like an explanation or clarification?
3

Download Report