[Teoria dei numeri] Funzione identità

[dan952]

Sia $f : \mathbb{N} \mapsto \mathbb{N}$ una funzione tale che $f(n+1)>f(f(n))$, dimostrare che $f(n)=n$.

[mklplo751]

Io ci provo,anche se non penso sia facile:

Dato che,la struttura algebrica $(ZZ,+,*)$ non è algebricamente chiusa,penso che si possano considerare solo le funzioni del tipo: \( kn,k+n,n^k,k^n,n^n \) dove $k in NN$ è un parametro.Ora per rispettare la condizione iniziale è facile convincersi che le funzioni \( k^n,n^n \),non soddisfano condizioni,indipendentemente dal valore di k.Mentre le funzioni \( kn,n^k\),soddisfano le condizioni,per $k=1$ e la funzione \( k+n\) per $k=0$,in tutti i casi si ritrova la funzione identità.

[dan952]

Ho editato il problema perché lo ricordavo male

[mklplo751]

ho modificato la pseudo-dimostrazione che ho fatto,spero che vada bene.

[dan952]

Ho modificato il problema la funzione è definita negli interi positivi a valori negli interi positivi...e comunque se in una dimostrazione leggo "penso che" già non va bene...

[mklplo751]

giusto,scusa non avevo letto con attenzione

[dan952]

Suggerimento:
Dimostrare che $f(m) \geq n$ per ogni $m \geq n$.

[ivan_franjic]

Sia $m$ il minimo dell'immagine di $f$.
L'unico numero che assume valore m è lo $0$ ;$m = f(n+1) > f(f(n))$ contraddicendo la minimalità di m.
Rigioco il gioco e ho $ f(N)=min_{n >= N} f(n) $ e $N$ è l'unico che realizza tale minimo.
Ora $ f(N+1) =min_{n >= N+1}f(n) > f(f(N)) => f(N) in {0,1,..,N} $
Chiudo con l'unicità.

[bobus1]

Sia \(\displaystyle \mathbb{N} = \{1,2,3 \dots \} \) e \(\displaystyle f: \mathbb{N} \rightarrow \mathbb{N} \) una funzione tale che \(\displaystyle f(n+1) > f(f(n)) \quad (1) \).

Supponiamo per assurdo che \(\displaystyle f(n) > n \quad (2)\), mostriamo che \(\displaystyle f(1) \) non e' definito.
Si ha che \(\displaystyle f(1) > 1 \) quindi \(\displaystyle f(1) \ne 1 \).
Se \(\displaystyle f(1) = 2 \), allora \(\displaystyle f(2) > f(f(1)) = f(2) \), assurdo, quindi \(\displaystyle f(1) \ne 2 \).
Sia \(\displaystyle f(1) = k \) e \(\displaystyle k > 2 \), allora \(\displaystyle f(2) > f(f(1)) = f(k) \).
Ma applicando alternarivamente \(\displaystyle (1) \) e \(\displaystyle (2) \) si ha che \(\displaystyle f(k) > f(f(k-1)) > f(k-1) > f(f(k-2)) > f(k-2) > \dots > f(f(2)) > f(2) \) che e' in contraddizione con il fatto che \(\displaystyle f(2) > f(k) \).
Quindi \(\displaystyle f(1) \) non e' definito e allora deve essere \(\displaystyle f(n) \leq n \).
Ma se \(\displaystyle f(n) < n \) allora di nuovo \(\displaystyle f(1) < 1 \) non e' definito, quindi \(\displaystyle f(n) = n \).

[dan952]

@ivan
Devo un attimo rivederla...

@bobus
Se neghi con un assurdo $f(n)

Cita

Segnala

[Gi81]

"dan95":Sia $f : \mathbb{N} \mapsto \mathbb{N}$ una funzione tale che $f(n+1)>f(f(n))$, dimostrare che $f(n)=n$.

Prima di tutto, la funzione $f(n):= n$ verifica l'ipotesi, dunque è una funzione accettabile. Mostriamo che è l'unica.


DImostro che $f(n)>=n$ per ogni $n in NN$.

Dimostro per induzione che per ogni $a in NN$ si ha ${(f(a)>= a),(f(m)>= a+1 quad AA m>=a+1):}$
Base : $a=1$.
E' ovvio che $f(1)>=1$.
Inoltre, se per assurdo esistesse $h >= 2$ tale che $f(h)=1$, allora, posto $k:= f(h-1) in NN$, si avrebbe $f(k) = f(f(h-1)) < f(h) = 1$, assurdo.


Passo: Sia $a>=1$ fissato.

Ipotesi: ${( f(1)>=1), (f(2)>=2), (...) , (f(a-1) >= a-1), (f(a)>=a), (f(b)>= a+1 quad AA b>= a+1):}$ Tesi: ${(f(a+1)>=a+1),(f(c)>=a+2 quad AA c>=a+2):}$

Dim: Che valga $f(a+1)>= a+1$ lo si ha gratis dall'ipotesi induttiva con $b=a+1$.
Inoltre, se per assurdo esistesse $h>= a+2$ tale che $f(h) <= a+1$, allora necessariamente $f(h) = a+1$ (per l'ipotesi induttiva). Allora, posto $k:= f(h-1)$, si avrebbe $f(k) = f(f(h-1)) < f(h) = a+1$. Ma allora $f(k)<= a$, da cui (per l'ipotesi induttiva) $k<= a$. Questo significa che $f(h-1)<= a$, da cui (sempre per l'ipotesi induttiva) $h-1<=a$, cioè $h<=a+1$, assurdo.

Da questo segue che $f$ è strettamente crescente, in quanto per ogni $n in NN$ si ha $f(n+1) > f(f(n)) >= f(n)$.
Ora, se per assurdo esistesse $n in NN$ tale che $f(n)>= n+1$, poichè $f$ è crescente avremmo $f(f(n)) >= f(n+1)$, assurdo (per l'ipotesi iniziale). Quindi necessariamente $f(n) =n$ per ogni $n in NN$.

[dan952]

Ok