Elliptic Geometry

by always_correct, Jul 23, 2017, 10:50 PM

always_correct wrote:

Here's a problem of mine!

Denote by $p_{XYZ}$ the perimeter of $\triangle XYZ$ .
Let $ABC$ be a triangle with point $D$ lying on $BC$ beyond $B$ such that $2 \cdot DC = p_{ABC}$ . Collinear points $E,P,Q$ are situated such that $E$ is the midpoint of $\overline{BC}$ , $ED = EP$ , and $EA = EQ$ . Points $R,S$ are the projections from $P$ to $\overline{BC}$ and $Q$ to $\overline{PR}$ , respectively. If $\angle ABC = \angle ACB < 45^\circ$ , prove that $p_{ABC} = p_{SBC}$ .

$[asy] size(10cm); pair A = (0, 0.5), B = (-1, 0), C = (1, 0), D = (-1.118, 0), E = origin, P = (0.52, 0.99), Q = (0.233, 0.443); pair R = (0.52, 0), S = (0.52, 0.443); draw(A--B--C--cycle); draw(D--E--P--cycle); draw(E--A); draw(P--R); draw(Q--S); draw(B--S--C); draw(rightanglemark(P,R,B,1.5)); draw(rightanglemark(P,S,Q,1.5)); label("$A$", A, N); label("$B$", B - (0, 0.05)); label("$C$", C - (0, 0.05)); label("$D$", D - (0, 0.05)); label("$E$", E - (0, 0.05)); label("$P$", P, N); label("$Q$", Q, - (0.05, -.05)); label("$R$", R - (0, 0.05)); label("$S$", S + (0.05, 0)); [/asy]$

It has a very cool solution! (I hope)

Hmm, it seems after a day nobody has a solution for me...

Time to post my own!

$[asy] size(10cm); pair A = (0, 0.5), B = (-1, 0), C = (1, 0), D = (-1.118, 0), E = origin, P = (0.52, 0.99), Q = (0.233, 0.443), Qp = (0.233, 0); pair R = (0.52, 0), S = (0.52, 0.443); draw(A--B--C--cycle); draw(D--E--P--cycle); draw(E--A); draw(P--R); draw(Q--S); draw(B--S--C); draw(Q--Qp); draw(rightanglemark(P,R,B,1.5)); draw(rightanglemark(P,S,Q,1.5)); draw(rightanglemark(Q,Qp,E,1.5)); draw(ellipse(E, 1.118, 0.5), blue+linewidth(1)); draw(circle(E, 0.5), red+linewidth(1)); draw(circle(E, 1.118), green+linewidth(1)); label(scale(0.7)*"$A$", A, N); label(scale(0.7)*"$B$", B - (0, 0.05)); label(scale(0.7)*"$C$", C - (0, 0.05)); label(scale(0.7)*"$D$", D - (0.05, 0.04)); label(scale(0.7)*"$E$", E - (0, 0.05)); label(scale(0.7)*"$P$", P, N); label(scale(0.7)*"$Q$", Q + (0, 0.09)); label(scale(0.7)*"$R$", R - (0, 0.05)); label(scale(0.7)*"$S$", S + (0.05, 0.02)); label(scale(0.7)*"$Q'$", Qp - (0, 0.05)); [/asy]$

Firstly note because $DB + DC = AB + AC$ , that $D, A$ lie on an ellipse with foci $B, C$ .

Let the blue ellipse with foci $B, C$ containing $A$ be $\mathcal{B}$ , the red circle with center $E$ containing $A$ be $\mathcal{R}$ , and the green circle with center $E$ containing $D$ be $\mathcal{G}$ . Finally, let $Q'$ be the projection from $Q$ to $\overline{BC}$ .

Consider the horizontal stretching $\mathcal{S}$ that takes $\mathcal{R} \to \mathcal{B}$ . It is equivalent to a homothety $\mathcal{H}$ at $E$ taking $\mathcal{R} \to \mathcal{G}$ followed by a vertical stretch $\mathcal{V}$ (as $\angle A$ is obtuse) with factor $k =\frac{R}{b}$ where $R$ is the radius of $\mathcal{G}$ and $b$ is the semi-minor axis of $\mathcal{B}$ . In other words,
$\mathcal{S} = \mathcal{V} \circ \mathcal{H}$
As $\triangle ABC$ is isosceles,
$k = \frac{R}{b} = \frac{ED}{EA}$ Now, as $P \in \mathcal{G}$ and $Q \in \mathcal{R}$ , it follows $k = \frac{EQ}{EP} = \frac{RS}{RP}$ by similarity of $\triangle EQQ'$ and $\triangle EPR$ .

Finally, note that $\mathcal{H}(Q) = P$ and as $k = \frac{RS}{RP}$ , $\mathcal{V}(Q) = S$ . Thus
$\mathcal{S}(Q) = \mathcal{V}(\mathcal{H}(Q)) = S$
As $\mathcal{S}(\mathcal{R}) = \mathcal{B}$ it follows $S \in \mathcal{B}$ , and as $B,C$ are the foci of $\mathcal{B}$ , we end up with
$AB + AC = SB +SC$ and we're done!

ellipse

geometry

homothety

transformation

The Mandelbrot Set

by always_correct, Jul 10, 2017, 9:40 PM

Hello!

As I have not posted in a long while, I'll post some eye candy. Context:

For those that don't know, the Mandelbrot set $\mathcal{M}$ is a set of complex numbers defined in the following manner. Consider the complex function $f_c(z) = z^2 + c$ . Now for a particular $c$ , consider the sequence
${z_n} = f_c^{n}(0) = \underbrace{f(f(\ldots(0)\ldots))}_{n\text{ times}}$ If $z_n$ does not diverge, then $c \in \mathcal{M}$ .

Here is an image of $\mathcal{M}$ . Every white pixel represents a point in $\mathcal{M}$ , while the colored pixels represent the number of iterations before it was certain the sequence would diverge.

How do we know at what point a sequence will diverge?

Most importantly, here are some deep zoom images I generated. (I might share the application itself when it runs faster)

I implemented a "real-time" Mandelbrot set viewer in C++ with AMP for GPU multithreading. A major optimization(among the countless micro optimizations) I have yet to implement uses the following fact: The Mandelbrot set is simply connected. In other words, If the boundary of a square(or any other shape) is a subset $\mathcal{M}$ then the interior of that square(or any other shape) is in $\mathcal{M}$ .

While the Mandelbrot set is generated by those points which do not diverge under the iteration of the complex function $f$ , what set is generated by those points who converge? Surely it must be a subset of $\mathcal{M}$ . The answer is...

Thanks for reading.

This post has been edited 3 times. Last edited by always_correct, Jul 10, 2017, 9:42 PM

programming

complex numbers

Multidimensional Triangle Inequality

by always_correct, Dec 28, 2016, 2:46 AM

Find the smallest even positive integer $n$ for which $|x-1|+|x-2|+\ldots+|x-n| \geq 2016$ for all real numbers $x$ .

Let $n = 2m$ .
Consider the metric space $(\mathbb{R}^{m}, d_{\text{TAXICAB}})$ . The triangle inequality asserts $d(y,x) + d(x,z) \geq d(y,z)$ . Let $X = (x,x,x,\ldots,x)$ , $Y = (1,2,3,\ldots,m)$ , and $Z = (m+1, m+2, m+3, \ldots, n)$ . Then:
$d(Y,X) + d(X,Z) \geq d(Y,Z)$ This expands to:
$|x-1|+|x-2|+\ldots+|x-n| \geq m^2$ We want the lowest $m$ such that $m^2 \geq 2016$ . This implies $m = 45$ . Thus $n=90$ .

This post has been edited 1 time. Last edited by always_correct, Jan 28, 2017, 6:12 PM
Reason: Thanks nahiphog!

Finite differences and Factorials

by always_correct, Dec 24, 2016, 11:05 PM

Denote by $\Delta_{k}$ the $k$ th finite difference of a sequence. Show that $\Delta_{n} x^{n} = n!$ .

Clearly $\Delta_{1} x^{1} = 1!$ . Now we show
$\Delta_{n} x^{n} = n! \implies \Delta_{n+1} x^{n+1} = (n+1)!$
Assume that $\Delta_{n} x^{n} = n!$ , which holds for all $x$ . Take the anti-derivative of both sides. We get
$\begin{align*} \int \Delta_{n} x^{n} dx = \int n! \, dx \\ \Delta_{n} \int x^{n} dx = n!\cdot x + C_{1} \\ \Delta_{n} \frac{x^{n+1}}{n+1} + C_{2} = n!\cdot x + C_{1} \end{align*}$
Setting $x=0$ we see that $C_1 = C_2$ . We remove them from the equality.

$\begin{align*} \Delta_{n} \frac{x^{n+1}}{n+1} = n!\cdot x \\ \frac{1}{n+1} \cdot \Delta_{n} x^{n+1} = n! \cdot x \\ \Delta_{n} x ^{n+1} = (n+1)!\cdot x \end{align*}$
We then proceed to take the next finite difference.

$\begin{align*} \Delta_{n+1} x^{n+1} = \Delta_{1} (n+1)! \cdot x \\ \Delta_{n+1} x^{n+1} = (n+1)! \cdot (x+1) - (n+1)! \cdot x \end{align*}$ $\boxed{\Delta_{n+1} x^{n+1} = (n+1)!}$

This post has been edited 2 times. Last edited by always_correct, Dec 24, 2016, 11:06 PM

Finite Differences

factorial

calculus

Gaussian Integers and Modular Arithmetic

by always_correct, Nov 29, 2016, 2:45 AM

Most, if not all reading should be acquainted with the set of complex numbers $\mathbb{C}$ , usually this comes from dealing with special polynomials, such as those of the form $x^{n} - 1$ . We introduce the Gaussian Integers, brought forth by Gauss in 1832. As one can guess, these integers comprise the set
$\mathbb{Z}[i] = \{a+bi \mid a,b \in \mathbb{Z} \}$ The interesting thing about Gaussian Integers is that they are similar to integers in the way that all $x \in \mathbb{Z}[i]$ can be factored into unique primes. As an example, we look at the factorization of $4+7i$ :
$4+7i = (3+2i)(2+i) = (2-3i)(-1+2i)$ Right now you have to take my word for it, but all four of these factors are prime. We see here that there are two possible factorizations, which seems to contradict the uniqueness of a prime factorization. We know* that the integers form a unique factorization domain, but look at this:
$10 = 2\cdot5 = (-2)\cdot(-5)$ Are these two different factorizations? In essence, no. These factorizations differ by the multiplication of a unit, in this case elements $u$ in $\mathbb{R}$ or $\mathbb{C}$ such that there exists another element in that set $v$ such that $uv = 1$ , the multiplicative identity.
Looking closely at the prime factorizations, we can't tell for sure right now that $(3+2i)$ and $(2+i)$ are indeed prime.

We can deal with the general case by noting a key fact, if $x \in \mathbb{Z}$ is not a Gaussian prime, then $x = (a+bi)(a-bi)$ for some $a,b \in \mathbb{Z}$ . Using this, assume $z = (a+bi)$ is a Gaussian prime, with $b\neq 0$ . Then, $z\overline{z}=a^2+b^2$ is not a Gaussian prime. Assume $a^2 + b^2$ is not prime, that is for some $c \in \mathbb{Z}$ , $c | a^2 + b^2$ . Then, $c \mid a+bi$ or $c \mid a-bi$ (why?). We know that $c \nmid a+bi$ as $z$ is a Gaussian prime, this means that $c \nmid a$ or $c \nmid b$ (why?). Thus, $c \nmid (a-bi)$ (why?) contradicting our assumption. Now, let $N(\alpha)=N(a+bi)=a^2+b^2$ , we call this the norm of $\alpha$ . We have just shown that if $\pi$ is Gaussian prime, then $N(\pi)$ is prime. We stop here to note the useful fact that the norm is multiplicative, that is:
$N(\alpha\beta)=N(\alpha)N(\beta)$ We would also like to show that if $N(\alpha)$ is prime, then $\alpha$ is a Gaussian prime. To do this we write down the prime factorization: $\alpha=\pi_{1}\pi_{2}\ldots\pi_{n}$ . The specific prime factorization does not matter. Just note that:
$N(\alpha) = N\left(\prod_{i=1}^{n}\pi_{i}\right) = \prod_{i=1}^{n}N(\pi_{i}) = \prod_{i=1}^{n}p_i$ where $p_i$ is a prime. We then switch to the contrapositive: If $\alpha$ is not a Gaussian prime, then $N(\alpha)$ is not prime. By the above, we see this is obviously true.

*If you are familiar with the proof of unique factorization in $\mathbb{Z}$ , try inducting on the norm to prove it in $\mathbb{Z}[i]$ .

We have obviously dealt with showing the numbers we assumed were Gaussian primes before were in fact Gaussian primes(still remember them?), but we left out a case in the first demonstration. We proved that the norm is prime for Gaussian primes with imaginary part not zero, i.e. $z \not\in \mathbb{Z}$ . This is obviously untrue for $z \in \mathbb{Z}$ . So what are the Gaussian primes on the real axis? One might guess all primes are Gaussian primes, but this would be close, but very far from the truth:
$5 = (2+i)(2-i) = 2^2 + 1^2$ This is such because $5$ is real, so might be able to be written as $(x+yi)(x-yi)=x^2+y^2$ . In this case we have found the sufficient $x,y$ . So, if $p$ is a real Gaussian prime, then $p \neq (x+yi)(x-yi) = x^2 + y^2$ . Straight away we can see if $p=4n+3$ , $p\neq x^2+y^2$ as the RHS is at most $2 \pmod{4}$ . Suprisingly, for any $p=4n+1$ , for some $x,y$ we have $p=x^2+y^2$ . An elegant proof credited to Dedekind is given below, although a bit out of scope for this post.

Let $p=4n+1$ be a prime number. By Euler's Criterion there exists an $a$ such that $a^{\frac{p-1}{2}} \equiv -1 \pmod{p}$ . Simplifying, we see this implies $a^{2n}-1 \equiv 0 \pmod{p}$ , or that there exists an $m$ such that $m^2+1$ is divisible by $p$ . We write this as $p \mid (m+i)(m-i)$ . Note that $p \nmid m \pm i$ (why?). Thus $m+i$ and $m-i$ contain factors such that when multiplied, $p$ divides their product. Thus, at best, $p$ divides the product of two or more factors, but can't divide just one, and hence is not prime. It follows then that $p = (x+yi)(x-yi)$ for some $x,y$ . This yields $p = x^2+y^2$ .

We understand fully when a Gaussian integer $a+bi$ is prime, this is when:

The norm $a^2+b^2$ is prime, and $b \neq 0$ .
$b = 0$ and $a\equiv 3 \pmod{4}$ and $a$ is prime.

Now we can have more of a visual understanding of these Gaussian primes, as I have programmed a complex plane viewer, which produced these nice images:

With primes out of the way, we can talk about arithmetic in the Gaussian integers. In the integers, we can use induction to prove that for any integers $a,b$ , $a$ can be written as $a = bq + r$ , where $0 \leq r < b$ . This can be shown to hold in a similar way for Gaussian integers, and the takeaway here is that writing a number in this form shows the least remainder and quotient obtained from a division algorithm. Here is the statement for Gaussian integers:

For any two Gaussian integers $\alpha$ and $\beta$ , $\alpha$ can be written as $\alpha = \beta \omega + r$ , where $0\leq |r| \leq \frac{\sqrt{2}}{2}\sqrt{N(\beta)}$ . Obviously this isn't satisfactory to simply hear, one must see. Before we visualize, realize that is we are not providing a rigorous proof, we simply mean to show how one can pick a $\beta$ and thus why $0\leq |r| \leq \frac{\sqrt{2}}{2}\sqrt{N(\beta)}$ . We start by expanding $\omega = x+yi$ . We then look solely at the $\beta \omega$ term.
$\beta \omega = \beta x + \beta yi = \beta x + \beta ' y$ where $\beta ' = i\beta$ . Now we can visualize. Remember that $x$ and $y$ may be any integer. We view $\beta$ and $\beta '$ as vectors, one rotated 90 degrees from the other(why?).

Now $x,y$ can be any integer, so we consider all linear combinations of these vectors, that is $x$ and $y$ scale the two, then we add the vectors. All the possible values of $\beta \omega = \beta x + \beta yi = \beta x + \beta ' y$ is shown by the intersection points in the image. Note that squares form as they are 90 degrees apart(what else makes them squares?).

We know $\alpha$ can be any point on this grid, so we now know what to do about the bounds on $|r|$ , seeing $r$ is the distance from the nearest intersection point. We know the minimum that $r$ can be $0$ , and the maximum distance is obtained when $\alpha$ is in the center of a square, when $|r| = \frac{\sqrt{2}}{2}\sqrt{N(\beta)}$ . This is show in the below image, the middle dot being the place $\alpha$ has to be to maximize $|r|$ , with the circles represent the area swept out by all points $|r|$ away from an intersection point.

Finally, we can talk about modular arithmetic. We define modular arithmetic in the same way we do in $\mathbb{Z}$ , that is $\alpha \equiv \beta \pmod{\gamma}$ iff $\gamma \mid (\alpha - \beta)$ . Many useful things can be done with this modular arithmetic, and it is very close to modular arithmetic in $\mathbb{Z}$ . Geometrically, we see the number of residues modulo $\pi$ is the number all the Gaussian integers in or on the sides, not corners, of a square of the many squares formed by considering linear combinations of $\pi$ and $i\pi$ , as we saw from looking at remainders from division algorithms. Note that in the integers, the number of non-zero residues modulo $p$ is $p-1$ . Let $n(\pi)$ represent the amount of residues modulo $\pi$ . The analog of Fermat's Little Theorem turns out to be true.

Let $\pi$ be a Gaussian prime. If $\alpha \not\equiv 0 \pmod{\pi}$ , then
$\alpha^{n(\pi)-1} \equiv 1 \pmod{\pi}$
We need a small affirmation, that is the existence of an inverse. We need to prove the there exist an $x$ such that $\alpha x \equiv 1 \pmod{\beta}$ if $\alpha$ and $\beta$ share no factors(why?). To prove this we write it as $\alpha x = \beta y + 1 \iff \alpha x - \beta y = 1$ . We note there exists $x,y$ that fulfill this as Bezout's lemma applies, because it is essentially the division algorithm run in reverse. (what division algorithm? try finding one for Gaussian integers!).

We prove this in the way we normally prove the theorem. Let $\beta_{1},\beta_{2},\ldots,\beta_{n(\pi)}$ be the distinct residues modulo $\pi$ , and set $\beta_{n(\pi)}=0$ . Consider the sequence $\alpha\beta_{1},\alpha\beta_{2},\ldots,\alpha\beta_{n(\pi)-1}$ .

Assume, for the sake of contradiction, for some $j$ and $k$ , that $\alpha\beta_{j} \equiv_{\pi} \alpha\beta_{k}$ . We multiply both sides by $\alpha^{-1}$ , and we obtain that $\beta_{j} \equiv_{\pi} \beta_{k}$ . This is absurd, as we have each residue being distinct.

Thus, all residues of the sequence $\alpha\beta_{1},\alpha\beta_{2},\ldots,\alpha\beta_{n(\pi)-1}$ are distinct, and thus, $\beta_{1}\beta_{2}\ldots\beta_{n(\pi)-1} \equiv\alpha\beta_{1}\alpha\beta_{2}\ldots\alpha\beta_{n(\pi)-1}\pmod{\pi}$ . Multiplying both sides by $\prod_{k=1}^{n(\pi)-1}\beta_{k}^{-1}$ , which exists since $\pi$ is a Gaussian prime and hence all non-zero residues are co-prime to $\pi$ , we arrive at $\alpha^{n(\pi)-1} \equiv 1 \pmod{\pi}$ . Note that the proof of the analog of Euler's Totient Theorem is exactly this.

We have just one more thing to deal with, what is $n(\alpha)$ ? There are a few things that need to be proved, which is left to you to prove.

1. $n(\alpha) = n(\overline{\alpha})$ (think geometrically)
2. $z \in \mathbb{Z} \implies n(z) = z^2$ (combinatorics)
3. $n(\alpha\beta)=n(\alpha)n(\beta)$ (expand and substitute as much as possible)

Using these facts, we have that:
$n(\alpha)^2=n(\alpha)n(\overline{\alpha})=n(\alpha\overline{\alpha}) = n(|\alpha|^2) = N(\alpha)^2$ Thus, $n(\alpha) = N(\alpha)$ . That is quite surprising, and I end this post with the theorem once more, for $\alpha$ co-prime to a Gaussian $\pi$ , we have that:
$\boxed{\alpha^{N(\pi)-1}\equiv 1 \pmod{\pi}}$ Thank you for reading.

This post has been edited 1 time. Last edited by always_correct, Nov 29, 2016, 2:53 AM

Abel Summation and an Analog for Calculus

by always_correct, Nov 22, 2016, 2:02 AM

For those acquainted with integral calculus, you should be familiar with the identity commonly known as Integration by Parts, which states for any two differentiable functions $f$ and $g$ :
$\int_{0}^{N}f(x)g'(x)dx=f(x)g(x)\rvert_{0}^{N}-\int_{0}^{N}f'(x)g(x)dx$ Now, when we think of derivatives, we think of the difference quotient of a function. This looks like:
$\frac{f(x+h)-f(x)}{h}$ We take the limit of this as $h \to 0$ to get a derivative, now, what if we didn't take a limit? What if we said $h=1$ was good enough? Then we get what is called a finite difference of $f$ , which in this case is $f(x+1) - f(x)$ . We denote this particular finite difference as $\Delta [f](x)$ . Why would we have to use a finite difference? Think sequences. Let $(a_n) = f(n)$ for all (or some) $n\in \mathbb{Z}$ with $n \geq 0$ . Now taking a derivative of a sequence sounds silly, but we can take a finite difference! For the rest of the post I will be denoting the sequence of finite differences as $(\Delta a_n) = \Delta[f](n)$ . This will make things a bit more readable.

Similarly, when we think of definite integration, we think of areas under curves.

Note that the sum can be an analog to an integral. As we know from the Fundamental Theorem of Calculus:
$\int_{0}^{N}f'(t)dt = f(N) - f(0)$ Using our analogs we discussed, we realize the same is true for sequences with finite differences:
$\sum_{n=0}^{N-1}\Delta a_n = \sum_{n=0}^{N-1}(a_{n+1}-a_n) = a_N - a_0$ For the first equality, note that the sum telescopes. Interesting. One more thing, we need a compact way to represent summation that is analogous to taking an integral. For a sequence $(a_n)$ we denote the sequence the represents the integral as $(A_n) = \sum_{k=0}^{n}a_n$ . We use the Fundamental Theorem once more and note that letting $F(N) = \int_{0}^{N} f'(t) dt$ , that $F'(N) = f(N)$ . Looking at the analog, we see that it is also in a sense true, that
$\Delta A_N = A_{N+1} - A_{N} = a_{N+1}$

Keeping integration by parts in mind, I introduce the Abel summation. I first represent it in the commonly use notation, then my own. For any two sequences $a_1,a_2,\ldots,a_N$ and $b_1,b_2,\ldots,b_N$ , with $S_k = \sum_{n=0}^{k}a_k$
$\sum_{n=0}^{N}a_n b_n = S_N b_N + \sum_{n=0}^{N-1}S_n(b_n - b_{n+1})$ Here it is again using my notation, note I have swapped to have that $(b_k - b_{k+1}) = -\Delta b_k$ .
$\sum_{n=0}^{N}a_n b_n = A_N b_N - \sum_{n=0}^{N-1}A_n \Delta b_n$ Compare this to the integration by parts formula, it's very similar! How can we prove this? Let's look at the simple proof for integration by parts.
$\begin{align*} \frac{d}{dx}[f(x)g(x)] &= f'(x)g(x) + f(x)g'(x) \\ f(x)g(x) &= \int f'(x)g(x) dx + \int f(x)g'(x) dx \\ \int f(x)g'(x) dx &= f(x)g(x) - \int f'(x)g(x) dx \\ \end{align*}$ From the Fundamental Theorem it follows that:
$\int_{0}^{N}g'(x)f(x)dx=g(x)f(x)\rvert_{0}^{N}-\int_{0}^{N}g(x)f'(x)dx$ Note that I swapped the location of $g(x)$ and $f(x)$ . We should look to mimick this proof to prove that Abel summation works, while there are somewhat simpler methods, I feel this shows how it really is an analog to integration by parts. We see that $g'(x)$ will represent $(a_n)$ and $f(x)$ will represent $(b_n)$ . We start our proof just like the previous one, by finding the derivative of the product of $g(x)$ and $f(x)$ . Note that as $g'(x)$ will represent $(a_n)$ , $(A_n)$ will represent $g(x)$ .
$\Delta (A_n b_n) = A_{n+1} b_{n+1} - A_n b_n$ How can we rewrite this? Looking at that fact that $\frac{d}{dx}[f(x)g(x)] = f'(x)g(x) + f(x)g'(x)$ , we might look at the expansion of $A_n \Delta b_n + b_n \Delta A_n$ (expand this). We see that this is not enough. One might also look at the expansion of $\Delta A_n \Delta b_n$ (this also). This is also not enough. However, the keen will realize that adding both works:
$\Delta (A_n b_n) = \Delta A_n \Delta b_n + A_n \Delta b_n + b_n \Delta A_n$ Using the analogs we previously noted, we simplify this to
$\begin{align*} \Delta (A_n b_n) &= a_{n+1} \Delta b_n + A_n \Delta b_n + b_n a_{n+1} \\ &= a_{n+1}(b_{n+1} - b_n) + A_n \Delta b_n + b_n a_{n+1} \\ &= a_{n+1}b_{n+1} + A_n \Delta b_n \end{align*}$ We are closer to finishing. In the original proof, we next then took the indefinite integral of both sides, and said the definite integral was also valid. So, let us do the analog, we will sum up both sides from $n=0$ to $n=N-1$ .
$\begin{align*} \sum_{n=0}^{N-1}\Delta (A_n b_n) &= \sum_{n=0}^{N-1}a_{n+1}b_{n+1} + \sum_{n=0}^{N-1}A_n \Delta b_n \\ A_N b_N - A_0 b_0 &= \sum_{n=1}^{N}a_{n}b_{n} + \sum_{n=0}^{N-1}A_n \Delta b_n \end{align*}$ Note that $A_0 = \sum_{n=0}^{0}a_n = a_0$ , we then add $A_0 b_0 = a_0 b_0$ to both sides effectively shifting the $n=1$ in the first sigma to $n=0$ .
$A_N b_N = \sum_{n=0}^{N}a_{n}b_{n} + \sum_{n=0}^{N-1}A_n \Delta b_n$ Rearranging, we arrive at the desired equality.
$\boxed{\sum_{n=0}^{N}a_n b_n = A_N b_N - \sum_{n=0}^{N-1}A_n \Delta b_n}$ Expanding to the usual notation, we get (we swapped $b_{n+1}$ and $b_n$ and made it negative):
$\boxed{\sum_{n=0}^{N}a_n b_n = S_N b_N + \sum_{n=0}^{N-1}S_n(b_n - b_{n+1})}$

Abel Summation is very powerful, but it is important to understand its connection to calculus. The close relation between derivatives, integrals, finite differences, and sums is very interesting, what can you prove with it?

Thank you for reading.

This post has been edited 3 times. Last edited by always_correct, Nov 22, 2016, 2:19 AM

abel

Summation

calculus

AM-GM and Cauchy-Schwarz (and Calculus)

by always_correct, Nov 21, 2016, 2:29 AM

One of the more simpler inequalities one uses regularly in an olympiad setting is the AM-GM and Cauchy-Schwarz inequalities. These inequalities provide clever ways to solve inequalities where calculus would be used by those inexperienced.

AM-GM

The AM-GM inequality tells us that the arithmetic mean is greater than the geometric mean. The statement for two variables is: For any $x,y \geq 0$
$\frac{x+y}{2} \geq \sqrt{xy}$ With equality at $x=y$ . The proof of this is simple, and thus, the two variable case isn't of too much use. However when we get to the $n$ -variable case, things get a little bit hairy. Here it is: For any $x_1,x_2,\ldots x_n \geq 0$
$\frac{x_1 + x_2 + \ldots + x_n}{n} \geq \sqrt[n]{x_1 x_2 \ldots x_n}$ We could prove this using Cauchy Induction, but there is a much more elegant way. Jensen's Inequality provides a beautiful proof.

Let $x_1,x_2,\ldots x_n \geq 0$ . Consider the exponential function $\exp(x)=e^{x}$ . This is convex, we can see this from either the graph or the second equivalent definition of convexity — the second derivative is always positive. By Jensen's Inequality:
$\exp\left(\frac{x_1 + x_2 + \ldots + x_n}{n}\right) \leq \frac{\exp(x_1)+\exp(x_2)+\ldots+\exp(x_n)}{n}$ Using the properties of $\exp(x)$ which are $\exp(a+b)=\exp(a)\exp(b)$ and $\exp(ab)=\exp(a)^b$ we obtain
$\sqrt[n]{\exp(x_1)\exp(x_2)\ldots\exp(x_n)} \leq \frac{\exp(x_1)+\exp(x_2)+\ldots+\exp(x_n)}{n}$ Now let $\exp(x_k)=u_k$ , note that $u_k > 0$ . Thus,
$\sqrt[n]{u_1 u_2 \ldots u_n} \leq \frac{u_1+u_2+\ldots+u_n}{n}$ This is AM-GM for $n$ variables. However, we did not account when $u_k = 0$ . When this happens the LHS is $0$ and so the inequality is obviously true.

Cauchy-Schwarz

The statement of this inequality is best understood in the form of vectors. As a reminder on vectors, a vector $X$ in the set of vectors $\mathbb{R}^{n}$ is written as $X = (x_1, x_2, \ldots, x_n)$ . We let the sum of two vectors $X$ and $Y$ be the vector having elements that are the sum of corresponding elements, that is:
$X+Y = (x_1 + y_1, x_2 + y_2, \ldots, x_n +y_n)$ We let the dot product between two vectors $X$ and $Y$ be the sum of the product of the corresponding elements, that is:
$X\cdot Y = x_1 y_1 + x_2 y_2 + \ldots + x_n y_n$ Try showing that the dot product is distributive, that is $A\cdot (B+C)=A\cdot B+A\cdot C$ . This is important.
Additionally, we generalize the Pythagorean Theorem to get the length, or magnitude of a vector $X$ is given as:
$\|X\| = \sqrt{x_1^2+x_2^2+\ldots x_n^2}$ Note that $X\cdot X= \|X\| ^{2}$ . Play around with concrete examples of this if you are new to this.

The Cauchy-Schwarz Inequality is, for any two vectors $X,Y \in \mathbb{R}^{n}$
$X\cdot Y \leq \|X\| \, \|Y\|$ That is, the dot product of two vectors is less than or equal to the product of the magnitudes.
When we have two vectors in $n$ -dimensional space, considering them as points in space, we note there exists a certain plane that contains both of these points. We look at the cross-section of the $n$ -dimensional space by this plane. Here we have two vectors, $X$ and $Y$ , and their difference $X-Y$ or $Y-X$ . Note that which difference we choose does not matter, as the magnitudes are the same(why?). Notice I have included the angle between the vectors, $\theta$ . Right, now you could stop reading and derive the Cauchy-Schwarz Inequality. Hint. I will go on for completion, however.

.
Using the Law of Cosines, we obtain that:
$\|X\|^{2} + \|Y\|^{2} - 2\|X\|\,\|Y\|\cos\theta = \|X-Y\|^{2}$ Using the basic facts of vectors we discussed earlier we simplify both sides to the equivalent identity:
$X\cdot X + Y\cdot Y - 2\|X\|\,\|Y\|\cos\theta = (X-Y)\cdot(X-Y)$ We use the distributive property to expand the RHS:
$X\cdot X + Y\cdot Y - 2\|X\|\,\|Y\|\cos\theta = X\cdot X - 2(X\cdot Y) + Y\cdot Y$ Finally we obtain that:
$\boxed{X\cdot Y = \|X\|\,\|Y\|\cos\theta}$ This is very surprising, at least to me. Note when $\theta = 0$ , the vectors lie on top of each other, that is one is a potentially scaled version of another, $X = kY$ . Thus, when $X = kY$ , $X\cdot Y = \|X\|\,\|Y\|$ . In all other cases, note that $\cos\theta < 1$ . Together we have:
$X\cdot Y = \|X\|\,\|Y\|\cos\theta \leq \|X\|\,\|Y\|$ with equality when $X$ and $Y$ are scalar multiples of each other. This is the Cauchy-Schwarz inequality!
Moving out of a vectors context, we can represent a vector as a sequence of numbers. Then, the Cauchy-Schwarz inequality is that for any two sequences $x_1,x_2,\ldots,x_n$ and $y_1,y_2,\ldots,y_n$ we have:
$x_1y_1 + x_2y_2 + \ldots + x_ny_n \leq \sqrt{x_1^{2} + x_2^{2} + \ldots + x_n^{2}}\sqrt{y_1^{2} + y_2^{2} + \ldots + y_n^{2}}$ Or more usually represented:
$(x_1y_1 + x_2y_2 + \ldots + x_ny_n)^{2} \leq (x_1^{2} + x_2^{2} + \ldots + x_n^{2})(y_1^{2} + y_2^{2} + \ldots + y_n^{2})$ And compactly:
$\left(\sum_{i=1}^{n}x_i y_i\right)^{2} \leq \left(\sum_{i=1}^{n}x_i^{2}\right)\left(\sum_{i=1}^{n}y_i^{2}\right)$ In this case, the equality happens when there exists a $k$ such that $x_1,x_2,\ldots,x_n = ky_1,ky_2,\ldots,ky_n$ .

And for the reader who knows calculus, I challenge them to solve this problem in two ways: using calculus, and one of the two inequalities aforementioned.

A farmer wants to construct a rectangular pen out of fencing for both his chickens and horses. He wants to leave one side open (not built) to let the horses roam. Additionally, he wants to construct a high fence along the diagonal to prevent the chickens and horses from interacting. He has a limited supply of $50$ yards of high fence to use for the diagonal. What is the maximum perimeter of the pen?

Thank you for reading.

inequalities

calculus

Convex Functions and Jensen's Inequality

by always_correct, Nov 20, 2016, 3:21 AM

What does it mean for a function to be convex? Concave? Intuitively we see that all convex functions on an interval $I$ look like a smooth valley, and all concave functions look like smooth hills. We want a rigorous definition of convex and concave functions, we first tackle this by realizing a concave function is just the negative of some convex function.

We can notice by drawing a convex function $f(x)$ on an interval $I$ , that for any line $L(x)$ through any two points on the function, $L(x)$ is above the graph, more precisely, $L(x) \geq f(x)$ for $x \in I$ .

For a non-convex function, we see that this line may be below the graph.

Let's define a convex function $f(x)$ this way. First, we need a concise way to say all points on this line segment are above or on the graph. Let $(a,f(a))$ and $(b,f(b))$ be the endpoints of a line in the interval where the function is convex, let this interval be $I$ . The midpoint of these two points is the average of the $x$ and $y$ coordinates. This is in the line segment, as the average of two numbers is between those numbers. Generally, we can say any for any $\mu \in [0,1]$ ,(Letting $\mu = \frac{1}{2}$ gives us the midpoint case.)
$\mu a + [1-\mu]b \in [a,b]$ To prove this we can write $\mu a + [1-\mu]b = b+\mu(a-b)$ and note this is the equation of a line $L(\mu)$ , and use the Intermediate Value Theorem. We can equally say that for any $\mu \in [0,1]$ ,
$\mu f(a) + [1-\mu]f(b) \in [f(a),f(b)]$ Note that if $L(x)$ is the equation of the line segment from $(a,f(a))$ to $(b,f(b))$ , by linearity*:
$L(\mu a + [1-\mu]b)=\mu L(a) + [1-\mu]L(b) =\mu f(a) + [1-\mu]f(b)$ The last equality comes from the fact, looking at the picture, that the line is equal to the function at $x=a$ and $x=b$ , in other words, $L(a)=f(a)$ and $L(b)=f(b)$ . Thus we come to the final conclusion that all points on the line segment connecting any two points of $f(x)$ can be written as:
$(h,k)=(\mu a + [1-\mu]b, \mu f(a) + [1-\mu]f(b))$ By our definition, this point has to be above or on $f(x)$ for $f(x)$ to be convex, where $x=h$ . Thus, if a function is convex in the interval $I$ , for all $a,b \in I$ and $\mu \in [0,1]$ ,
$\mu f(a) + [1-\mu]f(b) \geq f(\mu a + [1-\mu]b)$ *Actually, the function $L(x)$ is affine not linear, meaning $L(x)=ax+b$ and NOT $L(x)=ax$ . However we can still note that if $m + n = 1$ , then:
$\begin{align*} L(mx+ny) &= a(mx+ny)+b \\ &= amx+any+b \\ &= amx + mb + any + nb \\ &= m(ax+b) + n(ay+b) \\ &= mL(x)+nL(y) \end{align*}$ So "linearity" sometimes applies if the coefficients $m,n$ add up to one... make sure you understand this!

Great! We just rigorously defined convex functions, now I need to make sure you aren't lying when you say you understand.

Try proving the inequality in the definition of convexity fails for $\mu \in \mathbb{R}\setminus [0,1]$ .

Moving onward, we can now discuss Jensen's Inequality. Here is the statement of Jensen's Inequality.

Let $f(x)$ be a real convex function defined in the interval $I$ , and let $x_1,x_2,\ldots,x_n \in I$ and $\mu_1,\mu_2,\ldots,\mu_n$ be positive real numbers such that $\mu_1 + \mu_2 + \ldots + \mu_n = 1$ . Then
$\mu_1 f(x_1)+\mu_2 f(x_2)+\ldots+\mu_n f(x_n) \geq f(\mu_1 x_1 + \mu_2 x_2 + \ldots + \mu_n x_n)$
See if you can prove this. Here I will discuss an outline to think about.

Now that we understand Jensen's inequality(hopefully), we can prove powerful inequalities, and find maximums where no other methods provide help. For example look at this problem:

In $\triangle ABC$ , find the maximum of $\sin A + \sin B + \sin C$ .

Solution

Thank you for reading, and comment if you have any questions or feedback.

This post has been edited 7 times. Last edited by always_correct, Nov 20, 2016, 10:35 PM

Submit

there are over 6000! anyway, I'm resting with the whole Euler line problem right now
by always_correct, Aug 6, 2017, 8:16 PM
Have you seen something about Kimberling centers (triangle centers) and center lines?
by alevini98, Aug 5, 2017, 11:19 PM
no its not dead
by always_correct, Jul 12, 2017, 1:19 AM
Wow this is great, is this dead?
by Ankoganit, Jul 3, 2017, 8:41 AM
oh its a math blog.....
by Swimmer2222, Apr 13, 2017, 12:58 PM
Why is everyone shouting
Oh wait...
by ArsenalFC, Mar 26, 2017, 8:45 PM
Shout! ^^
by DigitalDagger, Mar 4, 2017, 3:49 AM
14th shout!
by arkobanerjee, Feb 8, 2017, 2:48 AM
14th shout! be more active
by Mathisfun04, Jan 25, 2017, 9:13 PM
13th shout
by Ryon123, Jan 3, 2017, 3:47 PM
Dang, so OP. Keep it up!
by monkey8, Dec 28, 2016, 6:23 AM
How much time do you spend writing these posts???
by Designerd, Dec 5, 2016, 5:02 AM
good blog!
by AlgebraFC, Dec 5, 2016, 2:09 AM
Nice finally material for calculus people to read thanks
by Math1331Math, Nov 27, 2016, 2:50 AM
Whoa how much time do you spend typing these posts?

They're nice posts!
by MathLearner01, Nov 24, 2016, 3:30 AM
i am remove it please
by always_correct, Nov 22, 2016, 2:18 AM
5th shout!
by algebra_star1234, Nov 20, 2016, 2:41 PM
fourth shout >
by budu, Nov 20, 2016, 4:59 AM
3rd shout!
by monkey8, Nov 20, 2016, 3:24 AM
2nd shout!
by RYang, Nov 20, 2016, 3:01 AM
first shout >
by doitsudoitsu, Oct 9, 2016, 7:54 PM

21 shouts

Mathematical

by always_correct, Jul 23, 2017, 10:50 PM

by always_correct, Jul 10, 2017, 9:40 PM

by always_correct, Dec 28, 2016, 2:46 AM

by always_correct, Dec 24, 2016, 11:05 PM

by always_correct, Nov 29, 2016, 2:45 AM

by always_correct, Nov 22, 2016, 2:02 AM

by always_correct, Nov 21, 2016, 2:29 AM

by always_correct, Nov 20, 2016, 3:21 AM