Prove $\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$

Question

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.

Thanks!

Answer 1

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