15
$\begingroup$

I was thinking about this question asked at Math.SE, when I came up with the following conjecture.

For every $q\in\mathbb Q$ consider a sequence $s_n^{(q)}$ (terms within the sequence are indexed by $n\in\mathbb N$): $$s_n^{(q)}=\left\lfloor\frac{n!\cdot q}e\right\rfloor-\,!n\cdot q$$ ($!n$ denotes the subfactorial).

Conjecture: For every $q$ the sequence $s_n^{(q)}$ is periodic. Furthemore, if $q$ is a positive integer is a reciprocal of a positive integer $m$, then the period is: $$p_{1/m}=\begin{cases}m,\quad m\text{ is even}\\2m,\quad m\text{ is odd}\end{cases}$$

Could you suggest any ideas how to prove this conjecture?

$\endgroup$
2
  • 3
    $\begingroup$ $1/e=\sum_{k=0}^\infty\frac{(-1)^k}{k!}$, so your formula is roughly the tail of the series multiplied by $n!\times q$. $\endgroup$ Nov 3, 2015 at 5:21
  • $\begingroup$ Sorry, I made a mistake when I formulated conditions for $m$ or $2m$ period. It happens not when $q$ is an integer, but when it's reciprocal of an integer. $\endgroup$ Nov 3, 2015 at 17:41

2 Answers 2

8
+50
$\begingroup$

Write $$ \frac{n!\,e^{-1}}m=x_n+\frac{(-1)^{n+m+1}y_n}m+\frac{(-1)^{n+1}\delta_n}m \qquad\text{and}\qquad \frac{!n}m=x_n+\frac{(-1)^{n+m+1}y_n}m, $$ where $$ x_n=\frac{n!}{m\cdot(n-m)!}\cdot(n-m)!\sum_{k=0}^{n-m}\frac{(-1)^k}{k!}\in\mathbb Z, \\ y_n=n!\sum_{k=n-m+1}^n\frac{(-1)^{k-(n-m+1)}}{k!}\in\mathbb Z, $$ and $$ \delta_n=\frac1{n+1}\biggl(1-\frac1{n+2}+\frac1{(n+2)(n+3)}-\dotsb\biggr) $$ satisfies $0<\delta_n<1$ (even this rough estimate is sufficient). Note that $$ y_n=n(n-1)\dotsb(n-m+1)-n(n-1)\dotsb(n-m+2)+\dotsb+(-1)^{m-1} $$ is $m$-periodic modulo $m$, because each factor in each term of the latter sum is; in other words, $\{y_n/m\}$ (the fractional part) is periodic with period $m$. It remains to observe that $$ \biggl\lfloor\frac{n!\,e^{-1}}m\biggr\rfloor-\biggl\lfloor\frac{!n}m\biggr\rfloor =\biggl\lfloor\frac{(-1)^{n+m+1}(y_n+(-1)^m\delta_n)}m\biggr\rfloor-\frac{(-1)^{n+m+1}y_n}m $$ and that $$ \biggl\lfloor\frac{\pm(y_n+(-1)^m\delta_n)}m\biggr\rfloor =\biggl\lfloor\frac{\pm y_n}m\biggr\rfloor \quad\text{or}\quad \biggl\lfloor\frac{\pm(y_n-1)}m\biggr\rfloor, $$ respectively, depending on whether $m$ is even or odd. The above argument works for $1/m$ replaced with $\ell/m$, though to guarantee the estimate for $\delta_n$ one needs $|\ell|\ge n$, so that the periodicity will be eventual; the period can double if $\ell<0$.

Proving that $m$ or $2m$ is the minimal period is equivalent to showing that the $m$ residues $(-1)^{m-1}y_0,(-1)^{m-1}y_1,\dots,(-1)^{m-1}y_{m-1}$ are not periodic modulo $m$: $$ (-1)^{m-1}y_0=1, \quad (-1)^{m-1}y_1=1-1, \quad \ldots, \\ (-1)^{m-1}y_k=1-k+k(k-1)-k(k-1)(k-2)+\dots+(-1)^kk!\,, \quad \ldots $$ This seems to be correct but the distribution of those residues modulo $m$ is quite chaotic.

$\endgroup$
6
$\begingroup$

Since $$ \frac1e=e^{-1}=\sum_{k=0}^\infty\frac{(-1)^k}{k!}, $$ we can write $$ q\,n!\,e^{-1}=q\,n!\sum_{k=0}^n\frac{(-1)^k}{k!} +(-1)^{n+1}\frac q{n+1}\biggl(1-\frac1{n+2}+\frac1{(n+2)(n+3)}-\cdots\biggr) =t_n+(-1)^{n+1}\epsilon_n, $$ where $t_n\in\mathbb Z$ and $0<\epsilon_n<1$ for $n\ge q$. Then $\lfloor q\,n!\,e^{-1}\rfloor=t_n$ if $n$ is odd and $=t_n-1$ if $n$ is even. Furthermore, $t_n={}!n\cdot q$. In other words, the sequence $s_n^{(q)}$ alternates with period 2 between $0$ and $-1$ for $n\ge q$ (that is, eventually).

$\endgroup$
2
  • 2
    $\begingroup$ In the last sentence, did you mean that $q$ is an integer? $\endgroup$ Nov 3, 2015 at 17:42
  • 1
    $\begingroup$ Yes, of course, as it was a positive integer at the time the answer was posted. $\endgroup$ Nov 11, 2015 at 2:09

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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