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$
No comments:
Post a Comment