HW #3 due Monday May 5 (yes, Monday)

More practicing proofs by induction.

1. Let f(n) be a function from N -> N (the naturals), satisfying
f(0) = 0
for n>0, f(n) = 2 * f(n-1) + 1.
Prove that for all n in the naturals, f(n) = 2ⁿ - 1.

2. Prove that for all n at least 2 (this induction doesn't start from 0, or from 1!),
that the product of the numbers {1 - 1/i : i = 2,...,n} is 1/n.

(I guess you can start from 1 if you want, regarding the LHS as an empty product, so = 1. But the problem doesn't ask you to think about that.)

3. Let f:N->N satisfy
f(0) = 38
f(1) = 39
for all n at least 2, f(n) = 3f(n-1) - 2f(n-2).
Prove that for all n in N, f(n) = 2ⁿ + 37.

Book:
11.6, 11.10, 11.15.
Think hard about 11.7 but don't turn anything in about it.

Scope of lexical binding

Aris asked a very good question: why do we write proofs as "Let x in X...[good thing happens] Since x was arbitrary, we've proven that for all x in X,..." rather than simply "For all x in X, [good thing happens]" ?

I think it has to do with lexical scoping.
When we say "for all x in X", that typically ties up the letter x to mean a certain something until the end of the sentence, or possibly the paragraph. But no further.
For example, one may say "for all i in 1,2,3,...,n" in every sentence, and have i free to mean something different each time.
But when we start out a proof with "Let x be in X" then the reader may assume that x will mean the same fixed element, for the rest of the proof.

Mind you, we're not discussing mathematics here; we're only discussing how mathematics is written and read.
And it's not to say that it isn't prone to error. All the time, in lectures, one hears the speaker (or the audience) say "where this n is not that n" or even just "where n doesn't equal n, of course"

HW #2 due Wednesday April 30 (acceptable Friday)

Let f:X->Y and g:Y->Z be functions.

1. Give an example where g o f is onto, but f is not onto.

2. Assume g o f is 1:1, and f is onto. Show that g is 1:1.

3. Let X have 2 elements and Y have n elements. Show, by induction on n, that the number of 1:1 functions from X to Y is n²-n.

4. Assume that X=Z, so g:Y->X.
The function I:X->X such that I(x)=x for all x in X is called the identity function.
(Every set's got one!)
Call g a left inverse of f if g o f is the identity function on X.

a. If g is a left inverse of f, show that f is 1:1.
b. If f is 1:1 and X is nonempty, show that f has a left inverse.
c. If X is empty, show that f is 1:1, and determine when it has a left inverse.

Midterm with answers

Here.

Office hours Thursday

I am traveling and will be back tomorrow; the Tuesday office hour is moved to Thursday.
Answers to the first midterm will be up soon.

Answers to practice midterm

Here.

Practice midterm

It's here, in PDF.
The actual midterm won't be as tough!

Monday April 14

More about induction proofs.
v1. Case check: either there are no counterexamples (yay), or there is a least one; ... we find a smaller one, and reach a contradiction.
v2. A rewriting of that.
v3. [the contrapositive] if P(m) is true for all m < n, then ... it's true for n; "hence we're done".

Example: every natural number is a product of prime numbers.

Weak induction only uses n-1 to prove n, rather than all m < n to prove n.

Examples: every natural number is even or odd. The sum of the first n integers is n(n+1)/2.

Friday April 11

Proofs.
Proof by case check.
When the cases are "Q is true or Q is false", the proof gets abbreviated, and is called a proof by contradiction. Underneath, it's still really a case check.
Well-ordering axiom of the natural numbers.
Proving something for all natural numbers: if it's not true, then there's a least counterexample.
We saw one way of writing a "proof by induction", using a counterexample to produce a smaller counterexample.

Wednesday April 9

We went back through the proof that subgraphs of bipartite graphs are bipartite.
The main point to absorb here was that
to show something exists (here, a splitting of the subgraph),
the best thing to do is EXHIBIT an example.
This isn't always how it works; there are a very few "pure existence" proofs that don't actually construct an example. But they are very rare, and your first impulse should be to find a recipe for an example.

Here's an example I didn't give in class:
Theorem. For any real number x, there exists a real number y such that x < y < x+1.
Proof. Let y = x + 1/37. Then y satisfies the desired properties. QED.

Note that lots of other recipes would have worked just as well -- we only needed one.

Then we defined circuits in graphs, and headed toward the theorem that circuits in bipartite graphs are always of even length. (Someday we'll prove a converse to this.)

Monday April 7

We reiterated the definition of a graph (V,E) and the degree of a vertex.
We gave a couple of definitions of "regular graph", in which all vertices have the same degree.
I drew two examples thereof, one being the Petersen graph:


We defined bipartite graph and subgraph, and started proving that subgraphs of bipartite graphs are themselves bipartite.

HW #1 due Friday April 11

[Solow] denotes the book. Since not everybody has it I'm typing in these problems.

Turn in
Ch 1, problems 4-9
4. Unpack these English sentences to determine the hypothesis and the conclusion.
a. The sum of the first n positive integers is n(n+1)/2.
b. r is irrational if r is real and satisfies r²=2.
c. If p and q are positive real numbers with SquareRoot(p*q) not = (p+q)/2, then p not = q.
d. When x is a real number, the minimum value of x(x-1) is at least -1/4.

5. "If I do not get my car fixed, I will miss my job interview," says Jack. Later, you come to know that Jack's car was repaired but that he missed his job interview. Was Jack's statement true or false? Explain.

6. Using Table 1.1 (namely, our class definition of "implies" as a mathematical term), determine the conditions on the hypothesis and the conclusion under which the following statements are true and false and give your reason.
a. If 2>7, then 1>3.
b. If 2<7, then 1<3.
c. If x=3, then 1<2.
d. If x=3, then 1>2.

7. Suppose someone says to you that the following statement is true: "If Jack is younger than his father, then Jack will not lose the contest." Did Jack win the contest?

8. If you are trying to prove that "A implies B" and you know B is false, do you want to show A is true or false? Explain.

9. By considering what happens when A is true and when A is false, it was decided that when trying to prove the statement "A implies B" is true, you can assume that A is true and your goal is to show that B is true. Use the same type of reasoning to derive another approach for proving that "A implies B" is true by considering what happens when B is true and when B is false.

Ch 7, problems 2,7,8.
2. Rewrite each of the following using nested quantifiers.
a. A set S of real numbers has the property that, no matter which element is chosen in the set, you can find another element in the set that is strictly larger.
b. A function of a single variable has the property that for some real number, the absolute
value of the function is always less than that real number
7. Prove that for every real number x>2, there is a real number y<0 such that x=2y/(1+y).
8. Prove that if S = {real numbers x>0 : x² < 2}, then for every real number epsilon > 0, there is an element x in S such that x² < 2 - epsilon.

Read Chapter 1 and the other problems within.

I. Let (V,E) be a graph and V' a subset of V, E' a subset of E. What condition need we add in order to say that (V',E') is also a graph? We did this one in class.

(turn in this one too)
II. For p a person and t a time, let fooled(p,t) be true if p is fooled at time t.
Use quantifier notation to write out "You can fool some of the people all of the time, and all of the people some of the time, but you can't fool all the people all of the time." (Abraham Lincoln, paraphrased)

More generally, how is "but" rendered in mathematics-ese?

Wednesday April 2

"or" in English means exclusive or, "or" in mathematics means inclusive.
"implies" in English suggests a logical connection, where "A => B" only means "it never occurs that A is true and B is false". So e.g. if B is always true, then "A => B" is true as a mathematical statement, even if they seem completely unrelated. Same if A is always false!
"is" in English often doesn't translate as =, but as "is an element of". So "Felix is a cat" doesn't mean any cat = Felix, but that Felix is an element of {the set of cats}.

Sets are determined by their elements. Subsets, power sets, union, intersection, cardinality.

Definition of an empty set. Theorem: there is only one empty set (meaning, any two such are equal). Proof: the only thing we know about sets is that they are equal if they have the same elements, which is true for any two empty sets. QED.

Next time: graphs.

Monday March 31

I listed the main things we'll cover: proofs, by checking cases / contradiction / induction, quantifiers, set theory, baby number theory e.g. Euclid's algorithm and prime factorization.

Then we did a bunch of conversion of a quantifier statement and the corresponding English sentence, e.g. the true statement "for every person in the class, there exists a name, such that the person has that name" vs. the false statement "there exists a name, such that for every person in the class, the person has that name". According to the rolls everybody has a name, but not everybody has the same name.

The first homework will be assigned on Friday, though suggested reading in the book will come sooner.

Please print and fill out the survey on the course web page and give it to me on Wednesday.

Welcome to Math 109

This is now the blog for my Math 109 class, where you'll find homework and other timely things. For more static things, see the course website.