November 22 Summary

We did talk a while about the first unexam. I want to stress that this is not supposed to be an exercise about counting or doing counting problems, it is all about the writing. I want you to explain something from first principles including only sentences which you need in order to explain the solution. It will be due on December 6, 2007.

Next we talked about the Euler phi function, phi(n). I said it was easy to show that for gcd(p,n)=1, p prime
phi(p^a n) = (p^a - p^(a-1)) phi(n)

But then I spent about a half hour trying to explain why that is true. I said, consider the set of elements which are between 1 and p^a n such that have gcd(k,n) =1. By the division algorithm k = q n + r where 0 ≤ r < n and 0 ≤ q < p^a and if gcd(k,n)=1 then we must have gcd(r,n)=1. That is,
(first set) = { k : gcd(k,n)=1, 1 ≤ k < p^a n } = { q n + r : 0 ≤ q < p^a, 0 ≤ r < n, gcd(r,n)=1 }
From these elements we want to subtract off those such that gcd(k,p) > 1. That is we remove the subset of integers
(second set) = { p q n + p r : 0 ≤ q < p^(a-1), 0 ≤ r < n, gcd(r,n)=1}
because every integer in the first set that contains a factor of p will look like this. Now how many choices are there for q and r? In the first set 0 ≤ q < p^a, so q has p^a choices and r has phi(n) choices. In the second set q has p^(a-1) choices and r still has phi(n) choices. Therefore the number of elements in the first set which are not in the second are
p^a phi(n) - p^(a-1) phi(n)

It follows roughly immediately that phi(n) is "multiplicative" since if m = p1^a1 p2^a2 ... pk^ak and n is relatively prime to n then
phi( m ) = (p1^a1-p1^(a1-1)) phi( p2^a2 ... pk^ak)
= (p1^a1-p1^(a1-1)) (p2^a2-p2^(a2-1)) phi( p3^a3... pk^ak)
= ...
= (p1^a1-p1^(a1-1)) ( p2^a2 - p2^(a2-1)) ... (pk^ak - pk^(ak-1))
and moreover
phi( mn ) = (p1^a1-p1^(a1-1)) phi( p2^a2 ... pk^ak n)
= ...
= (p1^a1-p1^(a1-1)) ( p2^a2 - p2^(a2-1)) ... (pk^ak - pk^(ak-1)) phi(n)
= phi(m) phi(n).

Next we talked about sequences in general. We have several example of sequences which represent the number of "things in a set."
* the number of integers between 1 and n relatively prime to n = phi(n)
* the number of divisiors of n = d(n)
* the number of subsets of size 3 of a three element set = C(n,3)
* the number of orderings of the numbers 1 through n = P(n,n) = n!

I can go on, these are just a few that we have explicitly encountered so far in this class. Some of the homework problems have involved others. Now consider an abstract sequence of numbers where the i^th element in the sequence represents the number of something of "size" i.
a_0, a_1, a_2, a_3, a_4, ...
I call these somethings widgets, to represent an unknown object so that the number a_i represents the number of widgets of size i. Then I said to make things interesting we can also talk about another sequence of non-negative integers which represents the number of doodles of size i.
b_0, b_1, b_2, b_3, b_4, ...
Then I asked what does the expresson
a_3 b_7 + a_1
represent? I suggested it was the number of widgets of size 1 or the number of ways of taking a widget of size 3 and tying it to a doodle of size 7 with rubber bands. We then did a worksheet together in class with exercises of this sort.

-----Added later because someone asked for a better explanation of this worksheet. ------

It is easier to go from the lettered descriptions to the numbered expressions than the other way around.
for example, the first one is:
(a) A pair consisting of a widget and a doodle such that the doodle is of size less than or equal to n and itÊ is one size larger than the widget

By a pair I mean and ordered tuple consisting of two elements. the doodle of size 1 through n (it can't be 0 because there are no widgets of size -1). If the doodle is of size k then the widget is of size k-1 and there are a_{k-1} b_k such pairs.

By the addition principle there are
a_0 b_1 + a_1 b_2 + ... + a_{n-1} b_n

such pairs (since either the doodle is of size 1, or it is of size 2, or ... or it is of size n).

This matches with (13).

I will try posting the answers to this worksheet here later, but you should try to do them yourself first.

-Mike