The matter of squares and rectangles

Being in Oxford and not dedicating some time to browse the local book shops is, imho, a crime. In one of my recent visits I found this recreational maths book "Mathematics and Chess" (Dover Publications, 1997) by Miodrag Petković. The very first problem in this book is:

Prove that the total number of rectangles that can be found on a generalized $n \times n$ board is a perfect square of a natural number.

You know, those squares from job interviews and puzzles? Yes, those! So this almost popular matter needs to be sorted out. I will skip the proofs, since almost everything is on Wikipedia these days and the proofs aren't complicated, simple applications of induction. The formula for rectangles is simply beautiful: $$\sum_{k=1}^{n} k^3=\left ( \sum_{k=1}^{n} k \right )^2=\left [ \frac{n(n+1)}{2} \right ]^2$$ Squares and cubes, amazing, isn't it?

While the formula for squares is simply: $$\sum_{k=1}^{n} k^2=\frac{n(n+1)(2n+1)}{6}$$

To the good people who passed away and those who survived the year

Sometimes I think,
Those people left
Just to avoid seeing
The way this world
Becomes insane
And horribly crazy.

Of course I'm wrong
All people die,
Inevitable matter.
But we survived
And they have left
An obvious reminder.

Just a beautiful inequality

Last week, Worldwide Center of Mathematics posted this problem on their Facebook page. So, I felt challenged. The solution turned to be quite simple, but that's not the point. The point is, this inequality simply looks beautiful.

Long story short, the task is to prove the following $$e^{\pi} > \pi^{e}$$

I will use few tricks, in form of this well known inequality $$x-1 \geq \ln(x), \forall x >0$$ and the fact that $x=\ln(\pi) > \ln(e)=1$. In fact this inequality is strict for $\forall x > 1$

As a result $$\ln(\pi)-1 > \ln(\ln(\pi)) \Leftrightarrow \ln(\pi) > 1+\ln(\ln(\pi)) $$

Luckily, exponential function $f(x)=e^x$ is strictly ascending, thus: $$e^{\ln(\pi)} > e^{1+\ln(\ln(\pi))} \Leftrightarrow \pi > e \cdot \ln(\pi) \Leftrightarrow \pi > \ln(\pi^e)$$

Using the exponential function trick again $$e^{\pi} > e^{\ln(\pi^e)} \Leftrightarrow e^{\pi} > \pi^e$$

Another number theory problem

This is the second post dedicated to the problems set posted on "Math, Math Education, Math Culture" LinkedIn group. Here is the original LinkedId discussion, again ... if you happen to have a LinkedIn account. Here is the problem:

Prove that the sequence a₁=1, a₂=11, a₃=111, a₄=1111,... contains an infinite sub-sequence whose terms are pairwise relatively prime.

Few observations first of all, without proving them as it should be fairly trivial, e.g. using induction: $$a_{m+n}=a_{m}\cdot 10^{n}+a_{n}$$

From the above: $$a_{m\cdot n} = a_{(m - 1)\cdot n}\cdot 10^{n} + a_{n} = a_{n}\cdot 10^{n\cdot (m-1)} + a_{n}\cdot 10^{n\cdot (m-2)} + ... + a_{n}\cdot 10^{n} + a_{n} $$

So if $a_{n}$ is divisible by $t\in \mathbb{N}, t>1$ then $a_{m\cdot n}$ is also divisible by $t$ (1).

Now, let's consider the sub-sequence $\left \{ a_{p_{k}} \right \}_{k=1}^{\infty } \subset \left \{ a_{n} \right \}_{n=1}^{\infty }$, where $p_{k}$- k-th prime. I state that this sub-sequence satisfies the condition of the problem. Let's prove it by contradiction.

I.e. let's assume there $\exists k \neq m$ such that $\gcd\left ( a_{p_{m}}, a_{p_{k}}\right )= d > 1$. Because $\gcd\left ( p_{m}, p_{k}\right )= 1$ (i.e. both are prime numbers), then, by applying Bezout's theorem (or lemma), there $\exists r,s\in \mathbb{Z}$ such that: $$r\cdot p_{m} + s\cdot p_{k}=1$$

Both $r,s$ can't be negative and positive as the same time, so we can rewrite it this way: $$r\cdot p_{m} = s\cdot p_{k} + 1$$ assuming both $r$ and $s$ are positive this time.

Because we assumed $\gcd\left ( a_{p_{m}}, a_{p_{k}}\right )= d > 1$, then $d$ should also divide both $a_{r\cdot p_{m}}, a_{s\cdot p_{k}}$ (using (1) proved above). But $$a_{r\cdot p_{m}} = a_{s\cdot p_{k}+1} = a_{s\cdot p_{k}} \cdot 10 + a_{1}$$ which means $d>1$ also divides $a_{1}=1$. Contradiction.

As a result $\forall k \neq m$, $\gcd\left ( a_{p_{m}}, a_{p_{k}}\right )= 1$.

Another probability problem

An interesting set of problems was posted on "Math, Math Education, Math Culture" LinkedIn group few weeks ago. I engaged myself in addressing few of them, so I will be posting my solutions in the next few posts. Just to clarify this from the beginning, interesting doesn't necessarily mean difficult. This particular post is dedicated to the probability problem and here is the original LinkedId discussion, if you happen to have a LinkedIn account. Otherwise, continue reading this post. Here is the problem ...

We have n urns, each of these urns contains A white balls and B black balls. We assume a ball from the first urn is randomly picked and then placed into the second urn, then another ball from the second urn is randomly picked and then placed into the third urn, and so on, until a ball from the last urn is finally randomly picked. If this last ball is white, what probability has this fact?

One way to attack the problem is to use total probability (Wikipedia is probably more descriptive on this topic).

Let's define the following two events:
- W_i - white ball is picked from i-th urn
- B_i - black ball is picked from i-th urn.
It is worth noting that $P\left ( W_{i} \right )+P\left ( B_{i} \right )=1$.

Now, applying total probability we have: $$P\left ( W_{n} \right ) = P\left ( W_{n} | W_{n-1} \right )\cdot P\left ( W_{n-1} \right )+P\left ( W_{n} | B_{n-1} \right )\cdot P\left ( B_{n-1} \right )$$ Where:
- $P\left ( W_{n} | W_{n-1} \right )=\frac{A+1}{A+B+1}$ - translated as "probability to pick a white ball from n-th urn, knowing that a white ball was picked from n-1-th urn"
- $P\left ( W_{n} | B_{n-1} \right )=\frac{A}{A+B+1}$ - translated as "probability to pick a white ball from n-th urn, knowing that a black ball was picked from n-1-th urn".

Putting all these together, we obtain: $$P\left ( W_{n} \right )= P\left ( W_{n-1} \right )\cdot \frac{1}{A+B+1}+\frac{A}{A+B+1}$$ Or, if we note $k= \frac{1}{A+B+1}$, then: $$P\left ( W_{n} \right )= P\left ( W_{n-1} \right )\cdot k+A\cdot k$$

Continuing doing this recursively, we obtain: $$P\left ( W_{n} \right )= P\left ( W_{1} \right )\cdot k^{n-1} + A\cdot \left ( k^{n-1}+k^{n-2}+...+k^{2}+k \right )$$ Where (because W₁ relates to the very first urn): $$P\left ( W_{1} \right )=\frac{A}{A+B}=A\cdot \frac{k}{1-k}$$

Finally: $$P\left ( W_{n} \right )=A\cdot \frac{k^{n}}{1-k}+A\cdot \frac{k^{n}-k}{k-1}=\frac{A}{A+B}$$

Which means, the trick with picking randomly a ball and moving it to the next urn has no effect on the final probability. Interesting, isn't it?

Tackling Andrica's conjecture. Part 3

Here is an interesting, but slightly detached from the previous two articles, result. Let's look at the following two sequences: $$a_{n}=\sqrt{p_{n+1}} - \sqrt{p_{n}}$$ $$b_{n}=\ln\left ( \frac{1+\sqrt{p_{n+1}}}{1+\sqrt{p_{n}}} \right )^{1+\sqrt{p_{n+1}}}$$

Here is a short Python code to visualise the sequences.

And here is how both sequences look like ($a_{n}$ the first and $b_{n}$ the second): Quite asymptotic, aren't they? Indeed they are ...

Lemma 3. $$\sqrt{p_{n+1}} - \sqrt{p_{n}} \leq \ln\left ( \frac{1+\sqrt{p_{n+1}}}{1+\sqrt{p_{n}}} \right )^{1+\sqrt{p_{n+1}}} \leq \left ( \frac{1+\sqrt{p_{n+1}}}{1+\sqrt{p_{n}}} \right )\cdot \left ( \sqrt{p_{n+1}} - \sqrt{p_{n}} \right )$$

Let's look at this function $f_{6}(x)=\frac{\sqrt{p_{n+1}}}{1+x\cdot \sqrt{p_{n+1}}}$. Obviously, ${\ln\left ( 1+x\cdot \sqrt{p_{n+1}} \right )}'=f_{6}(x)$. As a result $$\int\limits_{\sqrt{\frac{p_{n}}{p_{n+1}}}}^{1} f_{6}\left ( x \right )dx = \ln\left ( 1+x\cdot \sqrt{p_{n+1}} \right )|_{\sqrt{\frac{p_{n}}{p_{n+1}}}}^{1}=\ln\left ( \frac{1+\sqrt{p_{n+1}}}{1+\sqrt{p_{n}}} \right )$$

According to Mean Value Theorem, $\exists \mu \in \left (\sqrt{\frac{p_{n}}{p_{n+1}}} ,1 \right )$ such that: $$\int\limits_{\sqrt{\frac{p_{n}}{p_{n+1}}}}^{1} f_{6}\left ( x \right )dx = f_{6}\left ( \mu \right )\cdot \left ( 1- \sqrt{\frac{p_{n}}{p_{n+1}}} \right )$$

Putting all together: $$\ln\left ( \frac{1+\sqrt{p_{n+1}}}{1+\sqrt{p_{n}}} \right ) = \frac{\sqrt{p_{n+1}}-\sqrt{p_{n}}}{1+\mu \cdot \sqrt{p_{n+1}}}$$

Because $$\sqrt{\frac{p_{n}}{p_{n+1}}}< \mu < 1 \Rightarrow 1+\sqrt{p_{n}}< 1+\mu \cdot \sqrt{p_{n+1}} < 1+\sqrt{p_{n+1}} $$

And we get $$\frac{\sqrt{p_{n+1}}-\sqrt{p_{n}}}{1+\sqrt{p_{n+1}}}\leq \ln\left ( \frac{1+\sqrt{p_{n+1}}}{1+\sqrt{p_{n}}} \right )\leq \frac{\sqrt{p_{n+1}}-\sqrt{p_{n}}}{1+\sqrt{p_{n}}}$$ which proves this lemma.

Noting $\Delta_{n}=\sqrt{p_{n+1}}-\sqrt{p_{n}}$, this becomes: $$\frac{\Delta_{n}}{1+\sqrt{p_{n+1}}}\leq \ln\left ( 1 + \frac{\Delta_{n}}{1+\sqrt{p_{n}}} \right )\leq \frac{\Delta_{n}}{1+\sqrt{p_{n}}}$$ or $$\frac{1+\sqrt{p_{n}}}{1+\sqrt{p_{n+1}}}\leq \ln\left ( 1 + \frac{\Delta_{n}}{1+\sqrt{p_{n}}} \right )^{\frac{1+\sqrt{p_{n}}}{\Delta_{n}}}\leq 1$$

Is this result of any use? I don't know yet, but it looks like: $$\left ( 1 + \frac{\Delta_{n}}{1+\sqrt{p_{n}}} \right )^{\frac{1+\sqrt{p_{n}}}{\Delta_{n}}} \rightarrow e, n \to \infty$$ using this result.