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$.