4
$\begingroup$

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?

$\endgroup$
0

2 Answers 2

8
$\begingroup$

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

$\endgroup$
5
$\begingroup$

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

$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .