\ie\cf
\newcommand{\eqdef}{\mathbin{\stackrel{\rm def}{=}}}  \newcommand{\R} % real numbers  \newcommand{\N}} % natural numbers  \newcommand{\Z} % integers  \newcommand{\F} % a field  \newcommand{\Q} % the rationals  \newcommand{\C}{\mathbb{C}} % the complexes  \newcommand{\poly}}  \newcommand{\polylog}}  \newcommand{\loglog}}}  \newcommand{\zo}{\{0,1\}}  \newcommand{\suchthat}  \newcommand{\pr}[1]{\Pr\left[#1\right]}  \newcommand{\deffont}{\em}  \newcommand{\getsr}{\mathbin{\stackrel{\mbox{\tiny R}}{\gets}}}  \newcommand{\Exp}{\mathop{\mathrm E}\displaylimits} % expectation  \newcommand{\Var}{\mathop{\mathrm Var}\displaylimits} % variance  \newcommand{\xor}{\oplus}  \newcommand{\GF}{\mathrm{GF}}  \newcommand{\eps}{\varepsilon}  \notag
\no
Back to MB3

Week 5 Notes

100%

This week is Countdown week, so the notes are going to be a bit shorter than normal.

Take some time to review the material from the first 4 weeks.

Sequences

What is a sequence? Well, it is just an infinite list of numbers. That's it, really. There are two special types of sequences we care about, however.

Arithmetic Sequence

An arithmetic sequence is a sequence in which consecutive elements have constant difference. More precisely, given a sequence \(a_1,a_2,\ldots\), if $$a_2-a_1=a_3-a_2=\ldots$$we would call \(a_1,\ldots\) an arithmetic sequence.
Show that if \(a_1,\ldots\) is an arithmetic sequence, $$a_n=a_1+(n-1)\cdot(a_2-a_1)$$
Show that if \(a_1,\ldots\) is an arithmetic sequence, $$\sum\limits_{i=1}^na_i=na_1+\frac{n\cdot(n-1)}2\cdot(a_2-a_1)$$

Geometric Sequence

An geometric sequence is a sequence in which consecutive elements have constant ratios. More precisely, given a sequence \(a_1,a_2,\ldots\), if $$\frac{a_2}{a_1}=\frac{a_3}{a_2}=\ldots$$we would call \(a_1,\ldots\) an geometric sequence.
Show that if \(a_1,\ldots\) is an geometric sequence, $$a_n=a_1\cdot\left(\frac{a_2}{a_1}\right)^{n-1}$$
If \(r\neq1\), $$\sum\limits_{i=0}^{n-1}ar^i=a\cdot\frac{r^n-1}{r-1}$$If \(r=1\), the sequence is an arithmetic sequence.


Assume \(r\neq1\). Then $$(a+ar+\ldots+ar^{n-1})\cdot(r-1)=a\cdot(1+r+\ldots+r^{n-1})\cdot(r-1)$$$$=a\cdot(r^n-1)$$

Unlike arithmetic sequences, which we can only take finite sums of, we can consider infinite sums of geometric sequences. Suppose I have a geometric sequence \(a_1,\ldots\), with \(r=\frac{a_2}{a_1}\).

If \(|r|\geq1\), then it is clear that unless \(a_1=0\), \(\sum\limits_{i=1}^\infty a_i\) is \(\pm\infty\), or just not defined.

But, if \(|r|\lt1\), \(\sum\limits_{i=0}^\infty ar^i\) has a finite value. Here's how we can find it.

Let \(S=\sum\limits_{i=0}^\infty ar^i\). So, $$S=a+ar+\ldots$$$$rS=ar+ar^2+\ldots$$$$a+rS=a+ar+\ldots=S$$$$a+rS=S$$$$S=\frac a{1-r}$$

As an example of geometric series, suppose we wanted to compute the sum of all of the divisors of \(n\). We'd first prime factorize \(n\) as \(p_1^{e_1}p_2^{e_2}\ldots p_k^{e_k}\). Then, we observe that all divisors of \(n\) are of the form \(p_1^{a_1}\cdot\ldots\cdot p_k^{a_k}\), where \(a_i\leq e_i\) for each \(i\). Thus, the sum of divisors of \(n\) is $$(1+p_1+\ldots+p_1^{e_1})\cdot\ldots\cdot(1+p_k+\ldots+p_k^{e_k})$$However, each term is a geometric series, so we can replace each term by \(\frac{p_i^{e_i+1}-1}{p_i-1}\). Thus, our formula becomes $$\prod\limits_{i=1}^k\frac{p_k^{e_k+1}-1}{p_k-1}$$ (Side Note: \(\prod\) is similar to \(\sum\), except it is for products rather than sums.)

Challenge: Convexity

You may have learned about convex polygons before.

A convex polgyon is a polygon with all angles having measure less than \(180^\circ\)

Why do we call these polygons convex? What does it mean to be convex? In this section, we'll only be concerned with shapes in the cartesian plane, although convexity can be studied in other spaces, too.

A set of points in the plane is called a convex shape if for any two points in the shape, the line segment between these two points is inside the shape.

Can you see why the convex polygon in the diagram above is convex? Can you see why the concave polygon is not convex? If not, we'll prove it.

Convex polygons are convex, and concave polygons are not convex.


Like many theorems about convexity, the theorem seems obvious, but the proof is certainly not.

Convex polygons are convex: Suppose \(P\) is a convex polygon. Then, if there exists points \(A,B\) in the polygon such that the line segment \(AB\) is not contained in \(P\), then \(AB\) separates the exterior of \(P\) into multiple regions, including at least one polygon. Call one of these polygons \(Q\). Consider the vertex \(x\) of \(Q\) farthest from the line segment \(AB\) (pick any if there is a tie). Clearly, since \(2\) of the vertices of \(Q\) are on \(AB\), and there are at least \(3\) vertices of a polygon, the vertex \(x\) is not on line segment \(AB\). Thus, it is also a vertex of polygon \(P\). Since all angles of \(P\) have \(\lt180^\circ\), the angle \(x\) in polygon \(Q\) has \(\gt180^\circ\) as it is the exterior angle of \(P\) at vertex \(x\). But this implies that at least one of the two neighboring vertices to \(x\) is farther from \(AB\) than \(x\) is, a contradiction. Thus, if \(P\) is a convex polygon, it is a convex shape.

Concave polygons are not convex: Suppose \(P\) is a concave polygon, with vertices \(A,B,C\) such that \(\angle ABC\) in the polygon has measure \(\gt180^\circ\). Consider the triangle \(\triangle ABC\). Clearly, \(\angle B\) in this triangle is the complement of \(\angle B\) in the polygon, since triangles can't have angles larger than \(180^\circ\). Thus, there exists a point inside \(\triangle ABC\) not contained in polygon \(P\). However, the line segments starting at point \(A\), and ending on points on the line segment \(BC\), go through all the point in the triangle \(\triangle ABC\). Thus, at least one of them is not contained in \(P\), implying that \(P\) is not a convex shape.

An important application of convexity is perimeter.

Given convex shapes \(A,B\) such that \(A\) is contained in \(B\), the perimeter of \(A\) is \(\leq\) the perimeter of \(B\). And, for any shape \(C\), there exists some convex shape \(D\) that contains \(C\) such that its perimeter is \(\leq\) that of \(C\).
In week \(1\), we discussed approximating the perimeter of the circle with regular polygons. But we have to be careful with this logic. Consider the following picture.

If we take a square around a circle, and invert its corners repeatedly until it looks like a circle, we can approximate the perimeter of the circle. But, doing so doesn't change the perimeter of the square, so this shows that the perimeter of the unit circle is \(16\), right? The issue with this argument is that the polygon formed by inverting the corners of the square isn't convex, so our perimeter approximation argument no longer holds. The only reason the perimeter approximation argument from Week 1 works is because the regular polygons we used to approximate the circle are convex.

Convex Functions

The most common use case of convexity are convex functions.

Given a function \(f\) from a subset of the real numbers to the real numbers, \(f\) is a convex function if the area above the graph of \(f\) in the cartesian plane is a convex shape.

The following function (in dark orange) is an example of a convex function, since the area above the function (in light orange) is a convex shape.

On the other hand, the following function is not convex, as the area above the function is not a convex shape.

So how do we characterize convex functions? For any numbers \(x_1,x_2\) in the domain of \(f\), if the line segment between points \((x_1,f(x_1))\) and \((x_2,f(x_2))\) is above the function \(f\), then \(f\) is convex, as in the following diagram:

We can write this condition as follows: for any numbers \(x_1,x_2\) in the domain of \(f\) and \(t\in[0,1]\),$$tf(x_1)+(1-t)f(x_2)\geq f(tx_1+(1-t)x_2)$$This inequality, known as Jensen's inequality, is an alternate way to define convex functions. We can also define concave functions to be functions for which the area below the function is convex, or in other words, the negation of convex functions.

  • Can you show that a function \(f\) is concave if and only if for all real numbers \(x_1,x_2\) and \(t\in[0,1]\), \(tf(x_1)+(1-t)f(x_2)\leq f(tx_1+(1-t)x_2)\)
  • Can you find a function which is neither convex nor concave?

To demonstrate the usefulness of these ideas, we'll prove a famous inequality known as the Arithmetic Mean-Geometric Mean inequality (sometimes written as AM-GM). If you haven't learned about logarithms or induction, I'd suggest waiting till Weeks 12 and 14 before reading any further.

Given positive numbers \(x_1,\ldots, x_n\), $$\frac{x_1+x_2+\ldots+x_n}n\geq(x_1\cdot x_2\cdot\ldots\cdot x_n)^{1/n}$$


Since \(\ln\) is an increasing function, the given inequality is true if and only if $$\begin{aligned}\ln\left(\frac{x_1+x_2+\ldots+x_n}n\right)&\geq\ln(x_1\cdot x_2\cdot\ldots\cdot x_n)^{1/n}\\&\geq\frac{\ln x_1+\ln x_2+\ldots+\ln x_n}n\end{aligned}$$We'll prove this inequality to be true using Jensen's inequality and induction.

Base Case: \(n=1\): for any positive \(x_1\), \(\ln \frac{x_1}1\geq\frac{\ln x_1}1\)

Inductive Case: Suppose that for any positive \(x_1,\ldots,x_n\), the inequality below holds$$\ln\left(\frac{x_1+x_2+\ldots+x_n}n\right)\geq\frac{\ln x_1+\ln x_2+\ldots+\ln x_n}n$$then, since \(\ln\) is a concave function, for any positive \(a,b\) and \(t\in[0,1]\), \(\ln(ta+(1-t)b)\geq t\ln a+(1-t)\ln b\). Letting \(t=\frac n{n+1}\), \(a=\frac{x_1+x_2+\ldots+x_n}n\), and \(b=x_{n+1}\), a positive number, we get $$\begin{aligned}\ln\left(\frac{x_1+x_2+\ldots+x_{n+1}}{n+1}\right)&\geq\frac n{n+1}\ln\left(\frac{x_1+x_2+\ldots+x_n}n\right)+\frac1{n+1}\ln x_{n+1}\\&\geq\frac n{n+1}\cdot\left(\frac{\ln x_1+\ln x_2+\ldots+\ln x_n}n\right)+\frac{\ln x_{n+1}}{n+1}\end{aligned}$$This completes the proof.

Equality holds for the inequality in AM-GM only when all of the values \(x_1,\ldots,x_n\) are equal. Here's a basic application of the inequality.

If \(x,y\) are positive real numbers, and \(x+y=8\), what is the minimum value of \(\left(1+\frac1x\right)\left(1+\frac1y\right)\)?


Expanding out the product gives $$\frac{1+x+y+xy}{xy}=1+\frac9{xy}$$From AM-GM, $$\frac{x+y}2\geq\sqrt{xy}$$Thus, \(\frac1{xy}\geq\frac1{16}\), with equality when \(x=y\). Thus, the minimum of the product is \(1+\frac9{16}\), with the minimum occuring at \(x=y=4\).
Given a triangle \(ABC\) with \(\angle C=90^\circ\), such that \(h\) is the altitude from \(C\) to \(AB\), what is the maximum value of \(\frac h{AB}\)?.


Let \(D\) be the foot of the altitude \(h\). Then, triangles \(ADC\) and \(BDC\) are similar because they are both right triangles, and $$\angle BDC=90^\circ-\angle B=90^\circ-(90^\circ-\angle A)=\angle A$$Thus, \(\frac h{AD}=\frac{BD}h\), so \(h=\sqrt{AD\cdot BD}\). By AM-GM, \(h\leq \frac{AD+BD}2=\frac{AB}2\), with equality when \(AD=BD\), which happens when the triangle is a \(45-45-90\) triangle. Thus, the maximum value is \(\frac12\).
Top