Giocando coi numeri di Fibonacci

[spugna]

Siano $(F_n)_(n \in NN)$ i numeri di Fibonacci, con $F_1=F_2=1$.

1) Dimostrare che per ogni $m$ intero positivo esiste un'unica successione $1<n_1<n_2<...<n_k$ di interi positivi a due a due non consecutivi tali che $m=\sum_{i=1}^k F_(n_i)$.

2) Sia $p_m$ la probabilità che $1$ compaia nella decomposizione di un intero positivo non superiore a $m$: si calcoli $lim_(m -> +oo) p_m$.

[dan95]

Esistenza...

Testo nascosto, fai click qui per vederlo

Procediamo per induzione su $F_{n}$, cioè affermiamo che tutti numeri interi positivi $m \leq F_{n}$ sono esprimibili in quel modo e mostriamo che lo sono anche i numeri interi positivi minori di $F_{n+1}$. Ora per la relazione $F_{n+1}=F_{n}+F_{n-1}$ ogni numero intero $F_{n} < m < F_{n+1}$ è esprimibile come $F_n+k$ dove $k < F_{n-1}$ che per ipotesi induttiva è esprimibile in quel modo, questo significa che anche tutti gli interi positivi minori di $F_{n+1}$ sono esprimibili in quel modo.

[spugna]

Ok, manca l'unicità!

[dan95]

Unicità...

Testo nascosto, fai click qui per vederlo

Chiamiamo scomposizione additiva di Fibonacci la somma di termini di Fibonacci con la proprietà richiesta.

Sia $m$ il più piccolo intero tale che la scomposizione additiva di Fibonacci non sia unica, cioè

$m=\sum_{i=1}^{k} F_{n_i}^{(1)}=\sum_{i=1}^{h} F_{n_i}^{(2)}$

Ora $F_{n_1}^{(1)} > F_{n_1}^{(2)} $ se fossero uguali allora si andrebbe contro la minimalità di $m$. Quindi l'intero $F_{n_1}^{(1)} -F_{n_1}^{(2)}$ è minore di $m$ e in quanto tale ammette un'unica scomposizione additiva di Fibonacci

$F_{n_1}^{(1)} -F_{n_1}^{(2)}=\sum_{i=1}^{r} F_{m_i}$

In particolare si ha

$m'=\sum_{i=2}^{k} F_{n_i}^{(1)}+\sum_{i=1}^{r} F_{m_i}=\sum_{i=2}^{h} F_{n_i}^{(2)}$

Notiamo che $m'$ ammette due scomposizioni additive di Fibonacci differenti¹, d'altra parte $m>\sum_{i=2}^{h} F_{n_i}^{(2)}=m'$, assurdo.

---

Note

1. Ogni addendo è tale che $F_{m_i} <F_{n_1}^{(1)}< F_{n_2}^{(1)}$ quindi non vi sono termini di Fibonacci consecutivi. ↑

[spugna]

Bella! Si poteva fare anche così:

Testo nascosto, fai click qui per vederlo

Sempre per induzione: dato $m$, prendo il più grande $F_k <= m$ e dimostro che $F_k$ deve comparire nella decomposizione di $m$ (quindi si conclude immediatamente se $m=F_k$, altrimenti si usa l'ipotesi induttiva su $m-F_k$): se non si usa $F_k$, la massima somma che si può ottenere è $F_(k-1)+F_(k-3)+...=F_k-1$, che è strettamente minore di $m$.

Hint per il punto 2:

Testo nascosto, fai click qui per vederlo

Chi è $p_m$ se $m=F_k$? Sapendo questo, come si può calcolare ricorsivamente $p_m$ per $m$ generico?