Teorema di Zeckendorf

Numeri interi, razionali, divisibilità, equazioni diofantee, ...
Rispondi
Triarii
Messaggi: 464
Iscritto il: 18 nov 2010, 21:14

Teorema di Zeckendorf

Messaggio da Triarii » 15 ago 2013, 15:48

Posto questo fatterello carino che probabilmente molti qua sapranno già :)
Dimostrare che ogni intero positivo $ n $ può essere espresso unicamente come somma di numeri di Fibonacci distinti e non consecutivi.
(Si escluda da queste rappresentazioni il primo "1" della successione, che si farà partire dal secondo "1". Altrimenti l'unicità non è rispettata perchè si potrebbe scambiare l'uno in certi casi)
"We' Inge!"
LTE4LYF

Avatar utente
aetwaf
Messaggi: 41
Iscritto il: 07 ott 2013, 17:54
Località: Torino

Re: Teorema di Zeckendorf

Messaggio da aetwaf » 24 dic 2013, 23:05

Procediamo per induzione.
Sia $ f_k $ il $ k-$ esimo numero di Fibonacci e sia verificato il teorema fino a $ f_k-1$. $ f_{k+1}=f_k+f_{k-1}<2f_k $ allora possiamo esprimere ogni $ n $ tale che $ f_k <n <f_{k+1} $ nel modo richiesto poichè lo esprimeremo come $ f_k+x $ esprimibile nel modo richiesto per ipotesi. Caso base $4=3+1 $.
Dispongo di una meravigliosa dimostrazione di questo teorema che non può essera contenuta nel margine troppo stretto della pagina

Avatar utente
jordan
Messaggi: 3988
Iscritto il: 02 feb 2007, 21:19
Località: Pescara
Contatta:

Re: Teorema di Zeckendorf

Messaggio da jordan » 25 dic 2013, 23:59

aetwaf ha scritto:Sia $ f_k $ il $ k-$ esimo numero di Fibonacci e sia verificato il teorema fino a $ f_k-1$. $ f_{k+1}=f_k+f_{k-1}<2f_k $ allora possiamo esprimere ogni $ n $ tale che $ f_k <n <f_{k+1} $ nel modo richiesto poichè lo esprimeremo come $ f_k+x $ esprimibile nel modo richiesto per ipotesi. Caso base $4=3+1 $.
Se vuoi davvero scrivere le soluzioni in due righe, dovresti tentare di scriverle per bene, senza saltare passaggi logici intermedi che potrebbero sembrarti ovvi: in alcuni casi, oltre che non ovvi, potrebbero essere del tutto errati. Per capirci, avresti perso parecchi punti (se non tutti?) se avessi dato una soluzione del genere in gara. :roll: Ti elenco le mie obiezioni, sperando che ti siano d'aiuto:
  • $\circ$ Sarebbe piu' chiaro iniziare direttamente dal passo base dell'induzione: è ovvio, ma dove sono i casi $n \le 3$?
    $\circ$ Anche qui potrebbe essere ovvio, ma dove sono i casi $n=f_k$?
    $\circ$ A cosa serve la disuguaglianza $f_{k+1}<2f_k$? Da come l'hai scritta sembra per dire che $$f_k<n<f_{k+1}<2f_k \implies 0<x<f_k$$ E almeno a prima vista pare che hai sbagliato tutto, perchè per ipotesi induttiva la rappresentazione di $x$ potrebbe "includere" un addendo $f_{k-1}$, e una scrittura di $n$ come $f_k+f_{k-1}+\ldots$ non è ammessa!
    $\circ$ Ammesso che il correttore sia abbastanza buono da abbuonarti l'errore di sopra riguardo l'esistenza di una tale rappresentazione, hai completamente skippato la parte dell'unicità della stessa..
The only goal of science is the honor of the human spirit.

Avatar utente
aetwaf
Messaggi: 41
Iscritto il: 07 ott 2013, 17:54
Località: Torino

Re: Teorema di Zeckendorf

Messaggio da aetwaf » 26 dic 2013, 13:46

Jordan hai ragione, è un mio problema l'esposizione della soluzione. Comunque grazie per i consigli, in effeti la soluzione è da rivedere. Per $n\le 3$ rientriamo nel caso $n=f_i$, che è già una rappresentazione del tipo richiesto ed è unica perchè se lo scomponessimo otterremmo due termini della successione consecutivi ($f_{k-1}$ e $f_{k-2}$). Se poi cerco di scomporre questi otterrò ancora termini consecutivi. Per la disuguaglianza dovrei dire, poniamo $n=f_k+x$, $x<f_k$, allora potremo esprimere tutti i numeri di questo tipo come somma di $f_i$ per ipotesi. Ma poichè $f_{k+1}<2f_k$ allora la proprietà è verificata per $k+1$ perchè $x\le f_k-1$. Riguardo l'unicità, me l'ero perso, ma basta dire che se la rappresentazione è unica $\forall x$ allora lo sarà anche per $f_k+x$ poichè lo è per $f_k$. L'unico problema ora mi sembra dimostrare che non ci sono addendi $f_{k-1}$ ma per questo possiamo dire
Se a $f_k$ sommassimo $f_{k-1}$ otterremmo $f_{k+1}$ ma a noi, per il procedimento induttivo, basta dimostrarlo fino a $f_{k+1}-1$ perchè $f_{k+1}$ rientra nel caso $f_i$.
Dispongo di una meravigliosa dimostrazione di questo teorema che non può essera contenuta nel margine troppo stretto della pagina

Avatar utente
jordan
Messaggi: 3988
Iscritto il: 02 feb 2007, 21:19
Località: Pescara
Contatta:

Re: Teorema di Zeckendorf

Messaggio da jordan » 26 dic 2013, 14:52

aetwaf ha scritto:L'unico problema ora mi sembra dimostrare che non ci sono addendi $f_{k-1}$ ma per questo possiamo dire
Se a $f_k$ sommassimo $f_{k-1}$ otterremmo $f_{k+1}$ ma a noi, per il procedimento induttivo, basta dimostrarlo fino a $f_{k+1}-1$ perchè $f_{k+1}$ rientra nel caso $f_i$.
Esatto, la domanda "a che serve la disuguaglianza $x<f_k$?" aveva un senso: a te serve $x<f_{k-1}$, che è proprio quello che hai scritto qui sopra!
aetwaf ha scritto:Riguardo l'unicità, me l'ero perso, ma basta dire che se la rappresentazione è unica $\forall x$ allora lo sarà anche per $f_k+x$ poichè lo è per $f_k$.
Mi pare che ancora non ci siamo: te hai scritto "Mettiamo di rappresentare $n \in (f_k,f_{k+1})$ come $f_k+x$[etc.] allora una tale rappresentazione esiste". Bene, ma ancora non dimostri che questa somma non puo' partire da $f_t$ con $t\le k-1$, portando a una nuova rappresentazione ammissibile di $n$. Sei d'accordo?
The only goal of science is the honor of the human spirit.

Avatar utente
aetwaf
Messaggi: 41
Iscritto il: 07 ott 2013, 17:54
Località: Torino

Re: Teorema di Zeckendorf

Messaggio da aetwaf » 26 dic 2013, 15:22

Scusa ma non mi è chiara l'ultima obiezione, se io pongo $n=f_k+x$ e $x=f_{i_0}+f_{i_1}+\ldots+f_{i_n}$ con $f_{i_n}>f_{i_{n-1}}>\ldots >f_{i_0}$ senza termini consecutivi (e posso farlo per ipotesi) allora $f_k+x=f_k+f_{i_0}+f_{i_1}+\ldots+f_{i_n}$ con $f_{i_n}<f_{k-1}$ appunto perchè $x<f_{k-1}$. Quindi anche la rappresentazione di $f_k+x$ risponde alle richieste.
Dispongo di una meravigliosa dimostrazione di questo teorema che non può essera contenuta nel margine troppo stretto della pagina

Avatar utente
jordan
Messaggi: 3988
Iscritto il: 02 feb 2007, 21:19
Località: Pescara
Contatta:

Re: Teorema di Zeckendorf

Messaggio da jordan » 26 dic 2013, 15:27

aetwaf ha scritto:Quindi anche la rappresentazione di $f_k+x$ risponde alle richieste.
E va bene, qui non ci piove. Il problema nasce da: " chi si assicura che $n=f_k+x$ non possa essere scritto anche come, per esempio,
$$f_{k-2}+f_{i_1}+f_{i_2}+\ldots+f_{i_t}$$
con $i_1 \le k-4$ e $2\le i_j \le i_{j-1}-2$ per ogni $2\le j\le t$?"
The only goal of science is the honor of the human spirit.

Avatar utente
aetwaf
Messaggi: 41
Iscritto il: 07 ott 2013, 17:54
Località: Torino

Re: Teorema di Zeckendorf

Messaggio da aetwaf » 26 dic 2013, 15:45

jordan ha scritto:Il problema nasce da: " chi si assicura che $n=f_k+x$ non possa essere scritto anche come, per esempio,
$$f_{k-2}+f_{i_1}+f_{i_2}+\ldots+f_{i_t}$$
con $i_1 \le k-4$ e $2\le i_j \le i_{j-1}-2$ per ogni $2\le j\le t$?"
Sarebbe corretto dire che in questo caso avremmo che $f_{j_0}+f_{j_1}+\ldots +f_{j_t}=f_k+f_{i_0}+\ldots +f_{i_n}$ cioè $f_{j_{k_0}}+f_{j_{k_1}}+\ldots +f_{j_{k_m}}=f_k$ impossibile per ipotesi.
Dispongo di una meravigliosa dimostrazione di questo teorema che non può essera contenuta nel margine troppo stretto della pagina

Avatar utente
jordan
Messaggi: 3988
Iscritto il: 02 feb 2007, 21:19
Località: Pescara
Contatta:

Re: Teorema di Zeckendorf

Messaggio da jordan » 26 dic 2013, 16:10

aetwaf ha scritto:...avremmo che $f_{j_0}+f_{j_1}+\ldots +f_{j_t}=f_k+f_{i_0}+\ldots +f_{i_n}$ cioè $f_{j_{k_0}}+f_{j_{k_1}}+\ldots +f_{j_{k_m}}=f_k$ impossibile per ipotesi.
Ancora, no. L'equazione $f_{j_0}+f_{j_1}+\ldots +f_{j_t}=f_k+f_{i_0}+\ldots +f_{i_n}$ non implica $f_{j_{k_0}}+f_{j_{k_1}}+\ldots +f_{j_{k_m}}=f_k$ (almeno, non direttamente; da quanto è scritto sopra, e poi non è manco accennato perchè $f_k$ non puo' essere somma di fibonacci non consecutivi, se non $f_k$ stesso :? )
The only goal of science is the honor of the human spirit.

marconato
Messaggi: 34
Iscritto il: 13 mag 2013, 15:14

Generalizzazione al Teorema di Zeckendorf

Messaggio da marconato » 16 ago 2014, 23:47

Ciao a tutti :D, 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.

marconato
Messaggi: 34
Iscritto il: 13 mag 2013, 15:14

Re: Teorema di Zeckendorf

Messaggio da marconato » 17 ago 2014, 21:03

Ho scoperto che tale fatto prende il nome di Rappresentazione di Ostrowski :)

Avatar utente
jordan
Messaggi: 3988
Iscritto il: 02 feb 2007, 21:19
Località: Pescara
Contatta:

Re: Teorema di Zeckendorf

Messaggio da jordan » 24 ago 2014, 21:55

A quanto pare ne esistono molte di generalizzazioni. Questo mi era stato proposto anni fa per l'Oliforum Contest, prima che lo mettesse su ArXiv ;)
The only goal of science is the honor of the human spirit.

Triarii
Messaggi: 464
Iscritto il: 18 nov 2010, 21:14

Re: Teorema di Zeckendorf

Messaggio da Triarii » 31 ago 2014, 21:58

Wow fighissimo :)
Grazie ad entrambi per le notizie!
"We' Inge!"
LTE4LYF

Rispondi