# How prove this function $f(x)=x!-x^n$ is injective

Question: For any positive integer $n$ such $n\neq 2^m-1, n\ge 2$, and function $f$ defined by $$f(x)=x!-x^n$$

show that : $f:N\to Z$ is injective.

My idea: maybe for $x\neq y$ with $x,y\in N^{+}$, then this equation $$x!-x^n=y!-y^n$$ has no solutions?

$$\Longleftrightarrow x!-y!=x^n-y^n$$ if $(x,y)=d$ then we let $x=dx_{1},y=dy_{1}$ then $$(dx_{1})!-(dy_{1})!=d^n[(x_{1})!-(y_{1})!]$$

To solve this problem, maybe we can prove $f$ is monotonic? But I can't. It is said that this is from Mathematical olympiad problem.

• Perhaps induction – Hawk Jan 25 '14 at 5:54
• f ist not monoton until x is not big enough – user127.0.0.1 Jan 25 '14 at 6:07
• Idea: maybe the prime factors of $f(x)$ are important. – Martín-Blas Pérez Pinilla Jan 25 '14 at 7:57
• May I ask why the case $n = 2^m-1$ is excluded? Based on some computation, the result should hold for all $n \in (1, 5000)$. – G. H. Faust Jan 25 '14 at 15:47
• @G.H.Faust,maybe this problem for any postive integer $n$ is true? – china math Jan 27 '14 at 8:42

Note that the following proof does use the fact that $n\ne 2^m-1$ in the last line only.

The idea is to prove that when $x,y$ are big enough then the function $f(x)=x!-x^n$ is strictly increasing. The rest can be ruled out by considering some divisibility properties.

So let's suppose $x> y$ and $d_p(m)$ denotes the largest power of $p$ that divides $m.$ We have $$x!-y!=x^n-y^n.$$

Take any prime divisor $p|y.$ Then, $p|\ LHS,$ so $p|x.$ Therefore,$$d_p(x!-y!)=d_p(y!)< \frac{y}{p}+\frac{y}{p^2}+...=\frac{y}{p-1}.$$

From the other hand $d_p(x^n-y^n)\ge n$ and we must have $n< \frac{y}{p-1}.$ In particular, $y>n.$

Suppose $p\ge 3,$ then $y>2n.$ This restriction is enough to establish monotonicity of $f.$ Indeed, it is enough to show that for $y>2n,$ $f(y+1)>f(y).$ In other words, we would like to show $$(y+1)!-y!=y\cdot y!> (y+1)^n-y^n.$$

Using the inequality $y!\ge y^{\frac{y}{2}}$ that can be proved by induction or by grouping together $k$ and $y-k$ in the corresponding product, we can estimate $$y\cdot y!\ge y\cdot y^n>y^{n+1}-y^n>(y+1)^n-y^n,$$ and the result follows.

So we are left to consider the case when $p=2$ or $y=2^{\alpha}.$ Since $x$ is even, $d_2(x!-y!)=d_2(2^{\alpha}!)=2^{\alpha}-1.$ If $y=2^{\alpha}|x$ then $x\ge 2y> y+n$ and we can estimate $$x!-y!=y!(x(x-1)...(y+1)-1)\ge (n+1)!(x(x-1)....(x-n)-1)\ge x^n$$ for $x\ge 2n,$ because $k(x-k)\ge x$ for $x\ge 2n$ and $1<k\le n.$

Hence, we have $d_2(x^n-y^n)=d_2(x^n)=\beta n$ and we mush have $\beta n=2^{\alpha}-1=y-1.$

Now we use the fact that $n\ne 2^m-1$ to conclude that $\beta\ne 1$ and thus $\beta\ge 3.$ This implies $y-1\ge 3n,$ $y>2n$ and this case was considered above.

• This is an impressive answer: however, in the key step, i.e. showing $f(y+1) > f(y)$ for $y > 2n$, one would like to show $(y+1)! - y! > (y+1)^n - y^n$. This is however implied by the statement you showed, so there is no flaw – zcn Jan 28 '14 at 7:18
• thanks, I added the corresponding inequality to make the step more clear. – leshik Jan 29 '14 at 1:56
• I do not understand your "Hence, we have $d_2(x^n-y^n)=d_2(x^n)$... Where did this come from? – chubakueno Feb 12 '14 at 6:00
• well, $y=2^a.$ If $x$ is divisible by the same or higher power of $2$ than $y,$ we would get $x\ge 2\cdot 2^a=2y$ and we would be in the previous case. – leshik Feb 12 '14 at 15:16

for $x\neq y$ with $x,y\in N^{+}$, then this equation $$x!-x^n=y!-y^n$$ has no solutions?

W.o.l.o.g. assume $x < y$:

$$y^n-x^n=y!-x!$$

$$(y-x)(y^{n-1}+...+x^{n-1})=({y!}/{x!}-1)x!$$

Thus $y^n$ has to be a multiple of $x$...

• Why is $y$ a multiple of $x$? Taking your last equation modulo $x$ only gives $y^n \equiv 0 \pmod{x}$... – zcn Jan 28 '14 at 4:06
• @user115654 You're right. I was assuming more about $x$ and $y$ than we have. – Mark Hurd Jan 28 '14 at 4:12
• And now I see my deduction can actually be seen from the first line: $y!$ contains $x$, so $y^n$ must too. – Mark Hurd Jan 28 '14 at 4:36