I'm trying to prove that:

$$\sum_{k=1}^\infty\left \lfloor{\frac{n}{p^k}}\right\rfloor \leq 2\sum_{k=1}^\infty\left \lfloor{\frac{n-1}{p^k}}\right\rfloor $$ for composite $n > 4$ where $p$ is any prime less than $n$. The inequality is related to proving that $n|(n-1)!$ for composite $n >4$ and I know the standard proof for that but was wondering if this was an approach one could make.

I also know you can use the fact that $n|(n-1)!$ to prove this but I wanted an analytic solution. Any thoughts? I think it's true but I may be wrong.


  • 2
    $\begingroup$ It can be easily proven that $$2\left\lfloor\frac{n-1}{p^k}\right\rfloor-\left\lfloor\frac{n}{p^k}\right\rfloor\geq -1$$ for all positive integers $n$, $p$, and $k$ with $p>1$, where the equality case is $n=p^k$. By analyzing when $2\left\lfloor\frac{n-1}{p^k}\right\rfloor-\left\lfloor\frac{n}{p^k}\right\rfloor=-1$, you can show that $$\sum_{k=1}^\infty\,\Biggl(2\left\lfloor\frac{n-1}{p^k}\right\rfloor-\left\lfloor\frac{n}{p^k}\right\rfloor\Biggr)\geq -1\,.$$ The equality holds if and only if either $n=p$ or $(n,p)=(4,2)$. $\endgroup$ – Batominovski Jan 22 '17 at 5:22

We want to prove that $$\sum_{k=1}^{\infty}\left(2\left\lfloor\frac{n-1}{p^k}\right\rfloor-\left\lfloor\frac{n}{p^k}\right\rfloor\right)\ge 0$$

Let $n=p^kM_k+R_k$ and $n-1=p^km_k+r_k$ where $M_k,R_k,m_k,r_k$ are integers such that $M_k\ge 0,m_k\ge 0,0\le R_k\lt p^k$ and $0\le r_k\lt p^k$.

Let us separate it into two cases :

  • Case 1 : $n=p^aq$ where $a,q\ge 1\in\mathbb Z,\gcd(p,q)=1$

Since $R_k=0$ for $1\le k\le a$ and $R_k\ge 1$ for $k\gt a$, we have $m_k=M_k-1$ for $1\le k\le a$ and $m_k=M_k$ for $k\gt a$.

If $a=1$, then $$\begin{align}\sum_{k=1}^{\infty}\left(2\left\lfloor\frac{n-1}{p^k}\right\rfloor-\left\lfloor\frac{n}{p^k}\right\rfloor\right)&=\sum_{k=1}^{1}(2m_k-M_k)+\sum_{k=2}^{\infty}(2m_k-M_k)\\\\&=\sum_{k=1}^{1}(M_k-2)+\sum_{k=2}^{\infty}m_k\\\\&\ge (q-2)+0\\\\&\ge 0\end{align}$$ since $q\ge 2$.

If $a=2$, then $$\begin{align}\sum_{k=1}^{\infty}\left(2\left\lfloor\frac{n-1}{p^k}\right\rfloor-\left\lfloor\frac{n}{p^k}\right\rfloor\right)&=\sum_{k=1}^{2}(2m_k-M_k)+\sum_{k=3}^{\infty}(2m_k-M_k)\\\\&=\sum_{k=1}^{2}(M_k-2)+\sum_{k=3}^{\infty}m_k\\\\&\ge (pq+q-4)+0\\\\&\ge 0\end{align}$$ since $(p,q)\not=(2,1)$.

For $a\ge 3$, $$\begin{align}\sum_{k=1}^{\infty}\left(2\left\lfloor\frac{n-1}{p^k}\right\rfloor-\left\lfloor\frac{n}{p^k}\right\rfloor\right)&=\sum_{k=1}^{a}(2m_k-M_k)+\sum_{k=a+1}^{\infty}(2m_k-M_k)\\\\&=\sum_{k=1}^{a}(M_k-2)+\sum_{k=a+1}^{\infty}m_k\\\\&\ge \sum_{k=1}^{a}(p^{a-k}q-2)+0\\\\&\ge \sum_{k=1}^{a}(p^{a-k}-2)\\\\&\ge (2^{a-1}+2^{a-2}+\cdots +2+1)-2a\\\\&=2^a-1-2a\\\\&\ge 0\end{align}$$

  • Case 2 : $\gcd(n,p)=1$

Since $R_k\ge 1$ for every $k$, we have $m_k=M_k$ for every $k$.

Therefore, $$\sum_{k=1}^{\infty}\left(2\left\lfloor\frac{n-1}{p^k}\right\rfloor-\left\lfloor\frac{n}{p^k}\right\rfloor\right)=\sum_{k=1}^{\infty}(2m_k-M_k)=\sum_{k=1}^{\infty}m_k\ge 0$$


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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