Fibonacci e la ricorsione

Ricordate il problema che avevo postato il mese scorso, in cui si chiedeva di dimostrare che ogni numero intero può essere espresso in uno e un solo modo come somma di numeri di Fibonacci distinti e non consecutivi? Avevo dato una dimostrazione per induzione, ma avevo aggiunto che non avrei mai scelto di dimostrarlo in questo modo perché il tutto mi pareva inutilmente involuto. Adesso vi presento la “mia” soluzione, presentata in modo descrittivo seguendo il ragionamento che ho effetivamente fatto: come vedrete, è un misto di ricorsione e induzione.
Innanzitutto ho iniziato a scrivere i primi numeri che corrispondono alle ipotesi in “base Fibonacci”. Detto in altro modo, proprio come 2718 in base 10 equivale a 8*100 + 1*101 + 7*102 + 2*103, 2718 in base Fibonacci – che scriverò come 2718F – equivale a 8*F(1) + 1*F(2) + 7*F(3) + 2*F(4), cioè 8*1 + 1*2 + 7*3 + 2*5 = 41. I numeri esprimibili come somma di numeri di Fibonacci distinti e non consecutivi, se scritti in base Fibonacci, saranno composti da soli zero e uno, senza avere mai due uno consecutivi. Ho iniziato così a scrivere i primi di questi numeri, mettendo a fianco il valore corrispondente in base 10.
1F = 1
10F = 2
100F = 3
101F = 4
1000F = 5
1001F = 6
1010F = 7
10000F = 8
10001F = 9
10010F = 10
10100F = 11
10101F = 12
Mi sono subito accorto di una cosa fantastica: abbiamo scritto una e una sola volta tutti i numeri da 1 a 12! Visto che il numero successivo, 100000F, è già 13, posso immaginare che questo pattern continui all’infinito. A questo punto mi sono messo a cercare una formula ricorsiva per vedere quanti e quali sono i numeri di k cifre in base Fibonacci che soddisfino i vincoli. A parte i casi banali con k ≤ 2, un numero di k cifre inizia con il prefisso 10 e continua usando tutti i numeri con al più k-2 cifre (compreso 0). Il numero di questi numeri è Fk-2 (per ipotesi induttiva); visto che quelli con meno di k cifre sono Fk-1 (sempre per ipotesi induttiva), la loro somma è proprio Fk. Siamo così riusciti a costruire ricorsivamente tutti i numeri con al più k cifre in base Fibonacci che soddisfino i vincoli, e abbiamo scoperto che li abbiamo trovati tutti (e non ce ne sono di uguali, perché se mF e nF sono diversi, 10mF e 10nF sono anche diversi).
Il tutto è ricorsione oppure no? Qualche passaggio induttivo l’ho usato, e del resto il mio amico gnugnu dice che secondo lui ricorsione, induzione e discesa infinita – una tecnica di dimostrazione per assurdo che Fermat apprezzava molto ma che è davvero complicata da usare – sono poi la stessa cosa. Il mio pragmatismo è un po’ diverso: io vedo i vari metodi in maniera diversa, e trovo appunto una dimostrazione come questa essenzialmente più “visuale” di una prettamente induttiva. Inoltre in questo modo uno si convince del risultato, e riesce anche a capire come possa averlo trovato a chi ha proposto il teorema; sicuramente l’enunciato standard non ve l’avrebbe mai fatto venire in mente.
Voi che ne pensate?

Ultimo aggiornamento: 2010-04-08 07:00

7 pensieri su “Fibonacci e la ricorsione

  1. knulp

    C’è un typo dovuto a un taglia e incolla: 4321F non può essere quello che dici tu. Hai scritto 2718F.
    Comunque a me sembra un’altra dimostrazione per induzione. Da quello che ho capito, tu distingui la dimostrazione per ricorsione da quella per induzione semplicemente per il fatto che la ricorsione parte “dall’alto”, mentre l’induzione parte dal “basso”. Secondo me sono concetti perfettamente equivalenti, e di solito io ho sempre sentito parlare di dimostrazione per induzione o per “discesa infinita”, mai di dimostrazione per ricorsione.

  2. .mau.

    @knulp: il typo era dovuto all’aver cambiato all’ultimo momento l’esempio. Grazie della segnalazione.
    Quanto al tipo di dimostrazione, ammetto che “dimostrazione per ricorsione” forse ha poco senso, ed è meglio dire che si ottengono i vari numeri per ricorsione.
    Però la dimostrazione per discesa infinita è tutta un’altra cosa: giusto per dire, nonostante il nome è un procedimento finito, e poi è una dimostrazione non costruttiva per assurdo mentre la dimostrazione per induzione è una dimostrazione costruttiva diretta.

  3. Barbara

    Concordo con knulp: la dimostrazione per discesa infinita è una dimostrazione per induzione. Sul fatto che il nome possa essere mal scelto c’è poco da discutere, dopo tanti secoli di uso.
    Il numero N di casi da scrivere esplicitamente per convincersi della correttezza di una dimostrazione per induzione è certo un parametro (psicologicamente) interessante; ad esempio nel tuo caso N=12. Per la maggior parte dei matematici N è al più 2.
    Quanto alla tua preferenza per le dimostrazioni construttive, penso sia legata al fatto che fai l’informatico.

  4. .mau.

    io continuo a non vedere la somiglianza tra discesa infinita e ricorsione, come detto sopra, ma fa lo stesso.
    Per quanto riguarda il numero di casi da scrivere esplicitamente, mi pare che tu abbia dimenticato quanto avevo scritto la volta scorsa: in una dimostrazione per induzione tu sai cosa devi dimostrare. Qua non lo sapevo, e sfido un qualunque matematico a far partire la dimostrazione per induzione dai due casi 1F e 10F. (Probabilmente lo faranno con 100F e 101F, ma io sono sempre stato ipercauto)
    Infine si vede che tu non sei informatica: il concetto di dimostrazione con tecniche informatiche è ben diverso visto che deve comunque tener conto degli ordini di grandezza del numero di operazioni e degli eventuali errori di arrotondamento. La dimostrazione non costruttiva spesso è elegante, ma non è necessariamente la migliore…

  5. Barbara

    “si vede che non sei informatica”: questo è poco ma sicuro. Come si vede che tu non sei (più?) un matematico.

  6. .mau.

    » Come si vede che tu non sei (più?) un matematico.
    cancellerei la parentesi, visto che quello è stato il mio stile di dimostrazioni da decenni (chiedere al buon ddddottore, che essendo lui sì matematico ovviamente risolveva gli esercizi dal lato opposto di quello che sceglievo io)

  7. Anónimo

    Francamente trovo un po’ triste che nel terzo millennio si debba ancora assistere a discussioni (non so quanto scherzose) su chi sia più o meno matematico.
    Lasciamo pure da parte le tassonomie e le relazioni burocratiche tra logica, informatica e matematica. Ma per alcuni di noi la matematica discreta con le sue dimostrazioni prettamente costruttive e intrinsecamente algoritmiche è di fatto una seconda natura: e lo è da ben prima che si metta piede in università.
    Che la si chiami “inclinazione alla logica” (la logica è una teoria superiore dei reticoli, prima ancora che un modo di vedere le cose), “mentalità computazionale”, costruttivismo o che altro, un simile modo di pensare e di fare matematica è comunque valido e dotato di pari dignità degli altri. Anche chi non ama o non conosce le scuole di pensiero in filosofia della matematica strettamente connesse con costruttivismo, fallibilismo alla Lakatos, pragmatismo… non può comunque più avere dubbi dopo la grandiosa vita e l’opera di Gian-Carlo Rota, che di fatto ha “sdoganato” la matematica discreta e tutte le sue propaggini, dalla combinatorica alla teoria elementare del numero, in un ambiente certamente ancora troppo orientato alla modellistica continua e alla fisica matematica.
    Continuo e discreto, come tecniche ma anche come mentalità, sono paragonabili a diverse classi di strumenti: a fiato, a corda… ben pochi “strumentisti” possono eccellere in tutto (penso ad esempio a Von Neumann), eppure un’orchestra minimamente decente ha bisogno degli uni e degli altri – e sarebbe terribilmente incompleta in caso contrario.
    Just my 2 cents… :)

I commenti sono chiusi.