Una funzione "particolare"

[Gi.]

Sia $ f(n)= n+\lfloor \sqrt{n} \rfloor $. Dimostrare che, per ogni intero positivo $ m $, la sequenza

$ n,f(n),f(f(n)),f(f(f(n))),... $

contiene il quadrato di un intero.

[Gi.]

Ok, credo di essere riuscito a risolverlo.

Consideriamo i numeri della forma $ n=m^2+b $ (tutti gli interi positivi possono essere scritti in questa forma).
Sia $ g(n)=\lfloor \sqrt{n} \rfloor $, allora per $ b $ piccoli $ g(n)=n $, in particolare

$ m^2\le n <(m+1)^2 $

$ m^2\le n^2+b <m^2+2m+1 $

$ 0 \le b <2m+1 $


Definiamo $ f^r(m)=f(f(f(f(...(f(n)... $

Notiamo che per i numeri della forma $ n=m^2+1 $ vale $ f^2(n)=(n+1)^2 $
Dimostriamolo

$ f(n)=n+g(n) $

$ 1<2m+1 \Rightarrow g(n)=n $

$ f(m^2+1)= m^2+1+m $

$ m+1<2m+1 \forall m\ge 1 \Rightarrow g(n)=n $

$ f^2(m^2+1)= m^2+1+m+m= m^2+2m+1= (m+1)^2 $


Proviamo ora a controllare come si comportano invece i numeri della forma $ n=m^2+2 $

$ 2<2m+1 \Rightarrow g(n)=n $

$ f(m^2+2)= m^2+2+m $

$ m+2<2m+1 \forall m\ge 1 \Rightarrow g(n)=n $

$ f^2(m^2+2)= m^2+2+m+m= m^2+2m +1+1= (m+1)^2+1 $

Proviamo a generalizzare con un numero della forma $ n=m^2+b $, prendiamo $ b<2m+1 $, per cui $ g(n)=n $

$ f(m^2+b)= m^2+b+m $

Adesso vogliamo $ m+b<2m+1 $, il che accade per $ m\ge b $, per cui ancora una volta $ g(n)=n $

$ f^2(m^2+b)= m^2+b+m+m= m^2+2m+1+(b-1)= (m+1)^2 +(b-1) $

E abbiamo finito per i numeri in cui $ m\ge b $, infatti iterando la funzione possiamo ricondurci ad uno dei casi analizzati prima (poichè si nota che il resto $ b $ decresce di uno ogni due iterazioni), di conseguenza la sequenza contiene il quadrato di un intero.

Adesso dobbiamo occuparci del caso $ m<b $, definiamo allora $ b=m+k $, per cui consideriamo numeri della forma $ n=m^2+m+k $, come prima prendiamo $ b=m+k<2m+1 $, per cui $ g(n)=n $

$ f(m^2+m+k)= m^2+m+k+m= m^2+2m+k= (m+1)^2+(k-1) $

ma ora abbiamo concluso, infatti $ k<2m+1 $, perchè $ k=b-n $, per cui $ b-n<2m+1 $, $ b<3m+1 $, chiaramente vero perchè $ b<2n+1 $. Ci siamo dunque ricondotti ad un caso che sappiamo già raggiungere un quadrato prima o poi.

Secondo voi funziona?

[<enigma>]

Hint per la soluzione figa (l'idea non è molto diversa):

Testo nascosto:

Come cambia la quantità $(n -\left \lfloor \sqrt n \right \rfloor ^2 ) \pmod {\left \lfloor \sqrt n \right \rfloor }$?