29
$\begingroup$

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.

enter image description here

$\endgroup$
  • $\begingroup$ Perhaps induction $\endgroup$ – Hawk Jan 25 '14 at 5:54
  • $\begingroup$ f ist not monoton until x is not big enough $\endgroup$ – user127.0.0.1 Jan 25 '14 at 6:07
  • $\begingroup$ Idea: maybe the prime factors of $f(x)$ are important. $\endgroup$ – Martín-Blas Pérez Pinilla Jan 25 '14 at 7:57
  • 4
    $\begingroup$ 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)$. $\endgroup$ – G. H. Faust Jan 25 '14 at 15:47
  • $\begingroup$ @G.H.Faust,maybe this problem for any postive integer $n$ is true? $\endgroup$ – china math Jan 27 '14 at 8:42
15
+25
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ 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 $\endgroup$ – zcn Jan 28 '14 at 7:18
  • $\begingroup$ thanks, I added the corresponding inequality to make the step more clear. $\endgroup$ – leshik Jan 29 '14 at 1:56
  • $\begingroup$ I do not understand your "Hence, we have $d_2(x^n-y^n)=d_2(x^n)$... Where did this come from? $\endgroup$ – chubakueno Feb 12 '14 at 6:00
  • $\begingroup$ 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. $\endgroup$ – leshik Feb 12 '14 at 15:16
0
$\begingroup$

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

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

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.