un polinomio parecchio limitato

[jordan]

Fissiamo un polinomio $f(x) \in \mathbb{Z}[x]$ e definiamo la sequenza $x_1:=1$, $x_{n}:=f(x_{n-1})$ per ogni $n\in \mathbb{N}$.

Supponendo che

• per ogni $n\in \mathbb{N}_0$ $f(n)>n$
• per ogni $n\in \mathbb{N}_0$ esiste $i\in \mathbb{N}_0$ tale che $n \mid x_i$

mostrare che $f(x)=x+1$.


(Iran TST, 2004)

[dario2994]

Userò implicitamente $x_i>0$ (che si ottiene da $f(n)>n$).
Lemma nemmeno bello:Dati $m,n>0$ esiste $i>m$ tale che $n|x_i$

Testo nascosto:

Sia $X=\max\{x_j\ |\ 0\le j\le m\}$. Per ipotesi esiste $i$ tale che $2nX|x_i$ ma allora vale $x_i\ge 2nX>X$ e perciò $i>m$ è ho dimostrato il lemma dato che $n|x_i$.

Sia $g(n)=f(n)-n$. Per ipotesi $g(n)>0$.
Lemma ben più bello: Per ogni $n\in \mathbb{N}$ vale $g(x_n)\le x_n$

Testo nascosto:

Per induzione su $m\ge n$ dimostro che $g(x_n)|x_{m+1}-x_{m}$

• Passo base: Per $m=n$ è facile dato che vale $g(x_n)=x_{n+1}-x_n$
• Passo induttivo: Vale $x_{m+1}-x_{m}|f(x_{m+1})-f(x_{m})=x_{m+2}-x_{m+1}$ ma per ipotesi induttiva ho $g(x_n)|x_{m+1}-x_{m}$ e unendo le divisibilità ottengo la tesi d'induzione.

Per quanto appena dimostrato ottengo $x_m\equiv x_n\pmod{g(x_n)}$ per ogni $m>n$. Ma il lemma nemmeno bello mi assicura che esiste $u>n$ tale che $g(x_n)|x_u$ e allora ottengo $0\equiv x_u\equiv x_n \pmod{g(x_n)}$.
Quindi ho $g(x_n)|x_n$ e cioè $g(x_n)\le x_n$ che è la tesi.

Applicando il lemma ben più bello ho che vale $0<g(n)\le n$ per infiniti $n$ (dato che gli $x_i$ sono tutti distinti).
Ma $g$ è un polinomio a coefficienti interi e perchè quello sia vero deve essere o che $g(x)=x+k$ oppure $g(x)=k$ per qualche $k$.
Nel primo caso deve valere per forze $k\le 0$ ma allo stesso tempo devo avere (dato che $x_0=1$) $g(1)>0$ da cui $k\ge 0$. Da cui arrivo a $k=0$ e perciò $g(x)=x$ e quindi $f(x)=2x$ e allora ottengo $x_n=2^n$ che palesemente non rispetta le ipotesi.
Se invece $g(x)=k$ deve valere $k>0$ e anche ponendo $x=1$ per lo stesso motivo di prima $k\le 1$, quindi $k=1$. E questo genera $f(x)=x+1$ e $x_n=n+1$ che palesemente rispetta le ipotesi.

p.s. bellissimo problema

[jordan]

Ci ho messo un po' a leggerla, scusa il ritardo; comunque, bella soluzione dario2994