Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

Show that there is no function $f: \mathbb{N} \to \mathbb{N}$ such that $f(f(n))=n+1987, \ \forall n \in \mathbb{N}$.

share|improve this question

5 Answers 5

up vote 20 down vote accepted

Here is an alternative approach. It is obvious that such an $f$ must be an injection. Now, look at sets $\mathbb{N}$, $A = f(\mathbb{N})$ and $B = f(f(\mathbb{N})) = \{n + 1987 \ | \ n \in \mathbb{N}\}$.

It is easy to see that $B \subset A \subset \mathbb{N}$, and also from the injectivity of $f$ that $f$ induces a bijection between the disjoint sets $\mathbb{N} \setminus A$ and $A \setminus B$. Therefore, $\mathbb{N} \setminus B = (\mathbb{N} \setminus A) \cup (A \setminus B)$ must contain an even number of elements. But $|\mathbb{N} \setminus B| = 1987$, which is a contradiction, and we are done.

share|improve this answer
    
Very interesting solution. should say $f(f(n)) = n + 1987$ at the second last line. –  user58512 Mar 9 '13 at 15:33
1  
@user58512 Thanks for the correction! –  Dan Shved Mar 9 '13 at 15:35
    
+1 Great answer, mush easier to follow than the other ones. Only I would have said $B=f(f(\Bbb N))=\{\,i+1987\mid i\in\Bbb N\,\}$ right away, which avoids making a case distinction (and also like your answer avoids any commitment to where the natural numbers start exactly ;-). –  Marc van Leeuwen Mar 9 '13 at 15:40
    
@MarcvanLeeuwen I've updated the answer. Is this what you had in mind? If not, feel free to improve it! –  Dan Shved Mar 9 '13 at 15:53

Here is a generalisation.

Proposition. For positive integers $k,l$, the functional equation $$ f^k(n)=n+l\qquad\text{for all $n$} $$ has no solutions $f$ in the functions $\Bbb Z\to\Bbb Z$, or in the functions $\Bbb N\to\Bbb N$, unless $k$ divides $l$.

In the case $k\mid l$, one does of course have solutions, for instance $n\mapsto n+l/k$.

Proof. Assume that $f$ satisfies the functional equation.

  • For all $n$ one has $f(n+l)=f^{k+1}(n)=f(n)+l$.
  • Therefore $f(n+l)-(n+l)=f(n)-n$, and $f(n)-n$ is constant when $n$ varies over any congruence class modulo $l$.
  • The image under $f$ of such a congruence class is therefore another congruence class, and $f$ gives rise to a function $\bar f:\Bbb Z/l\Bbb Z\to\Bbb Z/l\Bbb Z$.
  • Since $(\bar f)^k(\bar n)=\bar n$ for all $\bar n\in\Bbb Z/l\Bbb Z$, this function $\bar f$ is a bijection.
  • Put $S=\sum_{i=0}^{l-1}(f(i)-i)$; then $l$ divides $S$ since $\sum_{i=0}^{l-1}f(i)\equiv\binom l2=\sum_{i=0}^{l-1}i\pmod l$, so put $s=S/l$.
  • From the functional equation $\sum_{i=0}^{l-1}\bigl(f^k(i)-i\bigr)=\sum_{i=0}^{l-1}l=l^2$.
  • By a telescopic sum, $f^k(i)-i=\sum_{j=0}^{k-1}\bigl(f^{j+1}(i)-f^j(i)\bigr)$.
  • Since each $(\bar f)^j$ is a bijection, this implies $$\sum_{i=0}^{l-1}\bigl(f^k(i)-i\bigr) =\sum_{j=0}^{k-1}\sum_{i=0}^{l-1}(f^{j+1}(i)-f^j(i)\bigr) =\sum_{j=0}^{k-1}S=kS=kls.$$
  • Therefore $l^2=kls$, so $l=ks$ and $k$ divides $l$.
share|improve this answer

Just a minor variation of the answer by user58512, for fun; like that answer it works even if we replace $\Bbb N$ by $\Bbb Z$. The equation $f(n+1987)=f(n)+1987$ in that answer means that $$f(n+1987)-(n+1987)=f(n)-n,$$ so it shows that $f(n)-n$ only depends on the class of $n$ modulo $1987$. Also the map $\bar f$ that $f$ induces on $\Bbb Z/1987\Bbb Z$ is surjective (the class of $n$ is in the image of $\bar f^2$) hence bijective: $f(n)$ runs over all congruence classes as $n$ runs over all congruence classes modulo $1987$.

Now let $S$ be the sum of $f(n)-n$ over all those congruence classes, obviously an integer. But computing the sum of $1987=f(f(n))-n=\bigl(f(f(n))-f(n)\bigl)+\bigr(f(n)-n\bigr)$ over all those congruence classes, one gets on one hand the odd number $1987^2$, and on the other hand the even number $2S$; contradiction.

share|improve this answer

Hint $\ $mod $\rm\,p\!:\ f(f(n)) = n+p\equiv n\:$ is an involution, hence $\rm\:p\:$ odd $\Rightarrow$ that it has a fixed point $\rm\:f(n)\equiv n,\:$ so $\rm\:f(n) = n\!+\!k p,\ k\in\Bbb Z.\:$ Now the orbit of $\rm\:f\:$ on $\rm\,n\,$ yields a contradiction

$$\rm\begin{array}{rlcl} &\rm n &\rm \to &\rm \color{#C00}{n+kp} \\ \to &\rm \color{#0A0}{n\!+\!p} &\rm \to &\rm n\!+\!(k\!+\!1)p \\ \to &\rm n\!+\!2p &\rm \to &\rm n\!+\!(k\!+\!2)p\\ \to &\rm n\!+\!3p &\rm \to &\rm n\!+\!(k\!+\!3)p\\ &\rm\ \cdots &\rm &\rm \quad\cdots \\ \to &\rm \color{#C00}{n\!+\!kp} &\rm \to &\rm n\!+\!(k\!+\!k)p = \color{#0A0}{n\!+\!p}\ \Rightarrow\ 2k=1\ \Rightarrow\Leftarrow\: k\in\Bbb Z\\ \end{array}$$

Remark $\ $ This was a hint I posted many years ago in another math forum. You can find many further posts here exploiting parity and involutions by searching on involution and Wilson (group theoretical form of Wilson's theorem).

share|improve this answer

We prove that if $f(f(n)) = n + k$ for all $n$, where $k$ is a fixed positive integer, then $k$ must be even. If $k = 2h$, then we may take $f(n) = n + h$.

Suppose,

$f(m) = n$ with $m= n (mod $ k $)$.

Then by an easy induction on $r$ we find $f(m + kr) = n + kr, f(n + kr) = m + k(r+1)$.

We show this leads to a contradiction.

Suppose $m < n$,

$n = m + ks$ for some $s > 0$ $\implies f(n) = f(m + ks) = n + ks$.

But $f(n) = m + k, so m = n + k(s - 1) >= n$. Contradiction.

So we must have $m\ge n$, so $m = n + ks$ for some $s \ge 0$.

But now,

$f(m + k) = f(n + k(s+1)) = m + k(s + 2)$.

But $f(m + k) = n + k$, so $n = m + k(s + 1) > n$. Contradiction again.

So if $f(m) = n$, then $m$ and $n$ have different residues $(mod $ k $)$.

Suppose they have $r_1$ and $r_2$ respectively.

Then the same induction shows that:

All sufficiently large $s= r_1 (mod k)$ have $f(s)= r_2(mod k)$,

and that all sufficiently large $s = r_2 (mod k)$ have $f(s) = r_1 (mod k)$.

Hence if $m$ has a different residue $r(mod k)$, then $f(m) cannot have residue $r_1$ or $r_2$.

For if f(m) had residue $r_1$, then the same argument would show that all sufficiently

large numbers with residue $r_1$ had $f(m) = r (mod k)$.

Thus the residues form pairs, so that if a number is congruent to a particular residue, then f of the number is congruent to the pair of the residue. But this is impossible for $k$ odd.

share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.