Leggendo quanto ho scritto sull’induzione, Gnugnu mi ha scritto, suggerendomi un teorema che si può dimostrare con l’induzione forte: ogni intero può essere scritto in un unico modo come somma di numeri di Fibonacci distinti e non consecutivi. Per chi non se lo ricordasse, i numeri di Fibonacci sono definiti così: F₁ = F₂ = 1, e poi F_n+1 = F_n + F_n-1. In questo caso, però, i primi due numeri di Fibonacci non sono 1 e 1 ma 1 e 2, in modo che tutti i numeri siano distinti. Se volete provare a dimostrare il teorema, smettete di leggere ora! Se invece della dimostrazione non ve ne può importare nulla, saltate i due paragrafi seguenti che sono sì semplici, ma anche piuttosto noiosi.
Per dimostrare che una cosa si può fare in un solo modo, in genere si inizia a domostrare che la si può fare, e poi si fa vedere che se la si fa in due modi questi sono in realtà lo stesso. Vediamo allora innanzitutto che ogni numero può essere scritto come somma di numeri di Fibonacci distinti e non consecutivi. I casi 1, 2 e 3 sono banali: la “somma” è il singolo numero stesso. Andiamo avanti, e prendiamo un n qualunque. Sia F_k=f il più grande numero di Fibonacci minore o uguale a n. Se f=n siamo a posto; altrimenti sia d=n–f. Sicuramente d<f, visto che tranne nel caso di 1 e 2 ciascun numero di Fibonacci è minore del doppio del precedente; cerchiamo ora il più grande numero di Fibonacci minore o uguale a d. Tale numero non può essere F_k-1, perché altrimenti se n ≥ F_k+F_k-1 allora è maggiore o uguale a F_k+1, contro la nostra ipotesi. Ma d è esprimibile come somma di numeri di Fibonacci distinti e non consecutivi per ipotesi induttiva, quindi siamo a posto per quanto riguarda la prima parte.
E per la seconda? Beh, prendiamo il più piccolo numero n esprimibile in due modi diversi come somma di numeri di Fibonacci distinti e non consecutivi. Il più grande F_k nello sviluppo dei due numeri deve essere per forza diverso: altrimenti anche n-F_k sarebbe esprimibile in due modi diversi, e quindi n non sarebbe il più piccolo. A questo punto ci occorre un lemma che mostri come – per quanto grande possa essere un numero come da ipotesi il cui sviluppo abbia come termine maggiore F_k – sarà sempre strettamente minore di F_k+1. Di nuovo, possiamo usare l’induzione. 1, 2, 3 non danno problemi perché il loro sviluppo contiene un solo numero. Per un k generico, un numero m il cui sviluppo abbia come termine maggiore F_k avrà al più come secondo termine F_k-2; quindi per ipotesi induttiva m – F_k < F_k-1 da cui m < F_k + F_k-1 = F_k+1, come volevasi dimostrare.
Dal lemma otteniamo così che non è nemmeno possibile che i due modi diversi per esprimere n abbiano come maggior numero di Fibonacci nel loro sviluppo due numeri diversi, e quindi la nostra tesi è ottenuta.
Detto tutto questo, e dando il bentornato a chi non ha avuto voglia di infilarsi in quei conti che sembravano essere infiniti, aggiungo che se io dovessi presentare una dimostrazione di questo teorema la farei in maniera completamente diversa e, almeno a mio parere, molto più intuitiva. Però prima di farla mi tocca fare qualche altro post…