$f(f(n))=f(n+1)-1$ sui naturali

[Gi81]

Trovare tutte le funzioni $f: NN -> NN$ tali che per ogni $n in NN$ valga $f(f(n))=f(n+1)-1$

[kobeilprofeta]

la funzione identica sicuramente.

[Black Magic]

Supponiamo che si abbia:
$f(n) = m$ e $m>n$

Allora si deve avere:
$f(m)=f(n+1)-1$, chiaramente non può essere $m=n+1$ altrimenti si avrebbe un assurdo. Ad ogni modo, abbiamo supposto $f$ crescente, quindi si avrebbe che:
$f(m) -f(n+1) = -1$, con $ m>n+1$
questo è assurdo, perché $f$ è crescente.
Se invece $f(n) $f(f(n))
Se $n=0$ trovo che è impossibile per ipotesi (si avrebbe $f(0)<0$), dunque non mi resta che $f(n) = n$

Q.E.D.

[Gi81]

@BlackMagic:

Non abbiamo supposto $f$ crescente.
Comunque, anche supponendolo, la prima parte è corretta
(cioè, è vero che deve valere $f(n)<=n$ per ogni $n$)
però la seconda parte no, o meglio non è completa: hai solo dimostrato che $f(0)=0$,
ma mancano tutti gli altri naturali.

[Black Magic]

Se suppongo $f(n)>n$ per $\forall n$, la $f$ è strettamente monotona crescente. Per questo nella prima parte della dimostrazione ne facevo cenno.
Per la seconda parte, ho supposto che $f(n) Allora $f(0)=0$, da cui consegue:

$f(0)=f(1)-1$
$f(1)=1$

In particolare è la prima uguaglianza che mi permette di sfruttare il Principio di Induzione. Supponendo infatti $f(n) = n$, dimostro che $f(n+1)= n+1$, difatti si ha:

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

E ciò prova che $f(n) = n, \forall n \in N$.

[Gi81]

"Black Magic":
Se suppongo $f(n)>n$ per $\forall n$, la $f$ è strettamente monotona crescente.

Perchè?

[Black Magic]

Ti chiedo scusa, abbaglio spaventoso: $f(n) > n$ non implica in nessun modo che $f$ sia strettamente crescente!

[milizia96]

Sia $m$ il minimo valore che assume $f(n)$ quando $n$ varia tra gli interi positivi.
Sia $a$ il minimo intero positivo tale che $f(a)=m$.
Allora, prendendo $n=a-1$ nella condizione del problema, si ottiene $f(f(a-1))= m-1$.
Se fosse $f(a-1) > 0$ avremmo un assurdo (per come è definito $m$).
Quindi $f(a-1) = 0$. Se $a-1 > 0$ avremmo un assurdo (per come è definito $a$).
Allora $a=1$.
Concludiamo quindi che $f(0)=0$, e da qui per induzione si ottiene che è $f(n)=n$ per ogni $n$ naturale.

E se fosse $f: ZZ^{-} -> ZZ^{-}$?
E se fosse $ f: ZZ -> ZZ $?

[Gi81]

Corretto

"milizia96":E se fosse $f: ZZ^{-} -> ZZ^{-}$?
E se fosse $ f: ZZ -> ZZ $?

Mi sembra che non siano molto semplici da risolvere.
Sbaglio?