On permutation

Let x_1, x_2, \dots, x_k be vectors of m – dimensional Euclidean space such that x_1+x_2+\cdots+x_k=0. Prove that there exists a permutation \pi of the integers \{1, 2, \dots,k\} such that

    \[\left \| \sum_{i=1}^{n} x_{\pi(i)} \right \|\leq\left ( \sum_{i=1}^{k} \left \| x_i \right \|^2 \right )^{1/2}\]

for each n=1,2, \dots, k.

Solution

We define \pi inductively. Set \pi(1)=1.Assume \pi is defined for i=1, 2, \dots, n and also

(1)   \begin{equation*} \left \| \sum_{i=1}^{n} x_{\pi(i)} \right \|^2 \leq \sum_{i=1}^{n} \left \| x_{\pi(i)} \right \|^2 \end{equation*}

Note that (1) is true for n=1. We choose \pi(n+1) in a way that (1) is fulfilled for n+1 instead of n. Set y=\sum \limits_{i=1}^{n} x_{\pi(i)} and A=\{1,2, \dots, k\} \setminus \{\pi(i) : i=1,2, \dots, n\}. Assume that (y, x_r)>0 for all r \in A.  Then \left ( y , \sum \limits_{r \in A} x_r \right )>0 and in view of y + \sum \limits_{r \in A} x_r =0 ones gets -(y, y)>0 which is impossible. Hence , there is r\in A such that

(2)   \begin{equation*} (y, x_r)\leq 0\end{equation*}

Put \pi(n+1) = r . Then using (2) and (1) we have

    \begin{align*} \left \| \sum_{i=1}^{n+1} x_{\pi(i)} \right \|^2 &= \left \| y + x_r \right \|^2 \\ &=\left \| y \right \|^2 + 2\left ( y, x_r \right ) + \left \| x_r \right \|^2 \\ &\leq \left \| y \right \|^2 + \left \| x_r \right \|^2 \\ &\leq \sum_{i=1}^{n} \left \| x_{\pi(i)} \right \|^2 + \left \| x_r \right \|^2\\ &= \sum_{i=1}^{n+1} \left \| x_{\pi(i)} \right \|^2 \end{align*}

which verifies (1) for n+1. Thus we define \pi for every n=1, 2, \dots, k. Finally from (1) we get

    \[\left \| \sum_{i=1}^{n} x_{\pi(i)} \right \|^2 \leq \sum_{i=1}^{n} \left \| x_{\pi(i)} \right \|^2 \leq \sum_{i=1}^{k} \left \| x_i \right \|^2\]

Read more

Does there exist an expression?

For which positive integers n does there exist expression

    \[\mathbb{R}^2 = \bigcup_{m=1}^{\infty} A_m\]

where each A_m is a disk of radius 1 such that each point x \in \mathbb{R}^2 belongs to either the boundary of some A_m or to precisely n interiors of the sets A_1 , A_2 , \dots ?

(Euler Competition , 2017)

Solution [official]

For none n. Assume , on the contrary , that such expression exists for some value of n. Let us first note that the set of disks is countable hence the Lebesgue measure of the union of all the circles is 0.

Further, consider any disk A_i and let us show that the number of the other disks it intersects is finite. Indeed, each disk that intersects A_k would have to be a subset of the disk or radius 3 co-centric with A_k. All such disks together would cover an area of at most 9 \pi so that each point is covered by at most n disks. Hence the total area of disks that intersect A_k is at most 9 \pi n and therefore there are not more than 9n of them.

Now, let us introduce the function f:\mathbb{R}^2 \rightarrow \mathbb{N} whose value f(P) is the number of disks A_i that P belongs to. Note that

  • f(P)=n for almost all P \in \mathbb{R}^2
  • f(P) is constant on every connected component of \mathbb{R}^2 \setminus \bigcup \limits_{k=1}^{\infty} \partial A_k.

What remains to be shown is that this is impossible. Since the disk A_i intersects only with finitely many other disks , let us consider the circular arc between two such intersection points such that the arc XY in the figure above. But then obviously the value f(P) for points on one side of the arc and f(P) for points on the other side of the arc differ by 1. For the collections of disks that cover the two regions is different – A_i is only on one side of the circular arc.

Read more

A divergent series

Let a_n be a positive and strictly decreasing sequence such that \lim a_n =0. Prove that the series

    \[\mathcal{S} = \sum_{n=1}^{\infty} \frac{a_n-a_{n+1}}{a_n}\]

diverges.

Solution

We shall begin with a lemma.

Lemma: Let x_1, \dots, x_n \in (0, 1). It holds that

    \[\sum_{i=1}^n (1-x_i) \geqslant 1 - \prod_{i=1}^n x_i\]

Proof: We are using induction on n. For n=1 it is trivial. Suppose that it holds for n=k. Then

    \begin{align*} \sum_{i=1}^{k+1} (1-x_i) &= \left( \sum_{i=1}^{k} (1-x_i)\right) + (1-x_{k+1}) \\ &\geqslant \left(1 - \prod_{i=1}^k x_i\right) + (1-x_{k+1}) \\ &= 1 - \prod_{i=1}^{k+1} x_i + \\ & \quad \quad +\left(1 - \prod_{i=1}^k x_i\right)\left(1-x_{k+1}\right) \\ &\geqslant 1 - \prod_{i=1}^{k+1} x_i \end{align*}

Thus it holds for n=k+1 and the lemma is proved. Since a_n>0 and \lim a_n =0 I can find 1 = i_1 < i_2 < \cdots such that \frac{a_{i_{r+1}}}{a_{i_r}} < \frac{1}{2} for all r. But then

    \begin{align*} \sum_{n=1}^{i_k-1} \frac{a_n - a_{n+1}}{a_n} &= \sum_{r=1}^{k-1} \sum_{n=i_r}^{i_{r+1}-1}\left(1 - \frac{a_{n+1}}{a_n} \right) \\ &\geqslant \sum_{r=1}^{k-1} \left(1 - \frac{a_{i_{r+1}}}{a_{i_r}} \right) \\ &> \sum_{r=1}^{k-1} \frac{1}{2} \\ &> \frac{k-1}{2} \end{align*}

where in the first inequality the lemma was used.

The exercise can also be found at mathematica.gr . It can also be found in Problems in Mathematical Analysis v1 W.J.Kaczor M.T.Nowak as exercise 3.2.43 page 80 .

 

Read more

Seemous 2017/4

(a) Let n \in \mathbb{N} \cup \{ 0 \}. Evaluate the integral:

    \[\mathcal{J} = \int_0^1 \left( 1 - t \right)^n e^t \, {\rm d}t\]

(b) Let k \in \mathbb{N} \cup \{ 0 \} and let \{x_n\}_{n \geq k} be a sequence defined as

    \[x_n = \sum_{i=k}^n \binom{i}{k} \left(e - 1 - \frac{1}{1!} - \frac{1}{2!} - \cdots -\frac{1}{i!} \right)\]

Find the limit of x_n.

Solution

(a) We have successively:

    \begin{align*} \int_{0}^{1} \left ( 1-t \right )^n e^t \, {\rm d}t &\overset{u=1-t}{=\! =\! =\! =\!} \int_{0}^{1} u^n e^{1-u} \, {\rm d}u\\ &= e \int_{0}^{1}u^n e^{-u} \, {\rm d}u\\ &= e \gamma(n+1, 1)\\ &\!\overset{(*)}{=} e n!\left ( 1- e^{-1} \sum_{k=0}^{n} \frac{1}{k!} \right )\\ &= n! \left ( e - \sum_{k=0}^{n} \frac{1}{k!} \right ) \end{align*}

where \gamma denotes the lower incomplete Gamma function.

(b) We are invoking Tonelli’s theorem. Hence the limit we seek is equal to

    \begin{align*} \sum_{i=k}^{\infty} \binom{i}{k} \sum_{r=i}^{\infty} \frac{1}{(r+1)!} &= \sum_{r=k}^{\infty} \frac{1}{(r+1)!}\sum_{i=k}^{r} \binom{i}{k} \\ &= \sum_{r=k}^{\infty} \frac{1}{(r+1)!} \binom{r+1}{k+1}\\ &= \frac{1}{\left ( k+1 \right )!} \sum_{r=k}^{\infty} \frac{1}{\left ( r-k \right )!}\\ &= \frac{e}{\left ( k+1 \right )!} \end{align*}

Read more

 

An arithmotheoretic sum

For any positive integer n , let \langle n \rangle denote the closest integer to \sqrt{n}. Evaluate:

\displaystyle \mathcal{S}= \sum_{n=1}^{\infty} \frac{2^{\langle n \rangle} +2^{-\langle n \rangle}}{2^n}

(Putnam 2001)

Solution

We begin by the simple observations that \displaystyle \left ( k - \frac{1}{2} \right )^2 =k^2 - k + \frac{1}{4} and \displaystyle \left ( k + \frac{1}{2} \right )^2 =k^2 + k + \frac{1}{4}  . Combining this we get that

\langle n \rangle = k \Leftrightarrow k^2 - k + 1 < n < k^2 + k

Hence

\begin{aligned} \sum_{n=1}^{\infty} \frac{2^{\langle n \rangle} + 2^{-\langle n \rangle}}{2^n} &= \sum_{k=1}^{\infty} \sum_{\langle n \rangle =k} \frac{2^{\langle n \rangle} + 2^{-\langle n \rangle}}{2^n} \\ &= \sum_{k=1}^{\infty} \sum_{n=k^2-k+1}^{k^2+k} \frac{2^k+2^{-k}}{2^n}\\ &= \sum_{k=1}^{\infty} \left ( 2^k + 2^{-k} \right ) \left ( 2^{-k^2+k} -2^{-k^2-k} \right )\\ &= \sum_{k=1}^{\infty} \left [ 2^{-k(k-2)} - 2^{-k(k+2)} \right ]\\ &= 3 \end{aligned}

Read more