Innanzitutto è immediato notare che $ f^4(n+1)=f^3(f^3(n)-1)=f^3(n)+1 $ e quindi $ f^4(n)=n+f^4(0) $, da cui si ha l'iniettività; inoltre si nota che se $ n>0 $ esiste $ m:\quad f(m)=f(n)+1 $ e quindi la funzione assume tutti i valori dal minimo a $ f(0) $ e poi tutti i valori da un certo punto in poi (essendo iniettiva deve assumere infiniti valori), con un eventuale "buco". Ora chiamiamo $ I $ l'immagine della funzione e distinguiamo due casi:
(i) non esiste $ h $ per cui $ f(f(h))=0 $: allora $ f $ ha minimo in $ f(0) $, perchè altrimenti esiste $ x $ con $ f(0)=f(x)+1 $ da cui per l'iniettività $ 0=f^2(x-1) $, assurdo. In particolare se $ f $ si annulla, $ f(0)=0 $, impossibile. Consideriamo il secondo valore più piccolo dell'immagine: se non viene preso da $ f(1) $, esiste $ y>0 $ per cui $ f(y)+1=f(1) $, da cui $ 1=f(f(y-1)) $ e quindi $ f(y-1)=0 $ e $ f(0)=1 $, assurdo. Ma allora esiste $ z $ per cui $ f(2)=f(z)+1 $ da cui $ 2=f(f(z-1)) $ e quindi $ f(0)=1, f(1)=2 $ e $ f(z-1)=1 $ da cui $ z=1, f(2)=3 $. Ora, considerando di volta in volta quel $ x_n $ per cui $ f(n)=f(x_n)+1 $ si verifica facilmente che $ x_n=n-1 $ e per induzione $ f(n)=n+1 $.
(ii) esiste $ h $ per cui $ f(f(h))=0 $; sia $ f(0)=a $. Notiamo innanzitutto che $ h $ non può stare in $ I $ (se $ h=f(h') $, allora $ f(h'+1)=-1 $).
Supponiamo ora che $ a>2 $: devono esistere $ p,q>0 $ tali che $ f(p)=a-3 $ e $ f(q)=a-2 $; allora $ f(q)=f(p)+1=f^3(p-1) $ e quindi, detto $ r=f^2(p-1) $, vale $ q=f(r) $; se invece $ f(0)=2 $, esiste comunque $ q $ e $ f(q)=0=f(f(h)) $, da cui $ q=f(h) $. In ogni caso se $ a>1 $ esiste un intero $ s $ tale che $ f(f(s))=f(q)=a-2 $; ora vale $ f^3(h)=a=f^3(f^2(q-1)-1) $ da cui $ h+1=f^2(q-1) $. Se esistesse $ s' $ tale che $ f(s')=q-1 $, varrebbe $ f(s'+1)+1=f^3(s')=f^2(q-1)=h+1 $, assurdo perchè $ h $ non è in $ I $. Notiamo però che esiste un unico intero $ x $ tale che $ x $ non sta in $ I $ e $ x+1 $ sta in $ I $, e che sia $ h $ che $ q-1 $ hanno questa proprietà: ma allora $ a-1=f(h+1)=f(q)=a-2 $, assurdo. Quindi $ f(0)=1 $ e $ f(h+1)=a-1=0=f(f(h)) $, ovvero $ f(h)=h+1 $. Ora se $ h=0 $ vale $ f(1)+1=f^3(0)=f(0)=1 $, impossibile. Allora l'immagine della funzione consiste di $ 0,1 $ e tutti e soli i valori maggiori di $ h $; in particolare $ f(f(h-1))-1\geq h+2-1 $ (se $ f(f(h-1))=h+1=f(h) $, allora $ h $ starebbe nell'immagine) e quindi esiste $ r $ per cui $ f^2(h-1)-1=f(r) $, ovvero $ h+3=f^3(f^2(h-1)-1)=f^4(r)
=r+f^4(0)\geq 1+h+2 $ (questo perchè se $ r=0 $ vale $ f(f(h-1))=2 $ e quindi la funzione è suriettiva, assurdo perchè $ h $ non può stare nell'immagine; similmente si dimostra che $ f^4(0)>h+1 $). Dunque $ f^4(0)=h+2=f^3(h-1) $ da cui $ h-1=f(0)=1 $ e $ h=2 $; ora $ f(1)=f^4(h)=h+f^4(0)=6 $. Da qui, sfruttando la semplice formula $ f(n+1)=f^{-1}(n)-1+f^4(0) $, è semplice mostrare per induzione che $ f(2l)=2l+1; f(4l+3)=4l; f(4l-3)=4l+2 $, e verificare che anche questa seconda soluzione soddisfa.
Forse intendevi 2013?
Editato