Monday, May 28, 2007

One By One, We're Making It Fun. Topic: Calculus/S&S.

Theorem: (Stolz-Cesaro) Let $ \{a_n\} $ and $ \{b_n\} $ be sequences of real numbers such that $ \{b_n\} $ is positive, strictly increasing, and unbounded. If the limit

$ \displaystyle \lim_{n \rightarrow \infty} \frac{a_{n+1}-a_n}{b_{n+1}-b_n} = L $

exists, then the following limit also exists and we have

$ \displaystyle \lim_{n \rightarrow \infty} \frac{a_n}{b_n} = L $.

--------------------

Theorem: (Summation by Parts) If $ \{f_k\} $ and $ \{g_k\} $ are two sequences, then

$ \displaystyle \sum_{k=m}^n f_k(g_{k+1}-g_k) = [f_{n+1}g_{n+1}-f_mg_m]-\sum_{k=m}^n g_{k+1}(f_{k+1}-f_k) $.

--------------------

Problem: Let $ \{a_n\} $ be a sequence of real numbers such that $ \displaystyle \sum_{k=0}^{\infty} a_k $ converges. Show that $ \displaystyle \lim_{n \rightarrow \infty} \frac{1}{n+1} \sum_{k=0}^n k \cdot a_k = 0 $.

Solution: Define the sequence $ \{b_n\} $ by $ \displaystyle b_n = \sum_{k=0}^n a_k $ and let $ \displaystyle \lim_{n \rightarrow \infty} b_n = L $. Then, by summation by parts with $ \{f_n\} = \{n\} $ and $ \{g_n\} = \{b_n\} $, we have

$ \displaystyle \sum_{k=0}^n k \cdot a_k = \sum_{k=0}^n k \cdot (b_{k+1}-b_k) = (n+1)b_{n+1}-\sum_{k=0}^n b_{k+1} $.

The summation we wish to take the limit of is then

$ \displaystyle \frac{1}{n+1} \sum_{k=0}^n k \cdot a_k = b_{n+1}-\frac{1}{n+1} \sum_{k=0}^n b_{k+1} $.

But since, by Stolz-Cesaro,

$ \displaystyle \lim_{n \rightarrow \infty} \frac{1}{n+1} \sum_{k=0}^n b_{k+1} = \lim_{n \rightarrow \infty} b_{n+1} = L $,

we obtain

$ \displaystyle \lim_{n \rightarrow \infty} \frac{1}{n+1} \sum_{k=0}^n k \cdot a_k = \lim_{n \rightarrow \infty} \left(b_n-\frac{1}{n+1} \sum_{k=0}^n b_{k+1}\right) = L-L = 0 $.

QED.

--------------------

Comment: Summation by parts is a very useful technique to change sums around so that they are easier to evaluate. If you hadn't noticed, it is the discrete analogue of integration by parts and is in fact very similar. Stolz-Cesaro is powerful as well and seems like a discrete analogue to L'Hopital (but I'm not sure about this one). Applying well-known calculus ideas to discrete things can often turn into neat results.

--------------------

Practice Problem: If $ \{a_n\} $ is a decreasing sequence such that $ \displaystyle \lim_{n \rightarrow \infty} a_n = 0 $, show that

$ \displaystyle \sum_{k=1}^{\infty} a_k \cdot \sin{(kx)} $

converges for all $ x $.

Saturday, May 12, 2007

Bigger Means Better. Topic: Algebra/Inequalities/Sets. Level: Olympiad.

Definition: A set $ S $ is said to be convex if, for any $ X, Y \in S $ and $ \lambda \in [0,1] $, we have $ \lambda X+(1-\lambda)Y \in S $.

--------------------

Definition: Let $ f: D \rightarrow \mathbb{R} $ be a real-valued function defined on a convex set $ D $. We say that $ f $ is convex if, for all $ X, Y \in D $ and $ \lambda \in [0, 1] $, we have

$ \lambda f(X) + (1-\lambda) f(Y) \ge f(\lambda X+(1-\lambda)Y) $.

--------------------

Theorem: (Jensen's Inequality) Let $ f $ be a real-valued, convex function defined on a convex set $ D $. Given $ x_1, x_2, \ldots, x_n \in D $ and nonnegative reals $ w_1, w_2, \ldots, w_n $ such that $ w_1+w_2+\cdots+w_n = 1 $, we have

$ w_1f(x_1)+w_2f(x_2)+\cdots+w_nf(x_n) \ge f(w_1x_1+w_2x_2+\cdots+w_nx_n) $

or, more concisely,

$ \displaystyle \sum_{i=1}^n w_if(x_i) \ge f\left(\sum_{i=1}^n w_ix_i\right) $.

Proof: We proceed by induction on $ n $.

Base Case - $ n = 1 $, we have $ f(x_1) \ge f(x_1) $ which is trivially true. $ n = 2 $, we have $ \lambda_1 f(x_1)+\lambda_2 f(x_2) \ge f(\lambda_1 x_1+\lambda_2 x_2) $ with $ \lambda_1+\lambda_2 = 1$ which is true by the definition of convexity.

Induction Step - Suppose $ \displaystyle \sum_{i=1}^k w_if(x_i) \ge f\left(\sum_{i=1}^k w_ix_i\right) $. We wish to show

$ \displaystyle \sum_{i=1}^{k+1} u_if(x_i) \ge f\left(\sum_{i=1}^{k+1} u_ix_i\right) $

for nonnegative reals $ u_1, u_2, \ldots, u_{k+1} $ that sum to $ 1 $. Well,

$ \displaystyle f\left(\sum_{i=1}^{k+1} u_ix_i\right) \le u_{k+1}f(x_{k+1})+(1-u_{k+1})f\left(\frac{1}{1-u_{k+1}} \sum_{i=1}^k u_ix_i\right) $

by the definition of convexity. But since $ \displaystyle \frac{1}{1-u_{k+1}} \sum_{i=1}^k u_i = \sum_{i=1}^k \frac{u_i}{1-u_{k+1}} = 1 $, by our inductive hypothesis (the $ k $ term case) we must have

$ \displaystyle f\left(\frac{1}{1-u_{k+1}} \sum_{i=1}^k u_ix_i\right) \le \sum_{i=1}^k \frac{u_i}{1-u_{k+1}} f(x_i) $.

Combining this into the above inequality, we obtain

$ \displaystyle f\left(\sum_{i=1}^{k+1} u_ix_i\right) \le u_{k+1}f(x_{k+1})+(1-u_{k+1})\sum_{i=1}^k \frac{u_i}{1-u_{k+1}} f(x_i) = \sum_{i=1}^{k+1} u_if(x_i) $

as desired, completing the induction. QED.

--------------------

Definition: The convex hull of a set $ S $ is defined to be the smallest convex set containing $ S $. It is the set of all points that can be written as $ \displaystyle \sum_{i=1}^n a_ix_i $, where $ n $ is a natural number, $ a_1, a_2, \ldots, a_n $ are nonnegative reals that sum to $ 1 $, and $ x_1, x_2, \ldots, x_n \in S $.

--------------------

Definition: A vertex of a set $ D $ is a point $ v \in D $ such that for all $ x \in D $ not equal to $ v $ and $ \lambda > 1 $ we have $ \lambda v+(1-\lambda)x \not\in D $.

--------------------

Theorem: Let $ V_D = \{v_1, v_2, \ldots, v_k\} $ be the set of vertices of a compact convex set $ D $. The convex hull of $ V_D $ is $ D $.

Example: The set of vertices of a convex polygon is, in fact, its vertices as traditionally defined in geometry. Any point inside the polygon can be written as a convex combination of its vertices.

--------------------

Theorem: If $ f $ is a real-valued, convex function defined on a compact convex set $ D $, then $ \displaystyle \max_{x \in D} f(x) = \max_{x \in V_D} f(x) $, where $ V_D $ is the set of vertices of $ D $.

Proof: We will show that $ \displaystyle f(x) \le \max_{x \in V_D} f(x) $ for all $ x \in D $.

Let $ \displaystyle x = \sum_{i=1}^k \lambda_i v_i $ where $ \lambda_1, \lambda_2, \ldots, \lambda_k $ are nonnegative reals that sum to $ 1 $ and $ V_D = \{v_1, v_2, \ldots, v_k\} $. This is possible by the preceding theorem. Then by Jensen's Inequality we get

$ \displaystyle \sum_{i=1}^k \lambda_i f(v_i) \ge f\left(\sum_{i=1}^k \lambda_i v_i\right) = f(x) $.

And since $ \displaystyle \max_{x \in V_D} f(x) \ge \sum_{i=1}^k \lambda_i f(v_i) $, we have $ \displaystyle \max_{x \in V_D} f(x) \ge f(x) $ for all $ x \in D $. Furthermore, since $ V_D $ is a subset of $ D $, we know that this maximum is attained, thus

$ \displaystyle \max_{x \in D} f(x) = \max_{x \in V_D} f(x) $

as desired. QED.

--------------------

Comment: This is a very useful result, as it allows us to limit our search for the maximum of a function to its set of vertices, which is usually a considerably smaller set, though it may still be infinite (think sphere). In any case, this works well for constrained optimization problems in which the domain is limited to a polygon, the easiest application of this theorem.

--------------------

Practice Problem: Let $ x $ and $ y $ be real numbers satisfying $ |2x-y| \le 3 $ and $ |y-3x| \le 1 $. Find the maximum value of $ f(x, y) = (x-y)^2 $.

Tuesday, May 8, 2007

A Square of Divisors. Topic: Number Theory. Level: AIME/Olympiad.

Problem: (1999 Canada - #3) Determine all positive integers $ n > 1 $ with the property that $n = (d(n))^2$. Here $d(n)$ denotes the number of positive divisors of $n$.

Solution: So, testing some small numbers yields $ n = 9 $ as a solution. We claim that this is the only such solution.

Clearly, since $ n $ is a square, we can use a variant of the usual prime decomposition and say that $ n = p_1^{2e_1} p_2^{2e_2} \cdots p_k^{2e_k} $.

Furthermore, again since $ n $ is a square, we know

$ d(n) = (2e_1+1)(2e_2+1) \cdots (2e_k+1) $

is odd, so $ n = (d(n))^2 $ must be odd as well, i.e. $ 2 $ is not one of the $ p_i $. Then we use the equation given to us to get

$ p_1^{2e_1} p_2^{2e_2} \cdots p_k^{2e_k} = (2e_1+1)^2(2e_2+1)^2 \cdots (2e_k+1)^2 $

$ p_1^{e_1} p_2^{e_2} \cdots p_k^{e_k} = (2e_1+1)(2e_2+1) \cdots (2e_k+1) $.

Note, however, that by Bernoulli's Inequality (overkill, I know) we have for $ i = 1, 2, \ldots, k $

$ (1+(p_i-1))^{e_i} \ge 1+(p_i-1)e_i \ge 2e_i+1 $

with equality iff $ p_i = 3 $ and $ e_i = 1 $. So

$ p_1^{e_1} p_2^{e_2} \cdots p_k^{e_k} \ge (2e_1+1)(2e_2+1) \cdots (2e_k+1) $.

Since we want equality, we must have $ p_i = 3 $ and $ e_i = 1 $ for all $ i $. But since the primes are supposed to be distinct we can have exactly one prime so that $ n = 3^2 = 9 $ is the only solution. QED.

--------------------

Comment: Another one of those problems that you kind of look at the result and you're like huh, that's interesting. But anyway, just throwing in some weak inequalities led to a pretty straightforward solution. As long as you know how to find the number of divisors of a positive integer it isn't too much of a stretch to figure the rest out, though it make take some time to get in the right direction since the problem is quite open-ended.

--------------------

Practice Problem: (1999 Canada - #4) Suppose $a_1,a_2,\cdots,a_8$ are eight distinct integers from $\{1,2,\ldots,16,17\}$. Show that there is an integer $k > 0$ such that the equation $a_i - a_j = k$ has at least three different solutions. Also, find a specific set of $7$ distinct integers from $\{1,2,\ldots,16,17\}$ such that the equation $a_i - a_j = k$ does not have three distinct solutions for any $k > 0$.

Saturday, May 5, 2007

Ready For AP Calculus? Topic: Calculus/S&S. Level: AIME/Olympiad.

Problem: Evaluate $ \displaystyle \sum_{n=1}^{\infty} \frac{1}{n^2 \cdot 2^n} $.

Solution: Let $ \displaystyle f(x) = \sum_{n=1}^{\infty} \frac{x^n}{n^2} $. Then $ \displaystyle f^{\prime}(x) = \sum_{n=1}^{\infty} \frac{x^{n-1}}{n} = -\frac{\ln{(1-x)}}{x} $, a well-known Taylor series. So we want to integrate this:

$ \displaystyle \int \frac{\ln{(1-x)}}{x}dx = \ln{x} \ln{(1-x)}-\int \frac{\ln{x}}{x-1}dx $

by parts using $ u = \ln{(1-x)} $ and $ dv = dx/x $. Substituting $ t = 1-x $ in the last integral, we have

$ \displaystyle \int \frac{\ln{(1-x)}}{x}dx = \ln{x} \ln{(1-x)}-\int \frac{\ln{(1-t)}}{t}dt $.

So $ -f(x) = \ln{x} \ln{(1-x)}+f(t)+C = \ln{x} \ln{(1-x)}+f(1-x)+C $. Thus

$ f(x)+f(1-x) = C-\ln{x} \ln{(1-x)} $

for some constant $ C $. Using our knowledge that $ f(0) = 0 $, $ \displaystyle f(1) = \frac{\pi^2}{6} $, and $ \displaystyle \lim_{x \rightarrow 1} \ln{x} \ln{(1-x)}= 0 $ by L'Hopital twice, we see that

$ f(0)+f(1) = C \Rightarrow C = \frac{\pi^2}{6} $

Then setting $ x = \frac{1}{2} $ we obtain $ \displaystyle 2f\left(\frac{1}{2}\right) = \frac{\pi^2}{6}-\ln{\frac{1}{2}} \ln{\frac{1}{2}} $ and $ \displaystyle \sum_{n=1}^{\infty} \frac{1}{n^2 \cdot 2^n} = f\left(\frac{1}{2}\right) = \frac{\pi^2}{12}-\frac{\ln^2{(2)}}{2} $. QED.

--------------------

Comment: This was a pretty tough problem that required you to compound a lot of calculus knowledge all into a single problem - series, integration by parts, limits. Recognizing all the steps was the first part; following through with the right computations was another. Still, there weren't really any super clever tricks, mostly just standard substitutions and approaches applied in a somewhat non-standard way. Makes for a very nice problem.

--------------------

Practice Problem #1: Show that $ \displaystyle \lim_{x \rightarrow 1} \ln{x} \ln{(1-x)} = 0 $.

Practice Problem #2: Evaluate $ \displaystyle \sum_{n=1}^{\infty} \frac{x^n}{n} $. Can you also find $ \displaystyle \sum_{n=1}^{\infty} \frac{x^n}{n^3} $?