414/514 – Partitions

October 31, 2011

I while ago I posted a short note on integer partitions and generating functions. I am adding a link here, as it is obviously connected to the combinatorial applications of power series we have been considering.

There are some excellent books on the topic of generating functions. The classic, generatingfunctionology, can be downloaded for free at the website of the author, Herbert Wilf.

Another nice reference is Analytic combinatorics, by Philippe Flajolet and Robert Sedgewick. It can be downloaded for free at Flajolet’s website.

Finally, a classic in analysis that in particular covers this material nicely is the book by Pólya and \mbox{Szeg\H o}, Problems and Theorems in Analysis. It is a work in two volumes. Series are studied in the first one.

414/514 – Limit points

October 28, 2011

The argument in today’s lecture depended at the end on the following fact:

Suppose that A is an uncountable subset of {\mathbb R}. Then A admits a limit point. In fact, if A\subseteq(-r,r), then A admits a limit point x_0 with {}|x_0|<r.

The proof should be standard by now but, for completeness, here is one way of seeing this:

Before we begin, recall that we already know that a bounded infinite set has a limit point. So, either A is unbounded, or else it has a limit point. But even if we know that A\subseteq(-r,r), so it certainly is bounded, we are not quite done yet because the limit point could be r or -r.

Recall as well that the countable union of countable sets is countable.

First, we may assume A is bounded. This is because

\displaystyle A=\bigcup_n A\cap(-n,n),

so for some n we must have A\cap(-n,n) is uncountable so, even if A is unbounded, we can replace it with the uncountable bounded set A\cap(-n,n).

Let I_0=(-n,n) or, if we are given that A\subseteq(-r,r) to begin with, let I_0=(-r,r). So we can assume A\subseteq I_0. Write I_0=(-a,a) so we do not have to distinguish between both cases. For n\ge1, let

\displaystyle I_n=\left(-a+\frac1n,a-\frac1n\right).

Then A=\bigcup_{n\ge1} A\cap I_n, and it follows that for some n\ge1 we must have A\cap I_n is uncountable.

Now, we know that any infinite bounded subset of the reals has a limit point, so A\cap I_n has a limit point. This point in absolute value has size at most \displaystyle a-\frac1n<a, but this is what we needed.

In fact, one can extend this argument to see that any uncountable set has an uncountable set of limit points, but we did not need this for today’s argument.

Added: You may find interesting this recent question in MathOverflow.

414/514 – Multiplying power series

October 25, 2011

In lecture today we argued that under reasonable circumstances, the product of two power series is the series given by their “formal” product. I think I unnecessarily made the argument more complicated than it is, so I am writing it here so we have a clean reference.

Let \displaystyle A(x)=\sum_{j=0}^\infty a_j x^j and \displaystyle B(x)=\sum_{j=0}^\infty b_j x^j. Suppose that both A and B converge absolutely and uniformly in the interval {}[-r,r]. We want to prove that for x\in[-r,r], we also have

\displaystyle A(x)B(x)=\sum_{j=0}^\infty\left(\sum_{i=0}^j a_i b_{j-i}\right)x^j,

and this latter series converges absolutely and uniformly in {}[-r,r].

To see this, let \displaystyle A_N(x)=\sum_{j=0}^N a_j x^j and \displaystyle B_N(x)=\sum_{j=0}^N b_j x^j denote the partial sums of A and B, and denote by \displaystyle P_N(x)=\sum_{m=0}^N\left(\sum_{j+k=m}a_j b_k\right)x^m the partial sums of the “formal product” series.

We want to show that \displaystyle\lim_{N\to\infty}P_N(x)=A(x)B(x).

Let us call R_N(x) the “remainder” or “tail” series of B(x), i.e., \displaystyle R_N(x)=B(x)-B_N(x)=\sum_{j=N+1}^\infty b_j x^j.

We have that P_N(x)=a_0B_N(x)+a_1xB_{N-1}(x)+\dots+a_N x^N B_0(x) =a_0(B(x)-R_N(x))+a_1 x (B(x)-R_{N-1}(x))+\dots +a_N x^N (B(x)-R_0(x)). Expanding this last expression, we find that it equals B(x)\sum_{j=0}^Na_j x^j-[a_0R_N(x)+a_1 xR_{N-1}(x)+\dots +a_N x^N R_0(x)].

Now, B(x)\sum_{j=0}^Na_j x^j=B(x)A_N(x) clearly converges to B(x)A(x) as N\to\infty, and the convergence is uniform in the interval {}[-r,r].

We want to show that the remaining term a_0R_N(x)+a_1 xR_{N-1}(x)+\dots+a_N x^N R_0(x) converges to 0 and does so uniformly in the interval {}[-r,r].

First, since B_n(x)\to B(x) uniformly as n\to\infty, then for any \epsilon>0 there is an N_0 such that if n\ge N_0 then {}|R_n(x)|<\epsilon for all x\in[-r,r].  If N>N_0, we can split the sum above as S_1(x)+S_2(x), where

\displaystyle S_1(x)=a_0 R_N(x)+a_1 x R_{N-1}(x) + \dots + a_{N-N_0}x^{N-N_0} R_{N_0}(x)


\displaystyle S_2(x)=\sum_{j=N-N_0+1}^N a_j x^j R_{N-j}(x).

Note that |S_1(x)|\le\epsilon\sum_{j=0}^{N-N_0}|a_j x^j|\le K\epsilon, where K is the constant \sum_j |a_j|r ^j. This shows that S_1(x)\to0 uniformly for x\in{}[-r,r].

To bound S_2, note that it is a sum of a constant number of terms, namely N_0. The functions R_{N_0-1},R_{N_0-2},\dots,R_0 are continuous and bounded in the interval {}[-r,r], so there is a constant L that bounds all of them (and, of course, L does not depend on N). Hence

\displaystyle |S_2(x)|\le L\sum_{j=N-N_0+1}^N |a_jx^j|\le L\sum_{j\ge N-N_0+1} |a_j|r^j.

Since \sum_j|a_j|r^j converges, there is an N_1 such that if n\ge N_1, then \sum_{j\ge n}|a_j|r^j<\epsilon.

Pick N so that N-N_0>N_1. Then |S_2(x)|<L\epsilon. We have now shown that |S_1(x)+S_2(x)|\to0 uniformly for x\in{}[-r,r], and this completes the proof.

(We also claimed that the convergence is absolute. To see this, replace all the terms a_j,b_j,x^j,\dots above by their absolute values. The same argument shows convergence of the relevant series, so we indeed have absolute convergence.)

414/514 – Continuity

October 24, 2011

This is homework 4, due Monday, October 31, at the beginning of lecture.

Suppose that f: {\mathbb R}\to{\mathbb R} and that a\in{\mathbb R}. We write

\displaystyle \lim_{x\to a^-}f(x)=L

iff for all \epsilon>0 there is a \delta>0 such that whenever 0<a-x<\delta, then |f(x)-L|<\epsilon. In this case, we say that f converges to L as x approaches a from the left.

Similarly, we define convergence from the right:

\displaystyle \lim_{x\to a^+}f(x)=R

iff for all \epsilon>0 there is a \delta>0 such that whenever 0<x-a<\delta, then |f(x)-R|<\epsilon. In this case, we say that f converges to R as x approaches a from the right.

In terms of these notions, we see that \lim_{x\to a}f(x) exists iff both \lim_{x\to a^-}f(x) and \lim_{x\to a^+}f(x) exist, and are equal, in which case \lim_{x\to a}f(x) equals their common value.

The function f is said to have a jump discontinuity (or a type I discontinuity, or a simple discontinuity, or a discontinuity of the first kind) at a, iff both \lim_{x\to a^-}f(x) and \lim_{x\to a^+}f(x) exist, but either they are not equal, or they are equal to each other, but not to f(a). Sometimes the notation f(a-) is used for \lim_{x\to a^-}f(x), provided that it exists and,  similarly, f(a+) is used to denote \lim_{x\to a^+}f(x), if it exists.

If f is discontinuous at a, but not through a jump discontinuity, we say that f has a type II discontinuity (or a discontinuity of the second kind) at a.

Recall that f is monotone iff it is either monotonically increasing or monotonically decreasing. The first alternative means that f(a)\le f(b) whenever a\le b. The second means that f(a)\ge f(b) whenever a\le b.

Read the rest of this entry »

187 – Mathematics – Stack Exchange

October 22, 2011

I have mentioned a few times the website http://math.stackexchange.com/ and suggested that you take a look at it and use it as a resource. I believe it is a really useful site when used appropriately. Some of you have asked for additional references, and I think this site may help supply some of them.

Here is a short list of questions posted on the site that may give you an idea of its value:

414/514 – Continuous nowhere differentiable functions

October 22, 2011

There are many excellent sources on the topic of continuous nowhere differentiable functions. Johan Thim’s Master thesis, written under the supervision of  Lech Maligranda, is available online, here, but feel free to use any other sources you find relevant.

As a final project for the course, please choose an example of a continuous nowhere differentiable function, either from Thim’s thesis or elsewhere, and write a note on who it is due to and what the function is, together with complete proofs of continuity and nowhere differentiability. Feel free to add additional information you consider relevant for context.

Contact me (by email) as soon as you have chosen the example you will work on, to avoid repetitions; I will add your name and the chosen example to the list below as I hear from you.

Please take this project very seriously (in particular, do not copy details from books or papers, I want to see your own version of the details as you work through the arguments). Feel free to ask for feedback as you work on it; in fact, asking for feedback is a good idea. Do not wait until the last minute. At the end, it would be nice to make at least some of the notes available online, please let me know when you turn it in whether you grant me permission to host your note on this blog.

The project is due Wednesday, December 14, by noon, but feel free (and encouraged) to turn it in earlier.

List of projects:

  • Diana Kruse: Bolzano function.
  • Jesse Tillotson: Weierstrass function.
  • Erron Kearns: Katsuura function.
  • David Sanchez: Peano function.
  • Shehzad Ahmed: Faber functions.
  • Chip Roth: McCarthy function.
  • Jeremy Ryder: Schoenberg functions.

187 – Presentation

October 21, 2011

Kevin Byrne will give a short presentation on Wednesday, October 26, on Alan Turing and Turing machines. Here is a link to the official page of the Alan Turing Year.