Ciao a tutti
, riprendo questo vecchio topic perché oggi, leggendo un articolo di Vera T. Sós mi sono imbattuto in una generalizzazione carina del teorema di Zeckendorf che voglio condividere. Non so di chi sia la generalizzazione, suppongo di Vera T. Sós, ma non sono sicuro, perché non ho accesso all'articolo, che è solamente citato, dove viene visto discusso tale teorema. La dimostrazione che propongo utilizza le idee chiave di una dimostrazione del Teorema di Zeckendorf che ho visto in passato.
Un po' di notazione e di fatti preliminari.
Sia $\alpha$ un numero irrazionale, denotiamo con $\alpha := [a_0;a_1,a_2,a_3,\ldots]$, $a_i \in \mathbb{N}$ la sua rappresentazione in frazione continua, ossia
$$\alpha = a_0 + \frac{1}{a_1 + \frac{1}{a_2 + \frac{1}{a_3 + \ldots}}}.$$
Indichiamo con $\frac{p_n}{q_n}$ la frazione ridotta ai minimi termini che rappresenta l'$n$-esimo convergente, ossia la frazione continua $[a_0;a_1,\ldots,a_n]$.
Si dimostra che le successioni $(p_n)$ e $(q_n)$, posti come termini iniziali $p_{-1} = 1,\ p_{-2} = 0,\ q_{-1} = 0,\ q_{-2} = 1$, soddisfano le relazioni $$p_n = a_n p_{n-1} + p_{n-2} \quad \text{e} \quad q_n = a_n q_{n-1} + q_{n-2}.$$
Da queste relazioni segue che le due successioni sono debolmente crescenti e nel caso in cui $\alpha$ sia irrazionale, esso sono anche divergenti.
Il teorema afferma che ogni numero naturale $n$ può essere espresso in modo unico come $$\sum_{i=0}^{+\infty}\left(b_i q_i\right)$$
dove
\begin{equation}
0 \leq b_0 < a_1 \text{ , } 0 \leq b_i \leq a_{i+1} \text{ per } i > 0 \qquad \text{(1)}
\end{equation}
e dove
\begin{equation}
\forall i>0 \quad b_i = a_{k+1} \implies b_{i-1} = 0. \qquad \quad \text{(2)}
\end{equation}
Prima della dimostrazione vediamo il caso particolare del Teorema di Zeckendorf: per $\alpha = \phi = \frac{1+\sqrt{5}}{2}$ abbiamo $q_0 = 1, \ q_1 = 1$ e $\forall n\in \mathbb{N} \quad q_{n+2} = q_{n+1}+q_n$. Dunque dato che $b_0 = 0$ e $\forall i > 0 \quad b_i \in \lbrace 0, 1\rbrace$, come conseguenza del teorema si ha proprio il Teorema di Zeckendorf.
Dimostrazione.
Dimostriamo innanzitutto l'esistenza dei $(b_i)$ che soddisfano la tesi e poi dimostreremo l'unicità.
Procediamo per induzione su $n$, il numero da rappresentare.
Per $n=0$ poniamo $(b_i)$ uguale alla successione costante zero.
Sia ora $n>0$, dato che $\alpha$ è irrazionale, abbiamo che la successione dei $q_n$ è divergente, dunque esiste un intero positivo $k$ per cui valgono $q_k < q_{k+1}$ e $q_k \leq n \leq q_{k+1}$.
Se $k = q_{k+1}$ basta porre $b_i=0$ per $i \neq k+1$ e $b_i = 1$ per $i = k+1$. Negli altri casi consideriamo l'intero $h := n - q_k$. Sia $(c_n)$ la successione che rappresenta $h$, essa esiste per ipotesi induttiva. Notiamo intanto che la successione $(b_n)$ definita da
$$b_n=
\begin{cases}
c_n & \text{se } n\neq k\\
c_n + 1 & \text{se } n = k
\end{cases}
$$
è tale per cui $$h = \sum_{i=0}^{+\infty}\left(b_i q_i\right).$$
Mostriamo ora che $\forall i \in \mathbb{N}$ i $b_i$ vale (1). L'ipotesi induttiva ci consente di limitarci solo al caso $i=k$, nel caso in cui $c_k < a_{k+1}$ non ci sono problemi, se invece $c_k = a_{k+1}$, $b_k$ non rispetterebbe i limiti. Notiamo però che in questo caso avremmo $$n \leq (a_{k+1} + 1)q_k \leq a_{k+1}q_k + q_{k-1} = q_{k+1}$$ quindi, dato che $n \leq q_{k+1}$, abbiamo $k = q_{k+1}$, ma questo caso l'abbiamo già trattato.
Mostriamo ora che vale (2).
Per farlo utilizziamo un lemma che ci servirà anche più avanti nella dimostrazione.
Lemma: Sia $(b_i)$ una sequenza che rispetta (1) e (2), allora abbiamo che $$\forall k \in \mathbb{N}_{>0} \quad \sum_{i=0}^{k}\left(b_i q_i\right) < q_{k+1}.$$
Dimostriamolo per induzione su $k$, per $k=1$, poiché $b_0$ vale al massimo $a_1 - 1$, il lemma è vero, infatti $(a_1 - 1)q_0 = a_1 - 1 < a_1$.
Sia ora $k > 1$, ci sono due casi da verificare: se $b_k = a_{k+1}$, allora dato che $b_{k-1}$ deve essere nullo, applicando l'ipotesi induttiva abbiamo che
$$\sum_{i=0}^{k}\left(b_i q_i\right) = \sum_{i=0}^{k-2}\left(b_i q_i\right) + a_{k+1} < q_{k-1} + q_k a_{k+1} = q_{k+1}.$$
Se invece $b_k < a_{k+1}$, basta considerare il massimo valore che può assumere, ossia porlo pari a $a_{k+1} - 1$. Dunque avremmo che
$$\sum_{i=0}^{k}\left(b_i q_i\right) = \sum_{i=0}^{k-1}\left(b_i q_i\right) + a_{k+1} - 1 < q_{k} + q_k(a_{k+1}-1) = q_k a_{k+1} < q_{k+1}.$$
Torniamo alla dimostrazione del teorema.
Se $b_k \neq a_{k+1}$ non c'è alcun problema perché l'ipotesi induttiva ci garantisce che (2) venga rispettata. Supponiamo dunque che valga $b_k = a_{k+1}$, se fosse $b_{k-1} > 0$ avremmo $n \geq a_{k+1}q_k + q_{k-1} = q_{k+1}$, quindi dovrebbe essere $n = q_{k+1}$, abbiamo però che $b_{k+1} = 0$, altrimenti $n$ sarebbe maggiore di $q_{k+1}$, contro le ipotesi. Notiamo quindi che tale situazione non può verificarsi, perché sarebbe in contraddizione con il lemma.
Possiamo ora dimostrare l'unicità della rappresentazione. A tale scopo siano $(b_i)$ e $(c_i)$ due rappresentazioni di uno stesso numero, mostriamo che coincidono.
Sia $(b'_i)$ successione definita da
$$
\begin{cases}
b'_i = b_i & \text{se } c_i \neq b_i \\
b'_i = 0 & \text{se } c_i = b_i
\end{cases}
$$
Sia $(c'_i)$ definita analogamente.
Dunque anche le due successioni $(b'_i)$ e $(c'_i)$ rappresentano uno stesso numero. Sia $$k_1 = \max\lbrace i\in \mathbb{N}: b'_i \neq 0\rbrace \quad \text{ e sia } \quad k_2 = \max\lbrace i\in \mathbb{N}: c'_i \neq 0\rbrace.$$ Tali valori sono definiti se le successioni $(b'_i)$ e $(c'_i)$ sono entrambe non nulle. Supponiamo, senza ledere le generalità, che $k_1 > k_2$ (notiamo che non possono coincidere). Dunque dovremmo avere che il numero rappresentato da $(c'_i)$ è maggiore o uguale a $b_{k_1}$, ma ciò contraddice il lemma. Segue che una delle due successioni è nulla e dunque lo è anche l'altra, in quanto deve rappresentare anch'essa il numero zero. Segue dalla definizione di $(b'_i)$ e $(c'_i)$, che le successioni $(b_i)$ e $(c_i)$ coincidono. Da cui la tesi.