9
$\begingroup$

This is a very interesting word problem that I came across in an old textbook of mine. So I know its got something to do with induction, which yields the shortest, simplest proofs for proving the finite amount of functions, but other than that, the textbook gave no hints really and I'm really not sure about how to approach it. Any guidance hints or help would be truly greatly appreciated. Thanks in advance :) So anyway, here the problem goes:

Let $\mathbb{N}^+$ denote the set of positive integers. Find all functions $f:\mathbb{N}^+ \rightarrow \mathbb{N}^+$ which are strictly increasing and such that for all positive integers $n$, we have $f(f((n))=n+2.$

So I found the function $f(n)=n+1$ works, but I'm not sure if it is the only possibility, and even so, how to prove that it is the only solution.

$\endgroup$
  • 2
    $\begingroup$ The harder part seems to be to prove that one's finding actually are all criteria-fullfilling functions in existence... $\endgroup$ – Marcus Müller Aug 13 '17 at 10:31
10
$\begingroup$

Lemma: $f(k)>k$.

Pf: it is clear that $f(1)≥1$ and that $f(1)\neq 1$ so the claim is true for $k=1$. Inductively suppose it is true up to $k-1$. Then $f(k-1)>k-1$ so $f(k-1)≥k$. Since $f(k)>f(k-1)$ we are done.

Claim: $f(n)=n+1$

Pf: Indeed the Lemma shows that $f(n)≥n+1$. But $f(f(n))=n+2\implies f(n)≤n+1$ and we are done.

$\endgroup$
3
$\begingroup$

Note that $f(f(1))=3$ and $f(1)\ge 1$

We can't have $f(1)=1$ because that would make $3=f(f(1))=f(1)=1$

If we had $f(1)=3$, we'd have $3=f(f(1))=f(3)$, but $f$ is strictly increasing, so this is a contradiction. As would be if $f(1)=n\gt 3$ when we'd have $3=f(f(1))=f(n)\gt f(1)\gt 3$.

So we have $f(1)=2$, and then $f(2)=f(f(1))=3$ and if $f(r)=r+1$ we have $r+2=f(f(r))=f(r+1)$, and you can prove by induction.

$\endgroup$
2
$\begingroup$

It's quite clear that $f$ cannot fixed a point $k$, i.e. $f(k) \neq k$ for every $k > 0$. Moreover, because $f$ is strictly increasing, we have $f(k) > k$. Therefore, one can write $f(k) = k + r_k$ with $r_k > 0$. Then, given any $k$, we have:

\begin{align*} k + r_k + r_{k + r_k} = f(k + r_k) = k + 2 \end{align*}

Which means that: $r_k + r_{k +r_k} = 2$, yielding that $r_k = 1$ for every $k$.

$\endgroup$

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.