OliForum Matematico

per caso ogni $n$-upla contiene lo $0$?

Sì, è vero

Innanzitutto da $x_{i+1}^2-x_{i+1}-x_i^2-x_i=0$ ci ricaviamo $\displaystyle x_{i+1}=\frac{1 \pm (2x_i+1)}{2}$, quindi $x_{i+1}=-x_i \lor x_i+1$.
Per non confonderci fra un cambio di segno e un incremento di $1$ dobbiamo eliminare il caso in cui $-x=x+1$, cioè dobbiamo dimostrare che il vettore non contiene l'elemento $-\frac{1}{2}$. Se lo contenesse possiamo considerare il vettore raddoppiato, che sarebbe necessariamente di interi, dove da un elemento al successivo si cambia segno o si somma $2$. Notiamo che qualunque sia il passaggio modulo $4$ il vettore diventa $-1, 1, -1, 1, \dots$ e dato che dobbiamo iniziare con un $-1$ e finire con un $1$ il vettore avrebbe un numero pari di elementi, assurdo.
Ora che possiamo ben distinguere fra cambio di segno e incremento di $1$ procediamo a dimostrare per assurdo che il numero di cambi di segno effettuati fra $x_1$ e $x_n$ (il passaggio da $x_n$ a $x_1$ non lo contiamo) sia dispari a patto di non essere nel vettore nullo.
Se ci fossero solo cambi di segno allora avremmo $x_1=x_n=x$ e dovrebbe valere $x=-x$ cioè dovrebbe essere il vettore nullo, che effettivamente funziona sempre.
Supponiamo quindi che ci sia un $x_i$ tale che $x_{i+1}=x_i+1$, allora dato che ruotare tutti gli elementi ci riporta sempre in un vettore valido possiamo supporre WLOG che quell'elemento sia $x_n$, abbiamo dunque $x_1=x, x_n=x-1$.
Supponiamo per assurdo che il numero di cambi di segno sia pari, allora $x_n=x+k-h=x-1 \Rightarrow h=k+1$ dove $k$ è il numero di incrementi effettuati dopo un numero pari di cambi di segno e $h$ è il numero di incrementi effettuati dopo un numero dispari di cambi di segno. Allora il numero di elementi del vettore è $1 \, (quello \, iniziale)+numero \, passaggi$, dove il numero di passaggi è uguale al numero di cambi di segno più il numero di incrementi. Il numero di incrementi è $h+k=2k+1$ dispari, mentre il numero di cambi di segno è stato supposto pari, quindi il numero di passaggi è dispari e il numero totale di elementi del vettore è pari, assurdo! Dunque si ha un numero dispari di cambi di segno.
Dimostriamo di essere in un vettore di interi. Per quanto detto $x-1=-x+k-h$, dove stavolta $k$ è il numero di incrementi effettuati dopo un numero dispari di cambi di segno e $h$ è il numero di incrementi effettuati dopo un numero pari di cambi di segno. Ne ricaviamo che $2x=k-h+1$. Dato che il numero di passaggi è pari (numero elementi del vettore - 1, il primo) e il numero di cambi di segno è dispari è dispari anche il numero totale di incrementi, quindi lo è $k+h$ e di conseguenza anche $k-h$, quindi $2x=k-h+1$ è un intero pari e quindi $x$ è intero.
Ci manca solo da dimostrare che si ha sempre uno $0$. Se $x=0, 1$ è banale, resta quindi $x \ne 0, 1$. Notiamo che in questo caso $x-1$ ha lo stesso segno di $x$. Supponiamo di non raggiungere mai lo $0$: ciò significa che con gli incrementi non possiamo mai cambiare di segno, altrimenti ci dovremmo necessariamente passare (per andare dagli interi negativi agli interi positivi, mentre dagli interi positivi si resta sempre negli interi positivi), quindi il numero di volte in cui si cambia di segno è effettivamente uguale al numero di cambi di segno, che è dispari, e quindi il segno di $x_n$ è opposto al segno di $x_1$, ma abbiamo detto che questo non può essere, assurdo! Quindi si ha sempre almeno uno $0$.
Da qui non riesco a proseguire, si dimostra facilmente che la somma di tutti gli elementi del vettore è $0$ e quindi ci dev'essere un numero pari di numeri dispari e un numero dispari di numeri pari, ma anche con queste informazioni non trovo un modo semplice per contare il numero effettivo di vettori. Una soluzione fino a questo punto secondo te quanti punti prenderebbe?

Risolvendo $x_i(x_i + 1) = x_{i + 1}(x_{i + 1} - 1)$ in $x_{i + 1}$ otteniamo $\displaystyle x_{i + 1} = \frac{1 \pm (2x_i + 1)}{2}$, quindi $x_{i + 1} = -x_i$ oppure $x_{i + 1} = x_i + 1$.
Ora ci conviene riformulare il problema in questo modo: scegliamo un numero $a$ (che sarebbe $x_1$) e facciamo $n$ mosse che consistono nel sostituire il numero corrente $t$ con (a) $-t$ oppure (b) $t + 1$, in modo che alla fine ci ritroviamo con $a$. In quanti modi possiamo farlo? (Due modi sono da considerarsi distinti se differiscono per il numero di partenza o per la sequenza di mosse)
Osserviamo che, se chiamiamo $p$ il numero di mosse (a) e $q$ il numero di mosse (b), il numero finale sarà $(-1)^pa + s$, dove $s$ è un intero che ha la stessa parità di $q$. Distinguiamo quindi due casi:

• Se $p$ è pari, si deve avere $a + s = a \implies s = 0$, il ché implica che anche $q$ è pari, assurdo perché $p + q = n$ è dispari.
• Se $p$ è dispari, si deve avere $-a + s = a \implies s = 2a$ e quindi $q$ pari. [O meglio, $q$ è necessariamente pari, quindi lo è anche $s$, quindi $a = \frac{s}{2}$ è intero]

Ora poniamo $p = 2k - 1$ e, per $2 \le i \le 2k$, definiamo $y_k$ come il numero di mosse (b) tra la $(i - 1)$-esima e la $i$-esima mossa (a); denotiamo inoltre con $y_1$ il numero di mosse (b) fatte prima della prima mossa (a). Non è difficile notare che valgono le seguenti:
(i) $y_1 + y_2 + \cdots + y_{2k} + 2k - 1 = p + q = n$
(ii) $y_1 - y_2 + y_3 - \cdots + y_{2k - 1} - y_{2k} = 2a$ è pari
Si vede chiaramente che esiste una bigezione tra le $(2k)$-uple $(y_1, \: \dots, \: y_{2k})$ (dove $k$ non è fissato) che soddisfano queste due e le cose che vogliamo contare. D'altra parte, la (i) implica la (ii), quindi ci basta contare le $(2k)$-uple che verificano (i) per ogni possibile $k$, che d'ora in poi saranno felici. Se chiamiamo $f(r)$ il numero di $(2r)$-uple felici, con $r$ stavolta fissato, sappiamo che $f(r)$ è il numero di modi di sommare a $n - 2r + 1$ con $2r$ addendi non negativi, cioè $\displaystyle f(r) = \binom{n}{2r - 1}$. In totale, le $(2k)$-uple felici sono dunque $$\sum_{r = 1}^{\frac{n + 1}{2}} f(r) = \sum_{r = 1}^{\frac{n + 1}{2}} \binom{n}{2r - 1} = \binom{n}{1} + \binom{n}{3} + \cdots + \binom{n}{n} = 2^{n - 1}$$