A strange but interesting Bulgarian Olympiad problem

 The problem is interesting because the result is nice. It is strange (to me) because I have a strange proof, which I don't think I can find in an exam setting. Not sure what the official etc solutions are, but I expect it will be something much simpler.

Anyway, the problem is:

$a_n$ is a sequence such that $a_1 = 1$ and

$$a_{n+1} = \frac{n}{a_n} + \frac{a_n}{n}   \quad \forall n \ge 1$$.

Show that $[a_n^2] = n$ for $n \ge 4$.  ($[x]$ is the integer part of $x$).

Scroll down for a solution.

.

.

.

.

Let $b_n = a_n^2$, the we have that

$$b_{n+1} = \frac{n^2}{b_n} + \frac{b_n}{n^2} + 2 $$

We also have $a_4 = 2 + \frac{1}{6}$ and so $b_4 = 4 + \frac{2}{3} + \frac{1}{36}$. 

So first assume $b_n$ satisfies $n < b_n < n+1$, being true for $n=4$. Then we proceed by induction.

Let us try to find a lower bound for $b_{n+1}$

Now

$$\frac{b_n}{n^2} + \frac{n^2}{b_n} + 2 > \frac{n}{n^2} + \frac{n^2}{n+1} + 2 = n+1 + \frac{1}{n} + \frac{1}{n+1}$$

Trying the same for an upper bound we get

$$\frac{b_n}{n^2} + \frac{n^2}{b_n} + 2 < \frac{n+1}{n^2} + \frac{n^2}{n} + 2  = n + 2 + \frac{n+1}{n^2}$$

We fail to get the upper bound we need (i.e $n+2$), because the lower bound $b_n > n$ is too small for us to get something smaller than $n+2$.

Perhaps we could change $n < b_n < n+1$ to $n + c_n < b_n < n + 1$.

Notice that we got $c_n = \frac{1}{n} + \frac{1}{n-1}$ from the lower bound computations earlier.

And the bound holds for $n = 4$, so if we are able to prove the upper bound of $b_n < n+1$, we will be done.

Let us try to find $d_n$ such that

$$\frac{n+1}{n^2} + \frac{n^2}{n + d_n} + 2  = n + 2$$

If $c_n > d_n$, then we will be done, because instead of $d_n$ if we choose a bigger number, the value of the expression will decrease and this expression with $c_n$ instead of $d_n$ is an upper bound for $b_{n+1}$.

Doing a bit of algebra gives us

$$d_n = \frac{n^2 + n}{n^3 - n - 1}$$

Our $c_n$ we chose was

$$c_n = \frac{1}{n} + \frac{1}{n-1} = \frac{2n-1}{n(n-1)}$$

Since $nc_n \to 2$ while $n d_n \to 1$, we have some hope that this might work.

Now for $n > 2$, $n^3 - n - 1 > n^3 - n^2$ and so

$$d_n = \frac{n^2 + n}{n^3 - n - 1} < \frac{n^2 + n}{n^3 - n^2} = \frac{n + 1}{n(n-1)}$$

For $n > 2$, $2n - 1 > n + 1$ and so

$$ d_n < \frac{n+1}{n(n-1)} < \frac{2n-1}{n(n-1)} = c_n$$

And so we  have the following:

$$n < n + d_n < n + c_n < b_n < n + 1$$

which holds for $n = 4$. And by induction we prove that

$$ n + 1 + c_{n+1} < b_{n+1} < n + 2$$

Thus for $n \ge 4$, $$[a_n^2] = [b_n] = n$$

Periodicity of integer parts of n!/e.

Follow up of the previous puzzle.

Let $M$ be a given positive integer $ > 1$. Let $$S_n = \left\lfloor \frac{n!}{e} \right\rfloor$$

Show that sequence $S_0, S_1, S_2, \dots$ is periodic $\mod M$ with period $2M$.

i.e show that $S_{n+2M} = S_n \mod M$

Scroll down for a solution.

.

.

.

.

Based on the previous puzzle solution, we have that

$$S_n = n! \sum_{k=1}^{m} \frac{2k}{(2k+1)!}$$

where $2m+1$ is the largest odd number $\leq n$.

From this, we can easily derive the following recurrence

$$\begin{aligned}& S_{2n+1} = (2n+1) S_{2n} + 2n \\& S_{2n} = 2n S_{2n-1} \end{aligned}$$

First notice that for any $k \ge 0$,  $S_{2kM} = 2kM S_{2M-1} = 0 \mod M$.

Now an induction like argument (on $(k,r)$) shows that $S_{2kM + r} \mod M$ is independent of $k$ and thus $S_n \mod M$ is periodic with period $2M$

Integer part of n!/e

 This is a classic puzzle. I am hoping the solution is new (unlikely though). Anyway.

The problem is: 

Show that the integer part of  $\dfrac{n!}{e}$ is always an even number, for positive integer $n$.

Scroll down for a solution.

.

.

.

.

.

We will use the following two:

$\textbf{Claim 1}$: 

$$\frac{1}{e} = \sum_{n=1}^{\infty} \frac{2n}{(2n+1)!}$$

$\textbf{Proof:}$

Use

$$\frac{1}{(2n)!} - \frac{1}{(2n+1)!} = \frac{2n}{(2n+1)!}$$

and $$e^x = 1 + \frac{x}{1!} + \frac{x^2}{2!} + \dots $$

(put $x = -1$ above). 

$\textbf{Claim 2}$:

$$\sum_{k = 1}^{n} \frac{a_k - 1}{a_1 a_2 \dots a_k} = 1 - \frac{1}{a_1 a_2 \dots a_n}$$

$\textbf{Proof:}$ Telescoping.

$$ \frac{a_n - 1}{a_1 a_2 \dots a_n} = \frac{1}{a_1 a_2 \dots a_{n-1}} - \frac{1}{a_1 a_2 \dots a_n}$$

Now back to the problem. 

$$\frac{N!}{e} = \sum_{n=1}^{\infty} \frac{2n N!}{(2n+1)!}$$

If $M = 2m+1$ is the largest odd integer $\leq N$ then we have

$$\frac{N!}{e} = \sum_{n=1}^{m} 2n \frac{N!}{(2n+1)!} + N! \sum_{n=m+1}^{\infty} \frac{2n}{(2n+1)!}$$ 

The first $\sum_{n=1}^{m}$ term is an even integer and the second term

$$N! \sum_{n=m+1}^{\infty} \frac{2n}{(2n+1)!} < \sum_{n=m+1}^{\infty} \frac{2n}{(2m+3)(2m+5)\dots(2n+1)} = 1$$

The equality of $1$ is because of claim 2 above (put $a_1, a_2, \dots = 2m+3, 2m+5, \dots$). 

Thus the integer part of $\frac{N!}{e}$ is an even integer. 

$\textbf{Additional Remarks:}$ Note that the above proof can be easily modified to give the following recurrence relation for $S_n = \lfloor n!/e \rfloor$.

$$\begin{aligned}&S_{2n+1} = (2n+1) S_{2n} + 2n \\ &  S_{2n} = 2n S_{2n-1}\end{aligned}$$

which yields the sequence $$0,0,2,8,44, 264, 1854, \dots$$

OEIS entry is here.

Starting Decimal Digits of Integer Square Roots

 Here is a cute result.

Given a finite string of digits $S = a_1 \dots a_k$, show that there is a positive integer $N$ such that the fractional part of $\sqrt{N}$ is of the form $0.S... = 0.a_1 \dots a_k \dots$.

For eg, is $S = "414"$, we have that $\sqrt{2} = 1.414\dots$ and fractional part is $0.414\dots$.

Scroll down for a solution.

.

.

.

.

.

Given $S = a_1 \dots ...a_k$, treat it as the number $M = a_1 a_2\dots a_k$.

We can also assume $a_k < 9$ (otherwise, we can just extend $S$ by the digit $0$).

Now consider $X = 10^{2k} + M$.

There are $2X+1$ numbers between $X^2$ and $(X+1)^2$ (not including $(X+1)^2$). Since $X \ge 10^{2k}$, some number among those is divisible by $10^{2k}$. Say it is $P = 10^{2k} Q$.

We have that

$$X^2 \leq 10^{2k}Q < (X+1)^2$$

which implies

$$ X \leq 10^k \sqrt{Q} < (X + 1)$$

i.e

$$ 10^k + \frac{M}{10^k} \leq \sqrt{Q} < 10^{k} + \frac{M + 1}{10^k}$$

And thus $Q$ is the required number.

For eg for $S = 2026$, we get $Q = 100004053$ and $\sqrt{Q} = 10000.2026479\dots$.