54
$\begingroup$

(A follow-up of sorts to this question.)

The quantity $\left\lfloor \frac{n!}{11e}\right\rfloor$ is always even, which can be proved as follows.

Using the sum for $\frac{1}{e}$, we split the fraction up into three parts:

  • $A_n=\sum_{k=0}^{n-11} (-1)^k\frac{n!}{11k!}$ is a multiple of the even integer $10! \binom{n}{11}$, and so can be ignored.
  • $B_n=\sum_{k=n-10}^n (-1)^k\frac{n!}{11k!}=\frac{1}{11}\sum_{k=0}^{10} (-1)^{n-k}(n)_k$. This is a finite sum of falling factorials, all of which are polynomial in $n$ with integer coefficients. So $B_n$ is of the form $\frac{P(n)}{11}$ where $P(n)$ is a polynomial in $n$ with integer coefficients.
  • $C_n = \sum_{k=n+1}^{\infty} (-1)^k\frac{n!}{11k!}$ is an alternating series whose terms decrease monotonically in absolute value, and so $|C_n|<\frac{n!}{11(n+1)!}<\frac{1}{11}$.

Putting all this together, we can see that:

  • Since $B_n$ is always an integer multiple of $\frac{1}{11}$ and $|C_n|<\frac{1}{11}$, $C_n$ can only affect the value of $\left\lfloor \frac{n!}{11e}\right\rfloor$ when $B_n$ is an integer. In this case it will change the parity when $C_n$ is negative (i.e., $n$ is even) and leave it alone when $C_n$ is positive.
  • Since $P(n)=11B_n$ is a polynomial with integer coefficients, $B_n$'s integer status is $11$-periodic, which means that whether $C_n$ affects the parity of $\left\lfloor \frac{n!}{11e}\right\rfloor$ is $22$-periodic.
  • Similarly, the parity of $\lfloor B_n \rfloor$ is also $22$-periodic.

So the parity of $\left\lfloor \frac{n!}{11e}\right\rfloor$ is $22$-periodic. Moreover, we can compute its first $22$ values to be: $$ 0, 0, 0, 0, 0, 4, 24, 168, 1348, 12136, 121360, 1334960, 16019530, 208253902, 2915554640, 43733319612, 699733113794, 11895462934514, 214118332821268, 4068248323604100, 81364966472082010, 1708664295913722230 $$ (a sequence which does not appear to be in OEIS).

All of these are even, and so $\left\lfloor \frac{n!}{11e}\right\rfloor$ must be even for all $n$.


This is not a very satisfying proof, though; in the end, it looks like we need a random $2^{22}$-fold coincidence to go our way in order to get the result we want. (In fact, that's the only place we used the specific value of $11$ in our proof at all; the rest of the proof shows that the parity of $\left\lfloor \frac{n!}{ke}\right\rfloor$ is $2k$-periodic for all positive integers $k$.) Even though $11$ was chosen arbitrarily, it looks like the heuristic probability of everything lining up falls off rapidly enough that it's surprising it all works out for any $k$ which is even that large.

Can someone convince me that this fact is less surprising than it looks? I would take either a completely different proof that established the result with less case analysis, or a reason why the parity of these numbers can be expected to be non-independent...

$\endgroup$
4
$\begingroup$

Half a suggestion for simplification: It seems a little awkward to work with the parity of the floor of $n!/11e$ when the more fundamental question is why the fractional part of $n!/ 22e$ is always less than 1/2 or $$\left\{\frac{n!}{22e}\right\}<\frac12.$$

Your $A_n/2$ is always an integer, so it has zero fractional part.

The fractional part of $B_n/2=P(n)/22$ is of course 22-periodic. Evaluate the polynomial $P(n)$ modulo 22 for a complete residue system modulo 22, e.g. for the integers 0 through 21. (N.B. $P(n)$ is not strictly a polynomial -- it involves a factor of $(-1)^n$ -- but that does not affect its periodicity for any even period.)

$C_n/2$ is small in magnitude and its sign alternates with a period 2 which divides 22.

Although this is a small change, I feel that reworking the proof in this way may be more illuminating and remove some of the "magic" and obfuscation of the underlying ideas.

$\endgroup$

Your Answer

By clicking "Post Your Answer", you acknowledge that you have read our updated terms of service, privacy policy and cookie policy, and that your continued use of the website is subject to these policies.

Not the answer you're looking for? Browse other questions tagged or ask your own question.