Showing posts with label analysis. Show all posts
Showing posts with label analysis. Show all posts

Tuesday, 6 September 2016

Convolution as Weighted Average

We know that the average of $f$ over $[x-T,x+T]$ for any fixed $x$ is given by $$f_{\text{avg}}(x)=\frac{1}{2T}\int_{x-T}^{x+T} f(t)\,\mathrm{d}t.$$ Define $\phi=\frac{\Pi_T}{2T}$, where \begin{align}\Pi_T(t)=\begin{cases}1,&\quad -T\leq t\leq T\\
0,&\quad |t|>T.\end{cases}\end{align} We then have $$\int_{-\infty}^\infty \phi(t)\,\mathrm{d}t=\frac{1}{2T}\int_{-T}^T \Pi_T(t)\,\mathrm{d}t=1.$$ For any fixed $x$, \begin{align}\phi(x-t)=\begin{cases}\frac{1}{2T},&\quad x-T\leq t\leq x+T\\
0,&\quad \text{else}.\end{cases}\end{align} Thus, for any given function $f$ and any fixed value of $x$, \begin{align}f(t)\phi(x-t)=\begin{cases}\frac{1}{2T}f(t),&\quad x-T\leq t\leq x+T\\
0,&\quad \text{else}.\end{cases}\end{align} We conclude that $$f_{\text{avg}}(x)=\int_{-\infty}^\infty f(t)\phi(x-t)\,\mathrm{d}t.$$ More generally, when we replace $\phi$ with an arbitrary function, we have the definition of a convolution: the convolution of two functions $f$ and $g$ is given by $$f*g(x)=\int_{-\infty}^\infty f(t)g(x-t)\,\mathrm{d}t.$$ Reference: The Mathematics of Imaging by Timothy G. Freeman

Sunday, 15 May 2016

Manipulations of Sums

Let $a_1,a_2,\cdots$ be any sequence of numbers. We are often interested in sums such as $a_1+\cdots+a_n$. This sum can be written more compactly using either of the following equivalent notations: $$\sum_{i=1}^n a_i\quad \text{or}\quad \sum_{1\leq i\leq n} a_i.$$ In general, if $R(i)$ is any relation involving $i$, the symbol $$\sum_{R(i)} a_i$$ means the sum of all $a_i$, where $i$ is an integer satisfying the condition $R(i)$. The letter $i$ is a dummy variable or index variable that may be renamed without changing the result.

We now discuss four important algebraic operations on sums.

1) The distributive law, for products of sums $$\bigg(\sum_{R(i)} a_i\bigg)\bigg(\sum_{S(j)} b_j\bigg)=\sum_{R(i)}\bigg(\sum_{S(j)} a_ib_j\bigg)$$ Consider for example $$\begin{align}\bigg(\sum_{i=1}^2 a_i\bigg)\bigg(\sum_{j=1}^3 b_j\bigg)&=(a_1+a_2)(b_1+b_2+b_3)\\
&=(a_1b_1+a_1b_2+a_1b_3)+(a_2b_1+a_2b_2+a_2b_3)\\
&=\sum_{i=1}^2\bigg(\sum_{j=1}^3 a_ib_j\bigg).\end{align}$$ 2) Interchanging order of summation $$\sum_{R(i)}\sum_{S(j)} a_{ij}=\sum_{S(j)}\sum_{R(i)} a_{ij}$$ For example, $$\sum_{R(i)}\sum_{j=2}^2 a_{ij}=\sum_{R(i)}(a_{i1}+a_{i2})\\ \sum_{j=1}^2 \sum_{R(i)} a_{ij}=\sum_{R(i)} a_{i1}+\sum_{R(i)} a_{i2}.$$ This means that $$\sum_{R(i)}(b_i+c_i)=\sum_{R(i)}b_i+\sum_{R(i)}c_i,$$ where $b_i=a_{i1}$ and $c_i=a_{i2}$. This operation is very useful because we often know a simple form for $\sum_{R(i)} a_{ij}$ but not for $\sum_{S(j)} a_{ij}$. More generally, we have $$\sum_{R(i)}\sum_{S(i,j)}a_{ij}=\sum_{S'(j)}\sum_{R'(i,j)}a_{ij},$$ where $S'(j)$ is the relation 'there is an integer $i$ s.t. both $R(i)$ and $S(i,j)$ are true'; and $R'(i,j)$ is the relation 'both $R(i)$ and $S(i,j)$ are true'. For example, if the summation is $\sum_{i=1}^n\sum_{j=1}^i a_{ij}$, then $S'(j)$ is the relation 'there is an integer $i$ s.t. $1\leq i\leq n$ and $1\leq j\leq i$, namely $1\leq j\leq n$; and $R'(i,j)$ is the relation '$1\leq i\leq n$ and $1\leq j\leq i$', namely $j\leq i\leq n$. Thus, $$\sum_{i=1}^n\sum_{j=1}^i a_{ij}=\sum_{j=1}^n\sum_{i=j}^n a_{ij}.$$ 3) Change of variable
$$\sum_{R(i)} a_i=\sum_{R(j)} a_j=\sum_{R(p(j))} a_{p(j)}$$ The first equality holds because we are simply changing the dummy variable. In the second case, $p(j)$ is a function of $j$ that represents a permutation of the range. For each integer $i$ satisfying the relation $R(i)$, there is a unique integer $j$ satisfying the relation $p(j)=i$. This condition is always satisfied in cases $p(j)=c+j$ and $p(j)=c-j$, where $c$ is an integer not depending on $j$. For instance, $$\sum_{1\leq i\leq n} a_i=\sum_{1\leq i-1\leq n} a_{i-1}=\sum_{2\leq i\leq n+1} a_{i-1}.$$ Note that for infinite sums, replacing $j$ by $p(j)$ is valid iff $\sum_{R(j)}|a_j|$ exists.

4) Manipulating the domain
If $R(i)$ and $S(i)$ are arbitrary relations, we have $$\sum_{R(i)}a_i+\sum_{S(i)}a_i=\sum_{R(i)\;\text{or}\;S(i)}a_i+\sum_{R(i)\;\text{and}\;S(i)}a_i.$$ For example, $$\sum_{1\leq i\leq m}a_i+\sum_{m\leq i\leq n}a_i=\bigg(\sum_{1\leq i\leq n}a_i\bigg)+a_m,$$ assuming that $1\leq m\leq n$.

Examples from high school:
[The sum of a geometric progression] Assume that $r\neq 1,n\geq 0$. A conventional way of deriving the formula is to consider $S=a+ar+\cdots+ar^n$ and $S-rS$. $$a+ar+\cdots+ar^n\\ \underline{-)\; ar+ar^2+\cdots+ar^{n+1}}\\ a-ar^{n+1}=S(1-r)\\ \Rightarrow S=a\dfrac{1-r^{n+1}}{1-r}$$ This can be easily derived too by manipulating sums: $$\begin{align}a+ar+\cdots+ar^n&=a+\sum_{i=1}^n ar^i\\
&=a+r\sum_{i=1}^n ar^{i-1}\\
&=a+r\sum_{i=0}^{n-1} ar^i\\
&=a+r\sum_{i=0}^n ar^i-ar^{n+1}\\
&=a\dfrac{1-r^{n+1}}{1-r}\end{align}$$
[The sum of a arithmetic progression] Assume $n\geq 0$. Then $$\begin{align}a+(a+d)+\cdots+(a+nd)&=\sum_{i=0}^n (a+di)\\
&=\sum_{n-i=0}^n (a+d(n-i))\\
&=\sum_{i=0}^n (a+dn-di)\\
&=\sum_{i=0}^n (2a+dn)-\sum_{i=0}^n (a+di)\\
&=(n+1)(2a+dn)-\sum_{i=0}^n (a+di)\\
&=a(n+1)+\dfrac{1}{2}dn(n+1)\\
&=\dfrac{1}{2}(n+1)(2a+dn)\end{align}$$ Another example:
Let $$\begin{align}S&=\sum_{i=0}^n\sum_{j=0}^i a_ia_j\\
&=\sum_{j=0}^n\sum_{i=j}^n a_ia_j\\
&=\sum_{i=0}^n\sum_{j=i}^n a_ia_j
\end{align}$$ Then $$\begin{align}2S&=\sum_{i=0}^n\bigg(\sum_{j=0}^i a_ia_j+\sum_{j=i}^n a_ia_j\bigg)\\
&=\sum_{i=0}^n\bigg((\sum_{j=0}^n a_ia_j)+a_ia_i\bigg)\\
&=\bigg(\sum_{i=0}^n a_i\bigg)^2+\bigg(\sum_{i=0}^n a_i^2\bigg)\end{align}$$ We have derived the identity $$\sum_{i=0}^n\sum_{j=0}^i a_ia_j=\dfrac{1}{2}\bigg(\bigg(\sum_{i=0}^n a_i\bigg)^2+\bigg(\sum_{i=0}^n a_i^2\bigg)\bigg).$$

Examples in analysis
In Riemann integration, we have the following result: Suppose $f\in \mathscr{R}[a,b]$ and $g\in \mathscr{C}([m,M])$, where $M=\sup\{f(x)\mid a\leq x\leq b\}$ and $m=\inf\{f(x)\mid a\leq x\leq b\}$. Then $g\circ f\in \mathscr{R}[a,b]$.

Idea: Consider continuous points and discontinuous points separately.

Proof: Let $\varepsilon>0$. Since $g$ is uniformly continuous on $[m,M]$, there exists $\delta>0$ s.t. $|g(x)-g(y)|<\varepsilon$ as $x,y\in [m,M]$ and $|x-y|<\delta$. Also, since $f\in \mathscr{R}[a,b]$, there exists a partition $P=\{x_0,x_1,\cdots,x_n\}$ of $[a,b]$ s.t. $U(f,P)-L(f,P)<\varepsilon \delta$. Consider $A=\{i\mid osc(f)< \delta\}$ (index w.r.t. continuous points) and $A^c=\{i\mid osc(f)\geq \delta\}$ (index w.r.t. discontinuous points). $i\in A$ does not cause much trouble. To handle $i\in A^c$, consider $$\begin{align}\sum_{i\in A^c}(x_i-x_{i-1})&=\dfrac{1}{\delta}\sum_{i\in A^c}\delta (x_i-x_{i-1})\\
&\leq \dfrac{1}{\delta}\sum_{i=1}^n(M_i(f)-m_i(f))(x_i-x_{i-1})\\
&=\dfrac{1}{\delta}(U(f,P)-L(f,P))\\
&<\varepsilon. \end{align}$$Therefore, $$\begin{align}U(g\circ f,P)-L(g\circ f,P)&=\sum_{i=1}^n\bigg(\sup_{[x_{i-1},x_i]}(g\circ f)-\inf_{[x_{i-1},x_i]}(g\circ f)\bigg)(x_i-x_{i-1})\\
&=\sum_{i\in A}\bigg(\sup_{[x_{i-1},x_i]}(g\circ f)-\inf_{[x_{i-1},x_i]}(g\circ f)\bigg)(x_i-x_{i-1})\\&+\sum_{i\in A^c}\bigg(\sup_{[x_{i-1},x_i]}(g\circ f)-\inf_{[x_{i-1},x_i]}(g\circ f)\bigg)(x_i-x_{i-1})\\
&\leq \varepsilon \sum_{i\in A}(x_i-x_{i-1})+C\sum_{i\in A^c}(x_i-x_{i-1})\\
&\leq \varepsilon(b-a)+C\varepsilon\\
&=(b-a+C)\varepsilon,\end{align}$$ where $C=\max\{g(u)\mid m\leq u\leq M\}-\min\{g(u)\mid m\leq u\leq M\}$. It follows that $g\circ f\in \mathscr{R}[a,b]$. $\Box$

Say we want to evaluate $\sum_{n=1}^\infty \dfrac{2n-1}{2^n}$ (which is convergent by ratio test). Consider $$\begin{align}s_n&=\sum_{k=1}^n \dfrac{2k-1}{2^k}\\
&=\dfrac{1}{2}+\sum_{k=2}^n\bigg(\dfrac{2k-1}{2^k}-\dfrac{2k-3}{2^k}\bigg)+\sum_{k=2}^n \dfrac{2k-3}{2^k}\\
&=\dfrac{1}{2}+\sum_{k=2}^n\dfrac{1}{2^{k-1}}+\sum_{k=2}^n \dfrac{2k-3}{2^k}\\
&=\dfrac{1}{2}+\sum_{k=2}^n\dfrac{1}{2^{k-1}}+\sum_{k=2}^n \dfrac{2(k-1)-1}{2^{k-1+1}}\\
&=\dfrac{1}{2}+\sum_{k=2}^n\dfrac{1}{2^{k-1}}+\sum_{k=1}^{n-1} \dfrac{2k-1}{2^{k+1}}\\
&=\dfrac{1}{2}+\sum_{k=2}^n\dfrac{1}{2^{k-1}}+\dfrac{1}{2}s_n-\dfrac{2n-1}{2^n}\\
&=1+2\bigg(1-\dfrac{1}{2^{n-1}}\bigg)-\dfrac{2n-1}{2^n}\end{align}$$ As $n\to \infty$, $s_n\to 3$.

Many manipulations of sums and other formulas become significantly simpler if we use the bracket notation: $$[\text{statement}]=\begin{cases} 1,\quad \text{if the statement is true;}\\ 0,\quad \text{if the statement is false.}\end{cases}$$ Then we can write $$\sum_{R(i)} a_i=\sum_i a_i[R(i)]$$ since the terms of that infinite sums are zero when $R(i)$ is false. In fact, we have seen this expression before -- Kronecker delta symbol is a special case of bracket notation: $$\delta_{ij}=[i=j]=\begin{cases}1,\quad \text{if }i=j\\ 0,\quad \text{if }i\neq j\end{cases}.$$ With bracket notation, we can derive rule (3) from rule (1) and (2): $$\begin{align}\sum_{R(p(j))} a_{p(j)}&=\sum_j a_{p(j)}[R(p(j))]\\
&=\sum_j \sum_i a_i [R(i)][i=p(j)]\\
&=\sum_i a_i[R(i)]\sum_j [i=p(j)].\end{align}$$ If $p$ is a permutation of the range, then we are left with $\sum_i a_i [R(i)]$, which is $\sum_{R(i)} a_i$.

We can also derive rule (2): $$\sum_{i=1}^n\sum_{j=1}^i a_{ij}=\sum_{i,j} a_{ij}[1\leq i\leq n][1\leq j\leq i]=\sum_{i,j}a_{ij}[1\leq j\leq n][j\leq i\leq n]=\sum_{j=1}^n\sum_{i=j}^n a_{ij},$$ since $[1\leq j\leq n][1\leq j\leq i]=[1\leq j\leq i\leq n]=[1\leq j\leq n][j\leq i\leq n]$.

More to explore:
Möbius inversion formula
arithmetic function

Reference
illustration

Saturday, 7 May 2016

Evaluate $\int_0^\pi \log(1-2a\cos x+a^2)\;dx$

From the identity $$1-a^{2n}=(1-a^2)\prod_{i=1}^{n-1}(1-2a\cos \dfrac{i\pi}{n}+a^2),\quad a\in \Bbb R$$ prove that $$\int_0^\pi \log(1-2a\cos x+a^2)\;dx=\begin{align}\begin{cases}0\quad &|a|<1\\ 2\pi\log|a|\quad &|a|>1.\end{cases}\end{align}$$


The identity follows from finding the roots of $\dfrac{1-a^{2n}}{1-a^2}$, whose proof is similar to this problem.

I: Elementary real analysis
$$1-a^{2n}=(1-a^2)\prod_{i=1}^{n-1}(1-2a\cos \dfrac{i\pi}{n}+a^2)\\
\dfrac{1-a^{2n}}{1-a^2}=\prod_{i=1}^{n-1}(1-2a\cos \dfrac{i\pi}{n}+a^2)\\
1+a^2+a^4+\cdots+a^{2n-2}=\prod_{i=1}^{n-1}(1-2a\cos \dfrac{i\pi}{n}+a^2)\\
\dfrac{\pi}{n}\log(1+a^2+a^4+\cdots+a^{2n-2})=\dfrac{\pi}{n}[\log(1-2a\cos \dfrac{\pi}{n}+a^2)+\log(1-2a\cos \dfrac{2\pi}{n}+a^2)+\cdots\\+\log(1-2a\cos \dfrac{(n-1)\pi}{n}+a^2)]$$Recall the motivation of the definition of Riemann sum: we want to approximate an area bounded by a curve by calculating areas of rectangles. Riemann sum is the sum of areas of rectangles. We partition $[0,\pi]$ into $n$ subintervals and find the sum of areas of rectangles each with width $\dfrac{\pi}{n}$ and lengths $\log(1-2a\cos \dfrac{i\pi}{n}+a^2)$ for $i=1,2,\cdots,n$. Therefore, we have $$\begin{align}\int_0^\pi \log(1-2a\cos x+a^2)\;dx&=\lim_{n\to \infty}\dfrac{\pi}{n}\sum_{i=1}^n \log(1-2a\cos \dfrac{i\pi}{n}+a^2)\\
&=\lim_{n\to \infty}\dfrac{\pi}{n}\log(1+a^2+a^4+\cdots+a^{2n-2}).\end{align}$$ When $|a|<1$, $\log(1+a^2+a^4+\cdots+a^{2n-2})=0$. It follows that the integral is $0$ when $|a|<1$. As for $|a|>1$, the trick is to make use of the case $|a|<1$. Note that $a>1$ implies that $\dfrac{1}{a}<1$: $$\lim_{n\to \infty} \dfrac{\pi}{n}\log\bigg(a^{2n-2}(\dfrac{1}{a^{2n-2}}+\dfrac{1}{a^{2n-4}}+\cdots+1)\bigg)=\lim_{n\to \infty} \dfrac{2n-2}{n}\pi \log a=2\pi\log a.$$
II: Complex analysis

More to explore
other proofs
another proof
yet another proof
Evaluating a similar integral by complex analysis methods

Friday, 6 May 2016

Wallis Formula

i) Show that for any $n\in \Bbb N$, $\int_0^{\pi/2}\sin^n x\;dx=\dfrac{n-1}{n}\int_0^{\pi/2}\sin^{n-2} x\;dx$.
ii) Show that for any $k\in \Bbb N$, $$\int_0^{\pi/2}\sin^{2k} x\;dx=\dfrac{(2k-1)(2k-3)\cdots 3\cdot 1}{(2k)(2k-2)\cdots 4\cdot 2}\dfrac{\pi}{2}=\dfrac{(2k)!}{(2^k k!)^2}\dfrac{\pi}{2}$$ and $$\int_0^{\pi/2}\sin^{2k+1} x\;dx=\dfrac{2k(2k-2)\cdots 4\cdot 2}{(2k+1)(2k-1)\cdots 3\cdot 1}=\dfrac{(2^k k!)^2}{(2k+1)!}.$$ iii) For $k\in \Bbb N$, let $$\mu_k=\dfrac{\int_0^{\pi/2}\sin^{2k} x\;dx}{\int_0^{\pi/2}\sin^{2k+1} x\;dx}.$$ Show that $1\leq \mu_k\leq \dfrac{2k+1}{2k}$ for each $k\in \Bbb N$ and consequently that $\mu_k\to 1$ as $k\to \infty$. Deduce that $$\sqrt{\pi}=\lim_{k\to \infty} \dfrac{(k!)^2 2^{2k}}{(2k)!\sqrt{k}}.$$ Thus $\pi\sim \dfrac{(k!)^4 2^{4k}}{((2k)!)^2 k}$. (Hint: $\sin^{2k+1}x\leq \sin^{2k}x\leq \sin^{2k-1}x$ for all $x\in[0,\pi/2]$.)



i) $$\begin{align}\int_0^{\pi/2}\sin^n x\;dx&=-\int_0^{\pi/2}\sin^{n-1} x\;d(\cos x)\\
&=-\sin^{n-1}\cos x\bigg|_0^{\pi/2}+(n-1)\int_0^{\pi/2}\cos^2 x\sin^{n-2} x\;dx\\
&=0+(n-1)\int_0^{\pi/2}\sin^{n-2} x\;dx-(n-1)\int_0^{\pi/2}\sin^n x\;dx\\
\Rightarrow \int_0^{\pi/2}\sin^n x\;dx&=\dfrac{n-1}{n}\int_0^{\pi/2}\sin^{n-2} x\;dx
\end{align}$$ ii) $$\begin{align} \int_0^{\pi/2}\sin^{2k} x\;dx&=\dfrac{2k-1}{2k}\int_0^{\pi/2}\sin^{2k-2} x\;dx\\
&=\dfrac{2k-1}{2k}\dfrac{2k-3}{2k}\int_0^{\pi/2}\sin^{2k-4} x\;dx\\
&=\dfrac{2k-1}{2k}\dfrac{2k-3}{2k}\cdots \int_0^{\pi/2}\sin^4 x\;dx\\
&=\dfrac{2k-1}{2k}\dfrac{2k-3}{2k}\cdots \dfrac{3}{4} \int_0^{\pi/2}\sin^2 x\;dx\\
&=\dfrac{2k-1}{2k}\dfrac{2k-3}{2k}\cdots \dfrac{3}{4} \dfrac{1}{2}\int_0^{\pi/2}\sin^0 x\;dx\\\\
&=\dfrac{(2k-1)(2k-3)\cdots 3\cdot 1}{(2k)(2k-2)\cdots 4\cdot 2}\dfrac{\pi}{2}\\
&=\dfrac{(2k)(2k-1)(2k-2)(2k-3)\cdots 3\cdot 2\cdot 1}{[(2k)(2k-2)\cdots 4\cdot 2]^2}\dfrac{\pi}{2}\\
&=\dfrac{(2k)!}{(2^k\cdot [k(k-1)\cdots 2\cdot 1])^2}\dfrac{\pi}{2}\\
&=\dfrac{(2k)!}{(2^k k!)^2}\dfrac{\pi}{2}
\end{align}$$ The other case is similar.
Question: How come the integral of 'odd sine function' is the 'reciprocal' of that of 'even sine function'?

iii) It is simple to prove the claim with the hint (which is true because $\sin x\leq 1$ when $x\in [0,\pi/2]$). For all $x\in[0,\pi/2]$, $$\sin^{2k+1}x\leq \sin^{2k}x\leq \sin^{2k-1}x\\  \int_0^{\pi/2}\sin^{2k+1}x\;dx\leq \int_0^{\pi/2}\sin^{2k}x\;dx\leq \int_0^{\pi/2}\sin^{2k-1}x\;dx\\ \dfrac{\int_0^{\pi/2}\sin^{2k+1}x\;dx}{\int_0^{\pi/2}\sin^{2k+1}x\;dx}\leq \dfrac{\int_0^{\pi/2}\sin^{2k}x\;dx}{\int_0^{\pi/2}\sin^{2k+1}x\;dx}\leq \dfrac{\int_0^{\pi/2}\sin^{2k-1}x\;dx}{\int_0^{\pi/2}\sin^{2k+1}x\;dx}\\ 1\leq \mu_k\leq \dfrac{\int_0^{\pi/2}\sin^{2k-1}x\;dx}{\int_0^{\pi/2}\sin^{2k+1}x\;dx}$$ We have $\dfrac{\int_0^{\pi/2}\sin^{2k-1}x\;dx}{\int_0^{\pi/2}\sin^{2k+1}x\;dx}=\dfrac{[2^{k-1}(k-1)!]^2}{(2k-1)!}\dfrac{(2k+1)!}{(2^k k!)^2}=\dfrac{(2k+1)2k}{4k^2}=\dfrac{2k+1}{2k}$, hence the claim.

By sandwich theorem, since $\lim_{k\to \infty} \dfrac{2k+1}{2k}=1$, we have $\mu_k\to 1$ as $k\to \infty$. But $\mu_k\to 1$ implies $\sqrt{\mu_k}\to 1$.
Question: Why does $\mu_k$ tend to $1$ intuitively?
We can look at the graphs of powers of $\sin x$. When the powers are close to each other, their graphs are very similar. That's why the ratio of the two integrals tends to $1$.

Now, $$\mu_k=\dfrac{\pi}{2}\dfrac{(2k)!(2k+1)!}{(2^k k!)^4}\\ \sqrt{\mu_k}=\dfrac{\sqrt{\pi}}{\sqrt{2}}\dfrac{\sqrt{(2k)!(2k+1)!}}{(2^k k!)^2}=\sqrt{\pi}\dfrac{\sqrt{2k+1}}{\sqrt{2}}\dfrac{(2k)!}{(2^k k!)^2} \to 1.$$ It follows that $$\sqrt{\pi}=\lim_{k\to \infty} \dfrac{(2^k k!)^2}{(2k)!\sqrt{k}}$$ For the approximation of $\pi$, just take the square of the limit.

Wallis Formula is one of the many formulas that approximates $\pi$. There are other proofs of this formula. See the notes by Steven R. Dunbar.

More to explore
notes by Steven R. Dunbar
math fun facts
notes by Ben Lynn
paper

Tuesday, 19 April 2016

Evaluate $\lim_n \dfrac{\sqrt[n]{n!}}{n}$

Prove that $$\lim_{n\to \infty} \dfrac{\sqrt[n]{n!}}{n}=e^{-1}.$$


I: Taking logarithm
Since $\ln \dfrac{\sqrt[n]{n!}}{n}=\ln \sqrt[n]{\dfrac{n!}{n^n}}=\dfrac{1}{n}\bigg(\ln \dfrac{1}{n}+\ln \dfrac{2}{n}+\cdots+\ln \dfrac{n}{n}\bigg)$, we have $$\begin{align}\lim_{n\to \infty} \dfrac{\sqrt[n]{n!}}{n} &=\exp\bigg(\lim\limits_{n\to \infty}(\dfrac{1}{n}\sum\limits_{k=1}^n\ln \dfrac{k}{n})\bigg)\\ &=\exp\bigg(\int_0^1 \ln x\;dx\bigg)\\ &=e^{-1}\;\Box\end{align}$$
II: Sandwich theorem
For any sequence $(a_n)$ of positive real numbers, we have $$\liminf_n \dfrac{a_{n+1}}{a_n}\leq \liminf_n a_n^{1/n}\leq \limsup_n a_n^{1/n}\leq \limsup_n \dfrac{a_{n+1}}{a_n}$$ Pick $a_n=\dfrac{n!}{n^n}$. Then $\dfrac{a_{n+1}}{a_n}=(1+\dfrac{1}{n})^{-n}$ and $a_n^{1/n}=\dfrac{\sqrt[n]{n!}}{n}$. It follows that $$\liminf_n (1+\dfrac{1}{n})^{-n}\leq \liminf_n \dfrac{\sqrt[n]{n!}}{n}\leq \limsup_n \dfrac{\sqrt[n]{n!}}{n}\leq \limsup_n (1+\dfrac{1}{n})^{-n}.$$ We know $$\liminf_n (1+\dfrac{1}{n})^{-n}=\limsup_n (1+\dfrac{1}{n})^{-n}=e^{-1}.$$ By sandwich theorem, we have $$\liminf_n \dfrac{\sqrt[n]{n!}}{n}=\limsup_n \dfrac{\sqrt[n]{n!}}{n}=\lim_n \dfrac{\sqrt[n]{n!}}{n}=e^{-1}\;\Box$$
III: Stirling approximation $$n!\sim \sqrt{2\pi n}(\dfrac{n}{e})^n\\ \dfrac{\sqrt[n]{n!}}{n}\sim \dfrac{\sqrt[2n]{2\pi}e^{-1}n^{1+1/(2n)}}{n}\to e^{-1}\;\Box$$
IV: Lemma: If $\lim_{n\to\infty}a_n=a$ and $a_n>0$ for all $n$, then we have $$ \lim_{n\to\infty}\sqrt[n]{a_1a_2\cdots a_n}=a.$$ Pick $a_n=\bigg(1+\dfrac{1}{n}\bigg)^n$. Since $a_n>0$ for all $n$ and $\lim_{n\to \infty}a_n=e$, we can apply the lemma: $$\begin{align} e&=\lim_{n\to\infty}\sqrt[n]{a_1a_2\cdots a_n}\\ &=\lim_{n\to\infty}\sqrt[n]{\left(\frac{2}{1}\right)^1\left(\frac{3}{2}\right)^2\cdots\left(\frac{n+1}{n}\right)^n}\\ &=\lim_{n\to\infty}\sqrt[n]{\frac{(n+1)^n}{n!}}\\&= \lim_{n\to\infty}\frac{n+1}{\sqrt[n]{n!}}\\&=\lim_{n\to\infty}\frac{n}{\sqrt[n]{n!}}+\lim_{n\to\infty}\frac{1}{\sqrt[n]{n!}} \tag{*}\\&=\lim_{n\to\infty}\frac{n}{\sqrt[n]{n!}},\end{align}$$ where in $(*)$ we have also used the lemma for $a_n=\dfrac{1}{n}\to 0$. It follows that $$\lim_{n\to \infty} \dfrac{\sqrt[n]{n!}}{n}=e^{-1}\;\Box$$
Reference
mse

Monday, 21 March 2016

Several inequalities

Let $m,n\in \Bbb N, x\in \Bbb R, x\geq 0, x\neq 1$. Prove the followings: if $m>n$, then $\dfrac{x^m-1}{m}>\dfrac{x^n-1}{n}$; if $m<n$, then $\dfrac{x^m-1}{m}<\dfrac{x^n-1}{n}$.

Proof:
Consider the case when $m>n$. The other case is similar. It suffices to show that $n(x^m-1)-m(x^n-1)> 0$ for $x>1$. $$\begin{align}n(x^m-1)-m(x^n-1)&=n(x-1)(x^{m-1}+x^{m-2}+\cdots+1)-m(x-1)(x^{n-1}+x^{n-2}+\cdots+1)\\&=n(x-1)(x^{m-1}+x^{m-2}+\cdots+x^n)+n(x-1)(x^{n-1}+x^{n-2}+\cdots+1)\\&\quad-m(x-1)(x^{n-1}+x^{n-2}+\cdots+1)\\&=n(x-1)(x^{m-1}+x^{m-2}+\cdots+x^n)\\&\quad-(m-n)(x-1)(x^{n-1}+x^{n-2}+\cdots+1)\\&> (x-1)[n\underbrace{(x^n+\cdots+x^n)}_{m-n\; terms}-(m-n)\underbrace{(x^n+\cdots+x^n)}_{n\; terms}]\qquad(*)\\&=(x-1)x^n[n(m-n)-(m-n)n]\\&=0\qquad \Box\end{align}$$ In $(*)$, we have used the facts that $x^{m-i}\geq x^n$ when $i=1,\cdots,m-n$ and $-x^{n-j}\geq -x^n$ where $j=1,\cdots,n$. The case for $0\leq x<1$ also holds because we have $-x^{m-i}\geq -x^n$ when $i=1,\cdots,m-n$ and $-x^{n-j}\leq -x^n$ where $j=1,\cdots,n$.

Remark: This result implies that the sequence of functions $f_n(x)=\dfrac{x^n-1}{n}$ is increasing when $x$ is fixed and $x>1$. The term $-1$ there is crucial. Recall the taylor series of $e^x$ and exponential functions: $$e^x=1+x+\dfrac{x^2}{2!}+\dfrac{x^3}{3!}+\cdots\\ 2^x=e^{(\ln 2)x}=1+(\ln 2)x+\dfrac{((\ln 2)x)^2}{2!}+\cdots.$$ Then $\dfrac{e^x-1}{x}=1+\dfrac{x}{2}+\dfrac{x^2}{6}+\dfrac{x^3}{24}+\cdots$, whereas $\dfrac{e^x}{x}$ or $\dfrac{e^x+5}{x}$ contains the expression $\dfrac{1}{x}$, which means there will be asymptotes.

We can use the proved inequalities to prove some other inequalities.

Let $a,b\in \Bbb R, a>0, b>0, a\neq b, r\in \Bbb Q$ Then $$rb^{r-1}(a-b)<a^r-b^r<ra^{r-1}(a-b)\quad r>1\\ ra^{r-1}(a-b)<a^r-b^r<rb^{r-1}(a-b)\quad 0<r<1.$$ Proof:
When we divide the inequalities by $b^r$, we will see that they resemble the inequalities that we have proved. We just prove the case when $r>1$. Let $r=\dfrac{m}{n}$, where $m,n\in \Bbb N$. $r>1\Rightarrow m>n$. Substituting $x=(\dfrac{a}{b})^{1/n}$ gives $$\dfrac{(\dfrac{a}{b})^{m/n}-1}{m}>\dfrac{(\dfrac{a}{b})^{m/n}-1}{n}\\ \dfrac{a^r-b^r}{mb^r}>\dfrac{a-b}{bn}\\ a^r-b^r>rb^{r-1}(a-b).$$ Similarly, substituting $x=(\dfrac{b}{a})^{1/n}$ yields $$\dfrac{(\dfrac{b}{a})^{m/n}-1}{m}>\dfrac{(\dfrac{a}{b})^{n/n}-1}{n}\\ \dfrac{b^r-a^r}{ma^r}>\dfrac{b-a}{an}\\ a^r-b^r<ra^{r-1}(a-b).\qquad \Box$$

Saturday, 19 September 2015

Discovery work in analysis

In this post, we will deal with statements of the form $$\forall x\;\exists y \bullet P(x,y).$$ To prove these statements, we need some preliminary 'discovery work' before embarking on the proof.

Convergence of sequences
Definition: The sequence $(a_n)$ converges to $l$ if, for any $\epsilon>0$, there exists $N\in \Bbb Z^+$ such that $$n>N \Rightarrow |a_n-l|<\epsilon.$$ We can write either $a_n\to l$ as $n\to \infty$ or $\lim\limits_{n\to \infty}a_n=l$.

Example
A sequence $(a_n)$ is defined by $a_n=\dfrac{3n^2-4n}{(n+1)(n+2)}$ for $n\in \Bbb Z^+$. Show that $\lim\limits_{n\to \infty}a_n=3$.

The definition of convergence involves two quantifiers and is of the form $$\forall \epsilon\;\exists N \bullet P(\epsilon,N)$$ where $P(\epsilon,N)$ is a propositional function and the universes for $\epsilon$ and $N$ are $\Bbb R^+$ and $\Bbb Z^+$ respectively. The structure of the proof starts with an arbitrary $\epsilon$ (in its universe) and then selects a particular $N$ (in its universe) which may depend on $\epsilon$. To complete the proof, we need to show that the propositional function $P(\epsilon,N)$ is satisfied for the arbitrary $\epsilon$ and particular $N$.

We first start by the definition. We need to find a positive integer $N$ such that for all $n>N$, $$|a_n-l|=\left|\frac{3n^2-4n}{(n+1)(n+2)}-3 \right|<\epsilon.$$ But how? We can manipulate $|a_n-l|$ until it is less than any positive $\epsilon$: $$\begin{align}\left| \dfrac{3n^2-4n}{(n+1)(n+2)}-3 \right|&=\left| \dfrac{3n^2-4n-3(n+1)(n+2)}{(n+1)(n+2)} \right|\\&=\left| \dfrac{3n^2-4n-(3n^2+9n+6)}{(n+1)(n+2)} \right|\\&=\left| \dfrac{-13n-6}{(n+1)(n+2)} \right|\\&=\dfrac{13n+6}{(n+1)(n+2)}.\end{align}$$ We want to show $\dfrac{13n+6}{(n+1)(n+2)}$ is less than or equal to some simple fraction which can still be made less than $\epsilon$. Since replacing the numerator with a larger value and replacing the denominator with a smaller value both increases the size of the expression respectively, we have $$\dfrac{13n+6}{(n+1)(n+2)}\leq \dfrac{19n}{(n+1)(n+2)}\leq \dfrac{19n}{n^2}=\dfrac{19}{n}.$$ Now to ensure $\dfrac{19}{n}<\epsilon$, we can take $n>\dfrac{19}{\epsilon}$. But we are not done yet. Recall that the definition requires $N$ to be a positive integer. To fix this, we take $N$ to be the integer part or floor of $\dfrac{19}{\epsilon}$, which is defined to be the largest integer less than or equal to $\dfrac{19}{\epsilon}$ and denoted by $\lfloor \dfrac{19}{\epsilon} \rfloor$. We can now proceed to the proof.

Proof: Let $\epsilon>0$ and $N=\lfloor \dfrac{19}{\epsilon}\rfloor \in \Bbb Z^+$. Then for all integers $n>N$, we have $$\begin{align}\left| \dfrac{3n^2-4n}{(n+1)(n+2)}-3 \right|&=\left| \dfrac{3n^2-4n-3(n+1)(n+2)}{(n+1)(n+2)} \right|\\&=\left| \dfrac{3n^2-4n-(3n^2+9n+6)}{(n+1)(n+2)} \right|\\&=\left| \dfrac{-13n-6}{(n+1)(n+2)} \right|\\&=\dfrac{13n+6}{(n+1)(n+2)}\\ &\leq \dfrac{13+6n}{(n+1)(n+2)}\\&\leq \dfrac{19n}{n^2}\\&=\dfrac{19}{n}\\&< \epsilon\quad \text{since}\;n>\dfrac{19}{\epsilon}.\end{align}$$ Therefore $\lim\limits_{n\to \infty}\dfrac{3n^2-4n}{(n+1)(n+2)}=3$.

Limits of functions
Definition: Let $f:A\subset \Bbb R \to B\subset \Bbb R$. Let $a\in A$. Then $f(x)$ tends to a limit $l$ as $x$ tends to $a$ if, for any $\epsilon>0$, there exists $\delta>0$ such that $$0<|x-a|<\delta \Rightarrow |f(x)-l|<\epsilon.$$ We can write either $f(x)\to l$ as $x\to a$ or $\lim\limits_{x\to a}f(x)=l$.

Example
Show that $\lim\limits_{x\to 2}2x^2-5x=-2$.

We need to ensure that $|f(x)-l|=|2x^2-5x+2|$ is less than any specified positive $\epsilon$ by taking $x$ such that $0<|x-2|<\delta$. So we consider $|2x^2-5x+2|$: $$|2x^2-5x+2|=|(x-2)(2x-1)|=|x-2||2x-1|.$$ We can control the size of $|x-2|$ since we can choose $\delta$ such that $|x-2|<\delta$. As for $|2x-1|$, we can rewrite it in terms of $|x-2|$ using the triangle inequality: $$\begin{align}|2x-1|&=|2(x-2)+3|\\ &\leq |2(x-2)|+|3|\\ &=2|x-2|+3.\end{align}$$ Therefore $$|2x^2-5x+2|=|x-2||2x-1|\leq |x-2|(2|x-2|+3).$$ Say $|x-2|<1$. Then $2|x-2|+3<5$. If, in addition, $|x-2|<\dfrac{\epsilon}{5}$, then $|x-2|(2|x-2|+3)$ will be less than $\epsilon$. We are now ready to start the proof.

Proof: Let $\epsilon>0$ and $\delta=\min\{1,\dfrac{\epsilon}{5}\}$. Then $$0<|x-2|<\delta \Rightarrow |x-2|<1 \wedge |x-2|<\frac{\epsilon}{5}\\ \begin{align}\Rightarrow |2x^2-5x+2|&=|x-2||2x-1|\\ &\leq |x-2|(2|x-2|+3)\\ &<5|x-2|\\ &<\epsilon \end{align}$$ Therefore $\lim\limits_{x\to 2}2x^2-5x=-2$.

Remark: The choice of $\delta=\min\{1,\dfrac{\epsilon}{5}\}$ is arbitrary. Choosing $\delta=\min\{\dfrac{1}{2},\dfrac{\epsilon}{4}\}$ will also work.

Sunday, 12 July 2015

Famous inequalities

In this post we prove several important inequalities that often arise in functional analysis.

Cauchy-Schwartz inequality
Let $x$ and $y$ be two vectors in $\mathbb{R}^n$. The Cauchy-Schwartz inequality states that $|\langle x,y \rangle| \leq \lVert x \rVert \lVert y \rVert$. Equality holds if and only if $x$ and $y$ are linearly dependent, that is, if $x=\lambda y$ for some scalar $\lambda$.

Proof 1: dot product
Note that $w \cdot w=w_1^2+w_2^2+\cdots+w_n^2 \geq 0$ for any $w \in \mathbb{R}^n$. We rescale $x$ and $y$ to new vectors which have the same length, namely $\lVert x \rVert y$ and $ \lVert y \rVert x$. Then

$$\begin{align} \langle \lVert x \rVert y-\lVert y \rVert x,\lVert x \rVert y-\lVert y \rVert x \rangle &\geq 0\\
\lVert x \rVert^2 \langle y,y \rangle-2\lVert x \rVert \lVert y \rVert \langle x,y \rangle+\lVert y \rVert^2 \langle x,x \rangle & \geq 0\\
2\lVert x \rVert^2 \lVert y \rVert^2-2\lVert x \rVert \lVert y \rVert \langle x,y \rangle & \geq 0\\
\langle x,y \rangle \leq \lVert x \rVert \lVert y \rVert
\end{align}$$

Similarly, setting $\langle \lVert x \rVert y+\lVert y \rVert x,\lVert x \rVert y+\lVert y \rVert x \rangle \geq 0$ gives us $-\langle x,y \rangle \leq \lVert x \rVert \lVert y \rVert$. Combining both cases, we have $|\langle x,y \rangle| \leq \lVert x \rVert \lVert y \rVert.\:\Box$

Proof 2: orthogonality
We orthogonally decompose $x$ into a component parallel to $y$ and a component perpendicular to $y$, and use the fact that the perpendicular component has a non-negative square norm.

$$\begin{align}\lVert x-\frac{\langle x,y \rangle}{\langle y,y \rangle}y \rVert^2 & \geq 0\\ \langle x-\frac{\langle x,y \rangle}{\langle y,y \rangle}y,x-\frac{\langle x,y \rangle}{\langle y,y \rangle}y \rangle & \geq 0\\ \langle x,x \rangle-2\frac{|\langle x,y \rangle|^2}{\langle y,y \rangle}\langle x,y \rangle+\frac{|\langle x,y \rangle|^2}{\langle y,y \rangle} & \geq 0\\ \langle x,x \rangle-\frac{|\langle x,y \rangle|^2}{\langle y,y \rangle} & \geq 0 \quad\Box \end{align}$$

Proof 3: discriminant
$\langle \lambda x-y, \lambda x-y \rangle=\lambda^2\langle x,x \rangle-2\lambda\langle x,y \rangle+\langle y,y \rangle$
This is a quadratic polynomial in $\lambda$, which is nonnegative for every $\lambda$, hence its discriminant $\Delta \leq 0$.
So $\langle x,y \rangle^2-\langle x,x \rangle \langle y,y \rangle \leq 0 \iff |\langle x,y \rangle|^2 \leq \lVert x \rVert^2 \lVert y \rVert^2.\:\Box$

Proof 4: Lagrange's identity [Check this out for more details.]
$|\langle x,y \rangle|=\lVert x \rVert \lVert y \rVert \iff$ $x$ and $y$ are linearly dependent $\iff$ the sequences $(a_i)$ and $(b_i)$ are proportional, where $x=(a_1,a_2,\cdots,a_n)^T$ and $y=(b_1,b_2,\cdots,b_n)^T$.

Define $(a_i)$ and $(b_i)$ to be proportional if $a_ib_j=a_jb_i$ for every pair $i,j$, or equivalently $a_ib_j-a_jb_i=0$ for every pair $i,j$. Thus

$$\begin{align}\sum_{i,j} (a_ib_j-a_jb_i)^2&=0\\
\sum_{i,j} (a_i^2b_j^2-2a_ia_jb_ib_j+a_j^2b_i^2)&=0\\
2(\sum_i a_i^2)(\sum_j b_j^2)-2(\sum_i a_ib_i)^2&=0.\:\Box \end{align}$$

The inequality together with the equality case, follows immediately, provided that the two sequences are positive.

Intuition for this inequality:
We restate the inequality as $|\langle x,y \rangle| \leq \lVert x \rVert$ for all normalised vector $y$, namely $\lVert y \rVert=1$. Then $\langle x,y \rangle$ is the component of the vector $x$ in the direction $y$. So the inequality can be thought of as saying that the component of a vector $x$ in a single direction is bounded by the magnitude of $x$.



Lemma
Let $0<\lambda<1$. Then $t^\lambda \leq 1-\lambda+\lambda t$ for all $t \geq 0$. This inequality becomes equality only when $t=1$.

Proof
Define $f: [0,\infty) \to \mathbb{R}$ by $f(t)=1-\lambda+\lambda t-t^\lambda$.
Then $f'(t)=\lambda-\lambda t^{\lambda-1}=\lambda(1-\dfrac{1}{t^{1-\lambda}})$.
$f'(t) \begin{cases} >0\;\text{if}\; t>1 \\ <0\;\text{if}\; 0<t<1 \end{cases}$
Thus $f(1)=0=\min f$ and $f(t)\geq 0$ for all $t \geq 0$, with equality iff $t=1$.
$\Rightarrow t^\lambda \leq 1-\lambda+\lambda t \;\; \forall t \geq 0, \quad t^\lambda=1-\lambda+\lambda t \;\; \text{iff} \;\; t=1\:\Box$

The inequalities that follow all use the notion of conjugate exponents.

Conjugate exponents are positive real numbers $p,q$ such that $\dfrac{1}{p}+\dfrac{1}{q}=1$.
For example, the pair $1,\infty$ is a pair of conjugate exponents since $p \to 1 \Rightarrow q \to \infty$.
If $p,q$ are integers, the only pair of conjugate exponents is $2,2$.

Young’s inequality
Let $p,q$ be conjugate exponents with $1<q<\infty$. Then $ab \leq \dfrac{a^p}{p}+\dfrac{b^q}{q}$ for all $a,b \geq 0$.
Equality holds iff $a^p=b^q$.

Proof 1: the above lemma
If $b=0$, there is nothing to prove.
Assume $b>0$. Using the lemma, substitute $\frac{1}{p}<1$ for $\lambda$ and $a^pb^{-q}$ for $t$.
Then we have
$$\begin{align}a^pb^{-q} &\leq 1-\frac{1}{p}+\frac{1}{p} a^pb^{-q}\\
ab^{\frac{-q}{p}} &\leq \frac{1}{p} a^pb^{-q}+\frac{1}{q} \quad [\frac{1}{p}+\frac{1}{q}=1]\\
ab^{\frac{-q}{p}+q} &\leq \frac{a^p}{p}+\frac{b^q}{q}\\
ab &\leq \frac{a^p}{p}+\frac{b^q}{q} \quad [\frac{q}{p}+1=q \Rightarrow \frac{-q}{p}+q=1],\end{align}$$
with equality when $t=1$, namely $a^pb^{-q}, a^p=b^q. \:\Box$

[How do we know we can prove $ab \leq \frac{a^p}{p}+\frac{b^q}{q}$ by proving $t^\lambda \leq 1-\lambda+\lambda t$? We divide Young's inequality by $b^q$, which gives us $\frac{a}{b^{q-1}}\leq \frac{1}{p}\cdot \frac{a^p}{b^q}+\frac{1}{q}$.]

Proof 2i: convex function
Recall that a function $f:I \to \mathbb{R}$ is convex if for all $x,y \in I$ and $\lambda \in [0,1]$, $f((1-\lambda)x+\lambda y)\leq (1-\lambda)f(x)+\lambda f(y)$.
We can make use of the convexity of the exponential function.
Substitute $\ln a^p$ for $x$ and $\ln b^q$ for $y$.
Since $\frac{1}{p}+\frac{1}{q}=1$, we have $\large e^{\frac{1}{p}\ln a^p+\frac{1}{q}\ln b^q} \leq \frac{1}{p}e^{\ln a^p}+\frac{1}{q}e^{\ln b^q}$.
Thus $ab \leq \frac{a^p}{p}+\frac{b^q}{q}.\:\Box$

Proof 2ii: concave function
Alternatively, we can use the concavity of the logarithmic function.
$\log(\frac{a^p}{p}+\frac{b^q}{q}) \geq \frac{1}{p}\log a^p+\frac{1}{q}\log b^q=\log(ab)\:\Box$

Proof 3: integration
Consider $f(x)=x^{q-1} \quad q>1$.
Then $g(y)=y^{p-1}$ where $\frac{1}{p}+\frac{1}{q}=1$.
So $ab \leq \int_0^b x^{q-1}\:dx+\int_0^a y^{p-1}\:dy=\frac{b^q}{q}+\frac{a^p}{p}.\:\Box$

Proof 4: differentiation
Let $f(a)=\frac{a^p}{p}+\frac{b^q}{q}-ab$. Then $f'(a)=a^{p-1}-b$.
Setting $f'(a)=0$, we have $a=b^\frac{1}{p-1} \Rightarrow a^p=b^\frac{p}{p-1}=b^q$.
$\min f=f(b^\frac{q}{p})=0 \Rightarrow 0 \leq \frac{a^p}{p}+\frac{b^q}{q}-ab \Rightarrow ab \leq \frac{a^p}{p}+\frac{b^q}{q}.\:\Box$

Remark: Young's inequality is one of the most important inequalities. It says that a product can be estimated by a sum. The [[AM-GM inequality]] is its special case. The Cauchy-Schwartz inequality can be proved from the AM-GM inequality. [to be explored in another post]

Hölder's inequality
Let $p,q$ be conjugate exponents with $1<q<\infty$. For any integer $n\geq 1$, assume that $a_1,\cdots,a_n$ and $b_1,\cdots,b_n$ are nonnegative. Then $\sum\limits_{k=1}^n a_kb_k \leq (\sum\limits_{k=1}^n a_k^p)^\frac{1}{p} (\sum\limits_{k=1}^n b_k^q)^\frac{1}{q}$.

Proof from Young's inequality:
Let $A=(\sum\limits_{k=1}^n a^p)^\frac{1}{p}$ and $B=(\sum\limits_{k=1}^n b^q)^\frac{1}{q}$.
Then $\dfrac{\sum\limits_{k=1}^n a^p}{A^p}=1$ and $\dfrac{\sum\limits_{k=1}^n b^q}{B^q}=1$.
Put $a=\dfrac{a_k}{A}, b=\dfrac{b_k}{B}$ in Young's inequality.
$\begin{align}\frac{a_kb_k}{AB} &\leq \frac{a_k^p}{pA^p}+\frac{b_k^q}{qB^q} \quad \forall k=1,2,\cdots,n\\
\sum\limits_{k=1}^n \frac{a_kb_k}{AB} &\leq \frac{1}{p}+\frac{1}{q}=1\\
\sum\limits_{k=1}^n a_kb_k &\leq (\sum\limits_{k=1}^n a^p)^\frac{1}{p} (\sum\limits_{k=1}^n b^q)^\frac{1}{q}\:\Box \end{align}$

We will delve into the applications of these inequalities in another post.

References:
proof 1 of Young’s inequality, Hölder's inequality
proof 4 of Cauchy-Schwartz inequality
Intuition of Cauchy-Schwartz inequality

Related:
Equality in Young's inequality for convolution
Young's inequality for three variables
Hölder's inequality with three functions

Friday, 3 July 2015

AM-GM inequality

Let $a_1,\cdots,a_n$ be positive real numbers. Then $$\sqrt[n]{a_1\cdots a_n}\leq \dfrac{a_1+\cdots+a_n}{n},\qquad (*)$$ with equality iff all $a_k\:(1\leq k\leq n)$ are equal.

Proof by standard induction
Let $H(n)$ stand for the hypothesis that inequality $(*)$ is valid for $n$. For $n=2$, we have $$\sqrt{a_1a_2}\leq \dfrac{a_1+a_2}{2}.\qquad (**)$$ This follows from $(\sqrt{a_1}-\sqrt{a_2})^2\geq 0$. Moreover, equality in $(**)$ holds iff $a_1=a_2$. Now we will show that $H(2)$ and $H(n)$ together imply $H(n+1)$. Let $$A_{n+1}=\dfrac{a_1+\cdots+a_n+a_{n+1}}{n+1}.$$ Then $$\begin{align}A_{n+1}&=\dfrac{1}{2n}[(n+1)A_{n+1}+(n-1)A_{n+1}]\\&=\dfrac{1}{2n}[(a_1+\cdots+a_n)+(a_{n+1}+A_{n+1}+\cdots+A_{n+1})]\\&\geq \dfrac{1}{2n}(n \sqrt[n]{a_1\cdots a_n}+n\sqrt[n]{a_{n+1}A_{n+1}^{n-1}})\\&\geq \sqrt[2n]{a_1\cdots a_n a_{n+1} A_{n+1}^{n-1}},\end{align}$$ where the first inequality follows from $H(n)$, while the second inequality follows from $H(2)$. Now, $H(n+1)$ follows from $$A_{n+1}^{2n}\geq a_1\cdots a_{n+1}A_{n+1}^{n-1}.$$ Equality holds iff $a_1=\cdots=a_n$ and $a_{n+1}=A_{n+1}$, or $a_1=\cdots=a_{n+1}$. $\Box$

Proof by analysis
The inequality $$\inf x +\inf y \leq \inf (x+y)$$ can be generalised to $$\sum\limits_{i=1}^n \inf f_i(x) \leq \inf \sum\limits_{i=1}^n f_i(x).$$ [Below we used $\sum$ to mean $\sum\limits_{i=1}^n$.]
Taking log on both sides of $(*)$, $$\sum \ln a_i\leq n \ln(\dfrac{\sum a_i}{n}).$$
Adding $n$ on both sides, $$\sum (1+\ln a_i)\leq n+n \ln(\dfrac{\sum a_i}{n}).$$
Claim $$f_i(x)=a_ix-\ln x\;\text{and}\;\min f_i(x)=1+\ln a_i.$$ Then $f_i'(x)=a_i-\frac{1}{x}$ and $f_i''(x)=\dfrac{1}{x^2}>0.$ It follows that $\min f_i(x)=1+\ln a_i$.
Now suppose $$f(x)=\sum f_i(x)=(\sum a_i)x-n\ln x.$$ Then $f'(x)=\sum a_i-\frac{n}{x} \Rightarrow x=\dfrac{n}{\sum a_i}$ and $f''(x)=\dfrac{n}{x^2}>0$. It follows that $\min f(x)=n+n\ln \dfrac{\sum a_i}{n}$.
Therefore $n+\ln a_1+\cdots+\ln a_n \leq n+n\ln \dfrac{\sum a_i}{n}\Rightarrow \dfrac{1}{n}\ln(a_1\cdots a_n)\leq \ln\dfrac{\sum a_i}{n}.\;\Box$

An application
Prove that $\{(1+\frac{1}{n})^n\}$ is monotonic increasing and bounded.
Proof: By the AM-GM inequality, we have $$\sqrt[n+1]{(1+\frac{1}{n})^n\cdot 1}<\dfrac{1}{n+1}[n(1+\frac{1}{n})+1]=1+\dfrac{1}{n+1}.$$ This is equivalent to $$(1+\dfrac{1}{n})^n<(1+\dfrac{1}{n+1})^{n+1},$$ which shows that $\{(1+\frac{1}{n})^n\}$ is monotonic increasing as required. To find an upper bound of the sequence, for $n>5$, using the AM-GM inequality once more, we have $$\sqrt[n+1]{(\dfrac{5}{6})^6\cdot 1^{n-5}}<\dfrac{1}{n+1}[6\cdot \dfrac{5}{6}+(n-5)\cdot 1]=\dfrac{n}{n+1},$$ and so $(\dfrac{5}{6})^6<(\dfrac{n}{n+1})^{n+1}$, or equivalently, $(1+\dfrac{1}{n})^{n+1}<(\dfrac{6}{5})^6$. Therefore, $$(1+\dfrac{1}{n})^n<(1+\dfrac{1}{n})^{n+1}<(\dfrac{6}{5})^6<3,\quad (\text{for}\; n>5).$$ Since $(1+\dfrac{1}{n})^n<3$, we conclude that $\{(1+\frac{1}{n})^n\}$ is bounded. $\Box$

More applications

Reference:
Excursions in Classical Analysis: Pathways to Advanced Problem Solving and Undergraduate Research