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*10⁰ + 1*10¹ + 7*10² + 2*10³, 2718 in base Fibonacci – che scriverò come 2718_F – 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.
1_F = 1
10_F = 2
100_F = 3
101_F = 4
1000_F = 5
1001_F = 6
1010_F = 7
10000_F = 8
10001_F = 9
10010_F = 10
10100_F = 11
10101_F = 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, 100000_F, è 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 è F_k-2 (per ipotesi induttiva); visto che quelli con meno di k cifre sono F_k-1 (sempre per ipotesi induttiva), la loro somma è proprio F_k. 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 m_F e n_F sono diversi, 10m_F e 10n_F 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

ricorsione, s.f.: vedi ricorsione

L’induzione, di cui ho parlato poco tempo fa, è una brutta bestia: non tanto per la complessità del concetto, quanto perché il modo con cui si impiega generalmente l’induzione è piuttosto astratto. Le dimostrazioni per induzione assomigliano spesso a un gioco di prestigio algebrico, con un po’ di operazioni formali. Insomma, qualcosa che funziona sì, ma non ci dà informazioni su cosa sta effettivamente dietro.
La cosa buffa è che però è relativamente semplice trovare spiegazioni sull’induzione, ma almeno per i matematici non ci sono così tante informazioni su un modo in un certo senso simile per risolvere i problemi matematici: la ricorsione. La mia sensazione è che la ricorsione era sempre stata usata dai matematici del passato, ma veniva considerata una tecnica di serie B e quindi snobbata nelle dimostrazioni “ufficiali”. Poi è arrivata l’informatica, dove la ricorsione è parecchio usata; di nuovo però i matematici pensano che una cosa usata dagli informatici non è poi così importante… Ma lasciamo perdere queste disquisizioni, e vediamo come funziona la ricorsione.
Tecnicamente la ricorsione consiste nel risolvere un problema P con dati in ingresso D riconducendosi alla risoluzione del problema P con dati in ingresso D’, dove i dati D’ sono “più semplici” dei dati D. La frasetta magica “ricondursi al caso precedente” ricorre spesso nelle barzellette create dai fisici per prendere in giro i matematici; ma in questo caso la cosa è piuttosto diversa, e molto più seria. Ecco l’esempio canonico di ricorsione, tanto per mettere le cose più in chiaro: il calcolo del fattoriale.
Come probabilmente ricordate, il fattoriale di un numero intero positivo n, indicato con n!, è il prodotto dei numeri da 1 a n. Per convenzione, 0! e 1! sono uguali a 1. Per calcolare n! si può appunto fare il prodotto dei numeri da 1 a n, ma si può anche operare in altro modo. Un informatico per esempio scriverebbe un programma la cui parte principale dice più o meno così: “Per calcolare la funzione “fattoriale di n“, chiamo la funzione “fattoriale di n-1″ e moltiplico il risultato per n.” Chi non è abituato a queste cose fa un balzo sulla sedia: “Ma come fa questo qua a scrivere una cosa del genere? Com’è possibile definire una funzione per mezzo di sé stessa? Non si sovrappongono i pezzi?” Per quanto riguarda la struttura informatica, vi posso assicurare che non ci sono problemi: quello che viene richiamato non è il programma inteso come archetipo ma una sua istanza, insomma un suo clone. Il punto chiave è che dobbiamo essere certi che il procedimento non si espenda all’infinito, oppure che a un certo punto si ritorni al punto di partenza ottenendo così un circolo vizioso. Ma per fortuna questo non è il caso: il numero di cui si deve calcolare il fattoriale continua a ridursi, e prima o poi diventerà 1 (beh, ammesso che l’input sia stato un numero intero positivo. Ma quello del validare i dati in ingresso è un altro tipo di problema: qui si fa matematica, non informatica). Ma noi sappiamo quanto vale il fattoriale di 1! (per la cronaca, quest’ultimo è un punto esclamativo, non il simbolo di fattoriale), cioè 1. In definitiva, basta aggiungere il caso particolare; “Per calcolare la funzione “fattoriale di n“, verifico se n=1; in caso affermativo il risultato è 1, altrimenti, ecc. ecc.”.
Notata la differenza con l’induzione? Lì partivamo da 1 e salivamo fino all’infinito, grazie al quinto postulato di Peano; qui partiamo da un numero qualunque e scendiamo fino a 1. C’è però un altro punto che in genere viene trascurato. L’induzione parte da una formula chiusa, una cioè dove basta infilare il numero e si ottiene il risultato; con la ricorsione non c’è nulla del genere, e anzi trovare una formula chiusa a partire da quella ricorsiva non è sempre così semplice. Tanto per fare un esempio pratico, prendiamo i numeri di Fibonacci. Come ricordate, la loro definizione è ricorsiva: F₁ = F₂ = 1, e F_n+1 = F_n + F_n-1. È anche possibile avere una formula esplicita per l’n-simo numero di Fibonacci:

dove φ₁ è (1+√5)/2 e φ₂ è (1-√5)/2. Semplice, no? Vero che ce l’avevate sulla punta della lingua? D’accordo, questo è forse un caso limite: ma in genere ci vuole comunque una certa arte per trovare la formula chiusa corrispondente a una formula ricorsiva.
Nonostante tutto, però, la ricorsione almeno a mio parere è un modo più naturale per trovare la soluzione di tutta una classe di problemi, e quindi dovrebbe essere sempre pronta nella borsa degli attrezzi di un matematico.

Ultimo aggiornamento: 2010-04-01 11:43

Non so quanto sia leggera questa matematica qua; diciamo però che la soluzione, quando ve la dicono, è facile.
Come forse ricordate, un polinomio di grado n può essere determinato univocamente se conoscete il suo valore in n+1 punti. Supponiamo però che ci venga detto che il nostro polinomio P sia speciale: i suoi coefficienti sono tutti interi non negativi. In questo caso è concepibile che si possa determinare il polinomio conoscendo un numero minore di valori. Se ci è consentito di scegliere opportunamente per quali numeri x (algebrici) ci venga detto qual è il valore di P(x), quanti ce ne serviranno?
(l’ho visto da God Plays Dice, dove c’è anche la soluzione…)

Ultimo aggiornamento: 2010-03-17 16:22

Vi siete ricordati ieri di festeggiare il Giorno Pi Greco? No? Male. Adesso per fare penitenza andate da Popinga e leggetevi il Carnevale della Matematica – edizione numero 23!

Ultimo aggiornamento: 2010-03-15 11:54

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…

Ultimo aggiornamento: 2010-03-11 07:00

Qualche giorno fa ho
iniziato a parlare dell’induzione matematica.
Dopo aver parlato di induzione solo dal punto di vista teorico, vediamo un esempio esplicito di dimostrazione per induzione, mostrando che la somma dei numeri dispari da 1 a 2n+1 è uguale a (n+1)². Il passo iniziale è semplicissimo: quando n=0, la somma dei numeri da 1 a 1 fa 1, che è esattamente il quadrato di 1. Più facile vederlo che spiegarlo. Immaginiamo ora che l’ipotesi valga fino a un certo n, e proviamo a vedere cosa succede con n+1. La somma dei numeri dispari da 1 a 2(n+1)+1, cioè da 1 a 2n+3, è pari a 2n+3 più la somma dei numeri dispari da 1 a 2n+1, che per ipotesi induttiva è (n+1)², cioè n²+2n+1. Facendo la somma otteniamo n²+4n+4, che guarda caso vale proprio (n+2)². Fine della dimostrazione: con un solo caso generale abbiamo dimostrato l’ipotesi per gli infiniti casi particolari.
Tutto questo è bellissimo, ma siete stati attenti c’è qualcosa che non va.Il guaio non è nella dimostrazione, che non è poi così difficile: si fanno giusto un po’ di giochetti formali coi numeri e si arriva al risultato, e questo capita spesso quando si usa l’induzione, tanto che a volte mi chiedo se nessuno abbia mai fatto un sistema di intelligenza artificiale che sappia risolvere problemi per induzione. Ma come facevamo a sapere che il risultato era proprio quello indicato nel teorema? Chi ce l’ha suggerito? Insomma, l’induzione è un bieco trucco; riusciamo solo a dimostrare qualcosa che conosciamo già. La cosa è spiazzante soprattutto per chi è rimasto alla concezione che purtroppo viene insegnata a scuola, vale a dire che la matematica sia qualcosa di perfettamente lucidato, con i teoremi che sono così perché non potrebbero essere diversi, e che scendono dall’alto come novelli deus ex machina. No, non è affatto così. La matematica avanza per tentativi ed errori, ed è solo in un secondo tempo che ci si affretta a togliere tutte le impalcature e lasciare solo il risultato finale per l’ammirazione del popolo. Per quanto riguarda l’induzione, quello che succede di solito è che il matematico fa un’ipotesi su quale possa essere il risultato, e poi controlla se ha ragione; proprio come un meccanico che ascolta il rumore di un motore e fa una diagnosi. Il vantaggio del matematico, se volete, è che non si sporca le mani… a meno che la penna con cui sta scrivendo non perda inchiostro!
Do solo un accenno a un’estensione del principio di induzione, che potete tranquillamente lasciar che è un parallelo della teoria cantoriana degli infiniti. L’induzione classica si applica all’infinito numerabile, ma si può anche parlare di induzione transfinita; in questo caso su dice che “se una proprietà P vale per zero, e quando vale per tutti gli ordinali minori di ψ, allora P vale anche per ψ, allora vale per tutti gli ordinali.” Come in tutte queste eteree proprietà logiche, l’induzione transfinita è indipendente da quella standard, nel senso che uno può accettarla oppure no e il resto della matematica va avanti tranquillo; se lo si accetta, però, l’induzione standard ci viene data gratis. Un esempio a riguardo è il teorema di Goodstein, che non è decidibile usando gli assiomi di Peano ma è vero se si ammette l’induzione transfinita.
Termino con un paradosso matematico basato sull’induzione, che “dimostra” come tutti i cavalli sono dello stesso colore. Prendiamo un insieme di n cavalli. Nel caso n=1 la tesi è banalmente vera. Per un n qualunque, numeriamo i cavalli e togliamo il numero 1. Rimangono n-1 cavalli, che per ipotesi induttiva sono tutti dello stesso colore. Ma se rimettiamo il numero 1 e ne togliamo un altro, abbiamo di nuovo n-1 cavalli, che sono sempre dello stesso colore di prima. A questo punto, visto che i due insiemi hanno un’intersezione in comune, è chiaro che tutti e n i cavalli sono dello stesso colore. O no?

Ultimo aggiornamento: 2010-03-08 07:00

Lo sappiamo tutti: Sherlock Holmes è il principe della deduzione. Almeno, ci è sempre stato venduto in questo modo, anche se poi a guardar bene anche l’investigatore dal naso adunco – o meglio Arthur Conan Doyle – spesso barava e tirava fuori dal cappello alcune informazioni che non erano state date al lettore, oppure giungeva a conclusioni non certe ma altamente probabili. I filosofi affermano che il metodo holmesiano si dovrebbe più correttamente definire abduzione, come lo pseudosillogismo che da una premessa maggiore corretta (“tutti gli uomini sono mortali”) e una minore molto probabile (“Giulio Andreotti dovrebbe essere un uomo”) conclude con una conseguenza molto probabile (“si presume che prima o poi Andreotti morirà”). A proposito di abduzione, attenti ai falsi amici! In inglese “abduction” è il rapimento, soprattutto se da parte di alieni… ma non divaghiamo.
Il vero regno del campo deduttivo è naturalmente la matematica, dove si inizia a mettere i paletti (gli assiomi e i postulati) e da lì si va man mano avanti a dedurre i vari teoremi, come abbiamo tutti imparato quando abbiamo studiato geometria. Se ci pensarte un po’, però, la deduzione è un percorso in un certo qual senso sterile; tutto quello che deduciamo, per quanto possa sembrare incredibile – avete presente il cosiddetto teorema di Napoleone? Se si disegnano le trisettrici di un triangolo qualunque, queste si incontrano a due a due nei vertici di un triangolo equilatero – era già presente in nuce negli assiomi e postulati iniziali. Non abbiamo inventato nulla, ma solo scoperto quello che c’era già fin dall’inizio. Ripensandoci, non è affatto strano che la gran maggioranza dei matematici sia fondamentalmente della scuola platonista; a furia di trarre conseguenze logiche di quello che hai, ti inizia a sorgere il dubbio che gli enti matematici sono tutti lì da qualche parte, un po’ come in Flatterlandia.
Eppure anche in matematica c’è un modo per tirare fuori qualcosa di nuovo: l’induzione (“induzione matematica” se si vuole fare i precisini, ma in genere l’aggettivo si omette perché è chiaro che si sta facendo matematica). Anche nel mondo di tutti i giorni si parla di “procedimento induttivo” , ma in realtà è tutta un’altra cosa; si vedono alcune correlazioni, per esempio che quando spunta il sole settembrino dopo un temporale si trovano molti funghi, e si stabilisce una legge generale, che il sole dopo la pioggia faccia crescere i funghi. Tale legge può però essere vera o falsa, ed è solo un risultato empirico che fa rabbrividire un qualunque matematico se applicato alla propria scienza. Qui si tratta di qualcosa di completamente diverso.
La formalizzazione dell’induzione matematica è stata data da Giuseppe Peano nella sua definizione dei numeri naturali. Gli assiomi di Peano sono cinque, come i postulati della geometria euclidea; l’induzione è l’ultimo e il più complicato da spiegare, proprio come in geometria euclidea. Dopo avere stabilito per legge che 0 è un numero, che esiste una funzione S (“successore”) tale che se n è un numero anche S(n) è un numero (“per quanto grande sia un numero, posso sommarci uno”), che non esiste un numero x tale che S(x) = 0 (“zero è il primo numero”), e che se ci sono due numeri m e n per cui S(m) = S(n) allora m = n (“posso mettere tutti i numeri in fila”), il quinto assioma dice che “Se una proprietà P vale per 0 – cioè P(0) è vera – e sappiamo inoltre che se P vale per n allora vale anche per S(n), allora P vale per tutti i numeri naturali”. Per amor di precisione, il quinto assioma di Peano afferma che non ci sono altri numeri naturali al di fuori di questi, ma è un punto secondario. In un certo senso, questo quinto assioma ricorda il postulato delle parallele: molto più complicato degli altri, uno si chiede se è proprio necessario e non si possa invece farne a meno. La risposta è però molto diversa, come vedremo subito.
La cosa che dovrebbe subito saltare alla vista è che il quinto assioma di Peano, a differenza degli altri, tratta con l’infinito. Gli altri assiomi lavorano tutti con un numero o due; anche dire “se esiste il numero un fantastiliardo, allora esiste anche un fantastiliardo e uno” è una proprietà locale. Col quinto assioma, invece, dobbiamo prendere tutti i numeri contemporaneamente. L’immagine che io ho in mente è quella di un numero infinito di tessere del domino messe ritte in piedi una vicina all’altra. Forse avete visto quei video in cui ci si limita a dare un colpetto alla prima tessera, che cadendo tocca la seconda che a sua volta cade colpendo la terza… finché tutta la costruzione finisce giù per terra. Ecco, l’induzione è esattamente la stessa cosa, solo che le tessere sono infinite. Per la cronaca, esistono due definizioni di induzione: nell’induzione forte, invece che solo per n, la proprietà P deve valere per tutti i numeri inferiori o uguali a n, perché valga anche per n+1. Ma in realtà le due formulazioni sono equivalenti, e si può scegliere l’una o l’altra a seconda della comodità. Inoltre non è affatto detto che l’ipotesi induttiva debba partire necessariamente da 0; la proprietà può essere valida da un certo numero k, e ovviamente il risultato sarà valido per ogni intero maggiore o uguale a k. Così, se vogliamo dimostrare per induzione che la somma degli angoli di un poligono convesso di n lati è pari a n-2 angoli piatti, partiremo dal triangolo e non certo da un ipotetico poligono con zero lati!
[non è tutto qua, vai alla seconda parte]

Ultimo aggiornamento: 2010-03-05 07:00

Lo so che state scambiandovi Valentines, ma mi preme ricordarvi che i Rudi Matematici (senz’acca) hanno (con l’acca) postato la nuova edizione del Carnevale della Matematica, e che la prossima sarà presso Popinga.

Ultimo aggiornamento: 2010-02-14 16:54