I have this problem:

Consider the function $f : \mathbb{N} \rightarrow \mathbb{N}$ defined, for every $n \in \mathbb{N}$, by

$$f(n) = (n+1)! - 1$$

Prove that $f$ is injective.

How do I solve this problem?


The easiest way probably to prove this is by proving that $f$ is strictly increasing. You can do that quite easily using induction.


Suppose $f(n)=f(m)$. Then $(n+1)!-1=(m+1)!-1$. Adding $1$ to each side we conclude that $(n+1)!=(m+1)!$. We assume without loss of generality, by swapping the names of $m,n$ if necessary, that $n\ge m$. We now divide both sides by $(m+1)!$ to conclude $$1=\frac{(n+1)!}{(m+1)!}=\frac{(m+1)!(m+2)(m+3)\cdots(n+1)}{(m+1)!}=(m+2)(m+3)\cdots (n+1)$$

If there is even one term on the right, that term is $n+1>1$, which is a contradiction. Hence there are no terms on the right, i.e. $n=m$.


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.