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.

Advertisement

Leave a Comment » | 414/514: Analysis I | Permalink
Posted by andrescaicedo

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.

Leave a Comment » | 414/514: Analysis I | Permalink
Posted by andrescaicedo

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)

and

\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.)

Leave a Comment » | 414/514: Analysis I | Permalink
Posted by andrescaicedo

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 »

Leave a Comment » | 414/514: Analysis I | Permalink
Posted by andrescaicedo

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:

Leave a Comment » | 187: Discrete mathematics | Permalink
Posted by andrescaicedo

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.

2 Comments | 414/514: Analysis I | Tagged: , , | Permalink
Posted by andrescaicedo

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.

Leave a Comment » | 187: Discrete mathematics | Permalink
Posted by andrescaicedo

596 – Continued fractions

October 10, 2011

This term, Summer Hansen is taking a reading course with me on Pell’s equation. Our basic reference is:

  • Jacobson and Williams, Solving the Pell equation. CMS Books in Mathematics/Ouvrages de Mathématiques de la SMC. Springer, New York, 2009. xx+495 pp. ISBN: 978-0-387-84922-5.

We are allowing a rather organic approach to the material, taking as many detours as it seems appropriate. The topic of continued fractions naturally came up. What follows is just a short compendium of results I found interesting while reading on the subject.

Read the rest of this entry »

1 Comment | 496/596: Independent study | Tagged: , , , | Permalink
Posted by andrescaicedo

187 – Arguing by contradiction

October 10, 2011

[Edit: I have extended the deadline until the day of the final exam.]

Here are some extra credit problems. They are due at the latest by November 1, the day of the second midterm (just turn them in when you come to take the test), but you can of course turn them earlier. You can turn in as many as you want, this is completely voluntary.

All these problems can be solved arguing by contradiction. They tend to require at least one additional idea. The problems come for Loren C. Larson’s book “Problem-solving through problems.”

  1. In a party with 2000 people, among any set of four there is at least one person who knows each of the other three. There are three people who are not mutually acquainted with each other. Prove that the other 1997 people know everyone at the party. (Assume that whenever a person A knows a person B, then also B knows A.)
  2.  Prove that there are no positive integers a, b, c, and n such that a^2+b^2+c^2=2^n abc.
  3. Every pair of communities in a country are linked directly by exactly one mode of transportation: bus, train, or airplane. All three modes of transportation are used in the country; no community is served by all three modes, and no three communities are linked pairwise by the same mode. For example, four communities can be linked according to these stipulations in the following way: bus, AB, BC, CD, DA; train, AC; airplane, BD.
    1. Give an argument to show that no community can have a single mode of transportation leading to each of three different communities.
    2. Give a proof to show that five communities cannot be linked in the required manner.
  4. Let S be a set of rational numbers with the property that whenever a and b are (not necessarily distinct) elements of S, then also a+b\in S and ab\in S. Moreover, suppose that for any rational number r, exactly one of the following is true: r\in S, -r\in S, r=0.
    1. Prove that 0 does not belong to S.
    2. Prove that all positive integers belong to S.
    3. Prove that S is the set of all positive rational numbers.

Leave a Comment » | 187: Discrete mathematics | Permalink
Posted by andrescaicedo

414/514 – Compactness

October 9, 2011

Here are some extra credit problems dealing with the notion of compactness. The deadline to turn them in is Wednesday, December 14, at noon. I will not post hints for now, but feel free to stop by my office as you work on the problems, if you want to double check how your approach is going, and we may discuss suggestions then. These results are proved in different sources, try not to look these solutions up.

  • (Vitali’s covering lemma)

Suppose that (X,d) is a metric space and K\subseteq X is compact. Let \{B_{\epsilon_i}(x_i)\mid i\in I\} be an open covering of K. Show that there is a finite set J\subseteq I such that the balls B_{\epsilon_i}(x_i) for i\in J are pairwise disjoint, and

K\subseteq\bigcup_{i\in J}B_{5\epsilon_i}(x_i).

If X={\mathbb R}, can the constant 5 be improved? (I.e., can it be replaced by a smaller number?) If so, can you find the optimal constant?

The Vitali covering lemma has nice consequences. For example, it allows us to prove Lebesgue’s differentiation theorem.

  • (Antisocial coverings)

This is a result of Krantz and Parsons. Again, let (X,d) be a metric space. A self-centered covering of a non-empty subset S\subseteq X is a collection \{B_{r_x}(x)\mid x\in S\} of open balls, with open ball centered at each point of S. An antisocial family is a collection of balls with the property that if B_\alpha(x) and B_\beta(y) are distinct balls in the collection, then x\notin B_\beta(y) and y\notin B_\alpha(x). Prove the following:

Suppose that {\mathcal C}=\{B_{r_x}(x)\mid x\in K\} is a self-centered covering of the compact set K, and suppose that the function x\mapsto r_x is continuous on K. Then there is an antisocial family {\mathcal A}\subseteq {\mathcal C} that covers K.

Also, show that any such family {\mathcal A} must be finite. Can you find a “reasonable” assumption on the map x\mapsto r_x, not as restrictive as continuity, but sufficient to ensure the result?

(By the way, the topic of covering theorems is very interesting. Let me know if you think you may want to explore this further.)

Leave a Comment » | 414/514: Analysis I | Permalink
Posted by andrescaicedo

« Previous Entries