Il Principio di induzione

(1)

Il Principio di induzione costituisce, a seconda dell’impostazione che si vuole dare, un as- sioma oppure un teorema dell’Aritmetica, ma `e uno strumento molto importante nei vari rami della Matematica. Queste pagine, tuttavia, non hanno alcuna pretesa nella direzione dei fondamenti della Matematica e riguardano piuttosto l’applicazione del principio. Per questo motivo semplicemente lo enunciamo, sorvolando cio`e su una sua eventuale dimo- strazione basata su altri assiomi. Diamo invece qualche semplice applicazione.

Principio di induzione. Sia {pn} una successione di proposizioni verificanti p₀ `e vera

(1)

per ogni n, p_n implica p_n+1. (2)

Allora tutte le proposizione della successione sono vere.

Prima variante. La proposizione pn è data solo per n ≥ 1 . In tal caso si sostituisce p₀ con p₁ in (1) e si può supporre n ≥ 1 nell’implicazione di (2) . Analogamente se p_n è data solo a partire da un altro valore iniziale di n .

Seconda variante. Ferma restando la (1) , la conclusione pu`o ancora essere dedotta se la (2) `e sostituita dalla condizione: per ogni n , ( p_k per k = 0, . . . , n ) implica p_n+1.

Ad esempio, nel caso n = 2 , l’implicazione `e “( p0 e p1 e p2) implica p3” anzich´e

“ p₂ implica p₃”. Tutto ci`o in rifermento al caso in cui le p_n sono date per ogni n ≥ 0 , ma potremmo anche qui apportare la prima variante.

Terza variante. La (1) `e sostituita da “ p0 e p1 sono vere”, mentre la condizione (2)

`

e sostituita da “per ogni n ≥ 1 , ( p_n−1 e p_n) implica p_n+1”.

Nota importante. Ogni applicazione del Principio di induzione (e analogamente per le sue varianti) corrisponde a eseguire le operazioni seguenti: a) si sceglie che cosa si vuole chiamare pn; b) si verifica la (1) ; c) si verifica la (2) . Si osservi che quest’ultima ha la forma classica di un teorema (dipendente da n ): l’ipotesi è pn e la tesi è pn+1 (per cui consigliamo di esplicitare sia pn sia pn+1, almeno finché non si è raggiunta una certa dimestichezza). Segnaliamo che, in questo contesto, pn è detta ipotesi di induzione.

Esercizio 1. Calcolare 1 + 2 + . . . + 2006 . Vi sono diverse possibilit`a. Una `e quella di Gauss: detta s la somma da calcolare, abbiamo

s = 1 + 2 + . . . + 2005 + 2006 s = 2006 + 2005 + . . . + 2 + 1 2s = 2007 + 2007 + . . . + 2007 + 2007

da cui 2s = 2007 · 2006 e s = 2007 · 2006/2 . L’altra possibilit`a `e quella di accatastare quadratini di lato unitario come segue: si costruisce una fila di 2006 quadratini giustapposti; su di questa si posa una analoga fila di 2005 quadratini giustapposti in modo che questi siano ordinatamente posti sopra i primi 2005 quadratini della fila precedente; si prosegue allo stesso modo con 2004 quadratini, eccetera, fino ad arrivare a una fila costituita da un solo quadratino. Risulta costruita una figura che, vista da lontano, appare

(2)

un triangolo rettangolo isoscele di cateto 2006 , ma che, in realtà, è costituita da un vero triangolo rettangolo isoscele avente i cateti lunghi 2006 e da 2006 triangolini simili al precedente, ma tutti di cateto unitario. La somma da calcolare, che è il numero complessivo dei quadratini, coincide con l’area della figura costruita, area che vale 2006²/2 + 2006 · 1²/2 . Naturalmente si ritrova il risultato precedente, ma presentato in un’altra forma.

Notiamo che le due vie considerate non si potrebbero percorrere nel caso dell’analogo problema di calcolare 1²+ 2²+ . . . + 2006². Ricalcoliamo allora la somma s di cui sopra usando l’induzione. A questo scopo `e essenziale generalizzare e cercare una formula per 1 + . . . + n con n intero positivo qualunque. Le tecniche viste sopra si applicherebbero anche al problema generale e fornirebbero

1 + . . . + n = n(n + 1)

2 .

Applichiamo allora il Principio di induzione (prima variante) scegliendo come p_n esattamente la formula da dimostrare. Il caso n = 1 `e banale. Assumiamo allora n ≥ 1 e pn

come ipotesi e deduciamo p_n+1 (l’inesperto espliciti sia p_n sia p_n+1 prima di proseguire).

Si ha (l’ipotesi di induzione `e usata nell’uguaglianza asteriscata) 1 + . . . + (n + 1) = 1 + . . . + n + (n + 1)=^∗ n(n + 1)

2 + n + 1 = (n + 1)(n + 2) 2

cio`e esattamente la proposizione p_n+1.

Ma si può fare di più: si può costruire la formula corretta senza conoscerla a priori.

Per`o bisogna almeno intuirne prima qualche aspetto. Ipotizziamo una formula del tipo 1 + . . . + n = P (n)

ove P (n) è un polinomio nell’indeterminata n . Siccome qualche semplice considerazione mostra che la somma deve essere compresa fra n²/2 e n², cerchiamo P (n) di secondo grado. Dunque P (n) = an²+ bn + c con certi coefficienti a, b, c . Cerchiamo di scrivere condizioni su a, b, c in modo che le condizioni date dal Principio di induzione siano soddisfatte. Il caso n = 1 conduce alla condizione 1 = a + b + c . L’implicazione che fa passare da n a n + 1 è sicuramente vera se è soddisfatta l’identità (rispetto a n )

P (n + 1) = P (n) + n + 1, cio`e

a(n + 1)²+ b(n + 1) + c = an²+ bn + c + (n + 1), cio`e an² + (2a + b)n + (a + b + c) = an²+ (b + 1)n + (c + 1) per garantire la quale basta imporre che a, b, c verifichino

a = a, 2a + b = b + 1, a + b + c = c + 1.

Riunendo tutte le condizioni imposte sui coefficienti troviamo un sistema, che è risolto da a = b = 1/2 e c = 0 . Con tale scelta, se si assume come proposizione pn la formula stessa, le condizioni (1) e (2) del Principio di induzione (in realtà quelle della variante) sono soddisfatte e il principio stesso assicura che la formula è vera per ogni n ≥ 1 .

Questa stessa tecnica si presta per trovare formule comode per le somme dei quadrati 1²+ . . . + n² o dei cubi, eccetera. La struttura da intuire è la seguente: nei due casi citati bisogna cercare polinomi nell’indeterminata n di gradi 3 e 4 rispettivamente. Detto ciò il procedimento è identico.

(3)

Esercizio 2. Determinare per quali interi positivi n si ha 3ⁿ · 2006 > 10ⁿ. L’idea è che, almeno per n abbastanza grande, valga la disuguaglianza opposta. Si cerca allora di dimostrare quest’ultima per induzione, assumendola come proposizione pn. L’implicazione pn ⇒ pn+1 è immediata e vale per ogni n . Basta allora cercare il valore di innesco: il primo dei valori di n per cui pn è vera (si trova n = 7 ). Quelli precedenti (dunque n = 1, . . . , 6 ) costituiscono la risposta al problema posto.

Esercizio 3. Dimostrare che

1 + x + . . . + xⁿ= 1 − xⁿ⁺¹ 1 − x

per ogni intero positivo n e per ogni numero reale x 6= 1 . Non ci sono difficoltà tecniche, ma concettuali. Se si assume come p_n la formula da dimostrare, non si ottiene una proposizione a causa della presenza di x . Le possibilità che rendono il discorso rigoroso sono due: nella prima si immagina di fissare x fin dall’inizio, per cui ciò che si vuole chiamare pn è effettivamente una proposizione. In tal caso pn e pn+1 si riferiscono allo stesso valore di x , quello che si immagina di aver fissato all’inizio. Nella seconda possibilità, invece, si “incorporano” le parole per ogni x 6= 1 in pn assumendo come pn la frase: per ogni x 6= 1 vale la formula da dimostrare.

Nel caso che stiamo trattando le due strade sono del tutto equivalenti, ma la cosa può essere diversa in altre situazioni. Se si adotta la seconda possibilità, infatti, la struttura logica dell’implicazione p_n ⇒ p_n+1 ha come ipotesi e tesi due frasi del tipo (qui n è da considerarsi fissato)

per ogni x a(x) e rispettivamente per ogni x b(x).

Ora, nel dimostrare la seconda si pu`o immaginare di fissare x (arbitrariamente, ben inteso), mentre l’ipotesi continua a contenere x come variabile, fatto che ci consente di applicare l’ipotesi stessa con tutti i valori di x che ci possono tornare comodi e non solo con quello che pensiamo di avere fissato nella tesi.

Esercizio 4. Sia P un poligono convesso. Dimostrare che P ha n(n − 3)/2 diagonali ove n è il numero dei lati. Anche in questo caso c’è un’altra variabile, il poligono, che però, ovviamente, non può essere fissato all’inizio, dato che in tal caso esso avrebbe un numero fissato di lati. Conviene allora riformulare il fatto da dimostrare come segue: per ogni n ≥ 3 (altrimenti non c’è il poligono) ogni poligono convesso di n lati ha n(n − 3)/2 diagonali. Scelta come p_n la frase “ogni. . . diagonali”, non ci sono difficoltà ad applicare il Principio di induzione: nel passaggio da n a n + 1 , fissato ad arbitrio un poligono convesso P con n + 1 lati, lo si decompone mediante una diagonale in un triangolo e in un poligono convesso P⁰, si controlla che P⁰ ha n lati, si applica l’ipotesi di induzione a P⁰ e si conclude facilmente.

Esercizio 5. Dimostrare che 1000 rette del piano comunque disposte, purch´e esse siano a due a due incidenti e tali che mai tre di esse passino per uno stesso punto, dividono il piano stesso in 500.501 regioni. Conviene cambiare e generalizzare la forma del problema:

trovare una formula per il numero rn delle regioni in cui n rette verificanti le condizioni

(4)

dette sopra dividono il piano. Usiamo il Principio di induzione seguendo pi`u o meno l’ultima strategia usata per la somma dei primi n numeri naturali. Chiaramente r1 = 2 . Supponiamo ora n ≥ 1 e cerchiamo una formula che leghi rn+1 a rn. Prendiamo dunque n + 1 rette nelle condizioni dette sopra e isoliamone una, che chiamiamo a , chiamando a1, . . . , an le altre n rette. Allora a taglia queste n rette in punti distinti, punti che originano su a due semirette e un certo numero di segmenti: se chiamiamo “parti” tali semirette e tali segmenti, queste parti sono n + 1 complessivamente e ciascuna di esse taglia in due ciascuna delle r_n regioni in cui il piano viene suddiviso dalle rette a₁, . . . , a_n. Abbiamo pertanto rn+1 = rn + n + 1 e, ipotizzando che rn si possa esprimere come polinomio di secondo grado nell’indeterminata n , possiamo procedere esattamente come nell’esercizio citato. Si ottiene rn = {n(n + 1)/2} + 1 .

Esercizio 6. Si ponga f (x) = x/(x + 1) per x reale positivo e si dimostri che f (f (. . . (x) . . .)) = x

2006 x + 1 per ogni x > 0

ove f e le parentesi aperte e chiuse sono scritte 2006 volte. Conviene dimostrare che f (f (. . . (x) . . .)) = x

nx + 1 per ogni x > 0

per n = 1, 2, . . . , ove ora f e le parentesi sono scritte n volte. La situazione è analoga a quella dell’Esercizio 3, ma qui è essenziale usare la seconda delle due vie là prospettate.

Usiamo dunque il Principio di induzione assumendo come pn esattamente la frase da dimostrare, con x “incorporato” nella frase stessa e non, invece, fissato all’inizio del discorso.

Introduciamo la notazione fⁿ(x) per denotare il primo membro della formula.

Il caso n = 1 coincide con la definizione di f (x) . Assumendo n ≥ 1 e la proposizione p_n come ipotesi di induzione, deduciamo la proposizione p_n+1. Sia dunque x > 0 . Abbiamo

fⁿ⁺¹(x) = fⁿ(f (x))

e possiamo usare l’ipotesi di induzione, che ci fornisce una formula per fⁿ(y) con y > 0 qualunque. Precisamente applichiamo l’ipotesi di induzione con y = f (x) (ove x è quello appena fissato) e non, si badi bene, con y = x . La cosa è lecita perché anche f (x) , come

`

e evidente, è positivo. Un calcolo immediato mostra che si ottiene x/{(n + 1)x + 1} . Esercizio 7. Sia a reale positivo tale che a + a⁻¹ sia intero. Dimostrare che, per ogni n intero positivo, è intero anche aⁿ+ a⁻ⁿ. Si può procedere per induzione, fissando a fin dall’inizio e assumendo come pn la proposizione: aⁿ+ a⁻ⁿ è intero. Ciò per n ≥ 1 . Il caso n = 1 corrisponde all’ipotesi. Vediamo il passaggio da n a n + 1 . Si ha

(aⁿ+ a⁻ⁿ)(a + a⁻¹) = aⁿ⁺¹+ a⁻⁽ⁿ⁺¹⁾ + aⁿ⁻¹+ a⁻⁽ⁿ⁻¹⁾ e si ricava

aⁿ⁺¹+ a⁻⁽ⁿ⁺¹⁾ = (aⁿ+ a⁻ⁿ)(a + a⁻¹) − {aⁿ⁻¹+ a⁻⁽ⁿ⁻¹⁾}.

Siccome interviene anche n − 1 oltre a n , occorre applicare una variante del Principio di induzione e quella comoda `e la terza. Per poterla applicare occorre dare senso a p0

(5)

(in modo che il ragionamento induttivo funzioni ancora) e verificarne la verità, ed è ovvio come si deve fare nel nostro caso: p0 significa “ a⁰+ a⁻⁰ è intero”, con l’usuale definizione a⁰ = 1 . Allora, grazie al fatto che le proprietà delle potenze valgono anche quando uno degli esponenti è 0 , il ragionamento induttivo resta corretto; d’altra parte p0 è vera.

Completiamo con qualche parola sui due termini successione e proposizione che com- paiono nell’enunciato del Principio di induzione, senza tuttavia pretendere di essere com- pletamente rigorosi. Ci concediamo dunque di appoggiarci ad altri termini non precisi.

Successioni. Con la parola “successione” si intende una legge (di natura qualunque) che a ogni numero naturale 0, 1, 2, . . . associa un ben determinato elemento di un certo insieme A . Si parla allora di successione di elementi di A .

Il concetto introdotto in tal modo generalizza quello di elenco (di elementi di A ) al caso in cui l’elenco sia costituito da infiniti termini nominati l’uno dopo l’altro. Abbiamo ad esempio successioni di numeri reali (quando A è l’insieme dei numeri reali), successioni di numeri naturali (quando A è l’insieme dei numeri naturali) e successioni di giorni della settimana (quando A è l’insieme dei giorni della settimana).

In riferimento ad esempio all’ultimo caso, dobbiamo pensare a un elenco infinito di parole scelte fra luned`ı,. . . , domenica, scritte l’una dopo l’altra, corrispondenti ordinatamente ai numeri naturali 0, 1, 2, eccetera. Si noti che, qualunque sia tale elenco, essendo solo 7 i giorni della settimana, deve accadere che a certe coppie di numeri naturali distinti la successione considerata fa corrispondere lo stesso giorno. In generale la definizione data non impone che a numeri naturali distinti corrispondano elementi distinti di A : nel caso estremo l’elemento di A `e sempre lo stesso qualunque sia il numero naturale condiderato.

Per le successioni si usa una notazione particolare. Fissata un lettera per denotare la successione che si vuole considerare, ad esempio, la lettera a , gli elementi che a fa corrispondere ai numeri naturali 0, 1, 2, . . . vengono denotati con i simboli a0, a1, a2, . . . . In alternativa alla scrittura a0, a1, a2, . . . , mediante la quale si immagina di elencare l’uno dopo l’altro gli elementi della successione (cioè gli elementi dell’insieme A considerato che la successione a fissata fa corrispondere ordinatamente ai numeri naturali 0, 1, 2, . . . ), si usa la scrittura concisa {a_n} , nella quale la variabile n (detta più spesso indice nel contesto delle successioni) può prendere un qualunque altro nome, ad esempio k . Naturalmente se, in contemporanea, si considera anche un’altra successione, questa verrà denotata con un simbolo diverso, ad esempio {bn} .

Il modo più semplice di assegnare una successione {a_n} è quello di dare una “formula” che fornisce il “valore” di an in funzione del numero naturale n (abbiamo messo le virgolette in quanto i due termini “formula” e “valore” devono assumere un senso lato, corrispondente alla generalità del termine “legge” usato nella definizione). Esempi di successioni di numeri reali sono allora dati dalle formule

a_n=p

n²+ 1 e b_n = n − 1 n + 1 mentre la “formula”

cn `e il pi`u piccolo dei numeri primi ≥ n²

(6)

definisce una successione di numeri naturali. Abbiamo ad esempio c₀ = c₁ = 2 e c₅ = 29 . Si noti che non sappiamo calcolare quanto vale cn se n = 10¹⁰⁰⁰: ci`o non toglie che tale valore cn sia un ben definito numero naturale.

Proposizioni. Con il termine “proposizione” si intende una frase di senso compiuto che

`

e vera oppure falsa, in termini oggettivi.

Esempi di proposizioni sono 2 ≤ 2 , 2 ≤ 3 (vere) e 2 > 3 (falsa), mentre x < 2 non lo è a causa della mancata precisazione di chi è x , che è una variabile (per fissare le idee nell’ambito dei numeri reali): questa frase diventa una proposizione ogni volta che si fissa il valore reale di x . Segnaliamo che frasi di questo tipo si chiamano predicati. Al contrario la frase ogni reale x è > 2 è una proposizione (falsa) anche se contiene la variabile x .

Altri esempi di proposizioni contenenti variabili sono i seguenti: per ogni reale x > 0 esiste un reale y > 0 tale che y < x (frase vera che si esprime anche dicendo che non esiste il pi`u piccolo reale positivo); esiste un numero naturale n tale che n ≤ m per ogni naturale m (frase vera che si esprime dicendo che esiste il pi`u piccolo dei numeri naturali, senza che 0 venga nominato); l’equazione x⁵+ x + 1 = 0 ha una e una sola soluzione reale.

Soffermiamoci un istante sull’ultima frase. Essa è vera (anche se non è ovvio che lo sia), ma questo non è importante. Importante è invece che essa è vera oppure falsa, anche se qualcuno chiamato a decidere non dovesse riuscirci.

Non è inutile una precisazione ulteriore. La frase x < x + 1 non è una proposizione (ma un predicato) anche se è vero che x < x + 1 qualunque sia x (diciamo, numero reale).

La differenza fra proposizioni contenenti la variabile x e predicati nella variabile x (e lo stesso discorso si ripete quando il nome della variabile è diverso oppure quando le variabili sono più di una) sta nel fatto che nei predicati x può assumere dei valori mentre nelle proposizioni no. Allora la frase appena considerata x < x + 1 è un predicato dato che x può assumere valori e si ottiene una proposizione (vera) qualunque sia il valore attribuito alla variabile. Al contrario la frase ogni reale x è > 2 menzionata sopra non è un predicato, perché non ha senso attribuire a x dei valori, a causa dell’ogni che la precede. Essa è una proposizione, come abbiamo già osservato.

Alcune frasi del linguaggio corrente non sono proposizioni: ad esempio nessuna domanda lo `e, dato che vera o falsa potr`a essere la risposta alla domanda, non la domanda stessa. Ma anche certe affermazioni (o negazioni) non sono proposizioni.

Ad esempio la frase Giovanni è alto è dichiarata vera da alcuni e falsa da altri (anche se si immagina che Giovanni sia una persona precisa e che il nome non si presti a equivoci), per cui la dichiarazione del fatto che essa sia vera o meno non è oggettiva.

Al contrario (sempre ritenendo Giovanni una persona precisa) la frase ieri Giovanni

`

e andato al mare `e una proposizione: in effetti essa `e vera o falsa, anche se qualcuno potrebbe non essere in grado di decidere (naturalmente occorre pensare di pronunciare la frase in un giorno preciso, altrimenti la parola “ieri” resterebbe ambigua).