Principio di induzione

Nell'ambito delle dimostrazioni matematiche, uno dei principali metodi utilizzati è il principio di induzione. In questa lezione vedremo cos'è, quando usarlo e come fare le dimostrazioni con il principio di induzione.

 

Diffidate da chi vi dice che le dimostrazioni per induzione sono una stupidaggine. E' vero: una volta acquisito e fatto proprio il metodo è uno fra i "più semplici" perché per certi versi è un po' meccanico (fra poco vedremo uno schemino da poter seguire), ma all'inizio è un po' difficile da capire e in questa lezione cercherò proprio di aiutarvi in tal senso.

 

Quando usare il principio di induzione

 

Il principio di induzione si utilizza quando è richiesta la dimostrazione di una proprietà, di un teorema, di una proposizione che vale per i numeri naturali. Per farla breve quando vi trovate di fronte ad un enunciato del genere:

 

"Dimostrare che per ogni n\in \mathbb{N} vale Pincopalla."

 

allora nel 99% dei casi si utilizzerà il principio di induzione.

 

Cosa dice il principio di induzione

 

Abbiamo appena detto che il principio di induzione si utilizza quando vogliamo dimostrare enunciati del tipo: "Dimostrare che per ogni n\in \mathbb{N} vale una certa proprietà P" (il nostro Pincopalla di poco fa).

 

Esso afferma che:

 

(1) se P è vera per n=0, cioè P(0) è vera;

 

(2) se P è vera per n allora P è vera per n+1, cioè P(n) vera implica P(n+1) vera;

 

allora P è vera per tutti gli n \in \mathbb{N}.

 

Il punto (1) si dice base di induzione.

 

Il punto (2) si dice passo induttivo e P(n) è detta ipotesi induttiva.

 

 


 

 

Scommetto che i meno esperti avranno capito poco o niente...Non scoraggiatevi! Fra poco risulterà tutto più chiaro! Continuate quindi a leggere il seguito...

 

Principio di induzione per principianti

 

Distacchiamoci dal formalismo matematico, anzi dimentichiamo per un momento che stiamo facendo Matematica, e supponiamo di aver costruito un robot privo di intelligenza ma che esegue tutti i nostri ordini vocali.

 

A tale robot vogliamo far costruire, con i mattoncini, una casa di due piani.

 

Gli diremo:

 

- costruisci il piano terra assemblando sei pezzi: uno per il pavimento, quattro per i muri laterali ed uno per il solaio;

 

- partendo dal solaio del piano terra assembla altri sei pezzi: uno per il pavimento, quattro per i muri laterali ed uno per il solaio;

 

- terminato: casa a due piani costruita.

 

Supponiamo ora di voler far costruire al robot un palazzo di dieci, cento, mille.... infiniti piani. Potremmo metterci, come fatto prima, a spiegargli come costruire il palazzo piano dopo piano impiegandoci però tutta la vita Surprised oppure potremmo:

 

- spiegargli come costruire il piano terra;

 

- dirgli come costruire un piano qualsiasi a partire dal precedente.

 

A questo punto il nostro lavoro è terminato. Infatti il robot sapendo costruire il piano terra e qualsiasi altro piano a partire dal precedente saprà portare a termine il palazzo!

 

Se questo (stupido) esempio vi è chiaro fra poco vi risulterà tale anche il principio di induzione!

 

Ora pensate:

 

- al palazzo (ad infiniti piani) da costruire come alla nostra proposizione P da verificare per ogni n \in \mathbb{N};

 

- alla costruzione del piano terra come alla "base di induzione" cioè alla verifica che P(0) sia vera;

 

- al "piano precedente" come all'ipotesi induttiva P(n);

 

- al piano da costruire a partire dal precedente come alla verifica di P(n+1).

 

Questa è la logica che regola il principio di induzione. Facile no? Laughing

 

Come usare il principio di induzione

 

Ora torniamo alla nostra cara Matematica, e vediamo uno schemino utile da utilizzare quando vorrete dimostrare una data proprietà per induzione.

 

Supponiamo di avere una proprietà P(n) da dover dimostrare per ogni n \in \mathbb{N} o più in generale per ogni n \geq k con k=0,1,2,3,....

 

Procederemo in questo modo...

 

(1) Base di induzione

 

Si sostituisce il valore iniziale k all'interno della proprietà e si verifica che si è ottenuta un'espressione vera.

 

(2) Passo induttivo

 

(2a) Si suppone che sia vera P(n) (ipotesi induttiva).

 

(2b) Si va a sostituire n+1 al posto di n in P(n) ottenendo P(n+1) e si dimostra che anche P(n+1) è vera. Come?

 

Una volta ricavata P(n+1) con qualche passaggio algebrico (che può essere più o meno semplice) ci si deve ricondurre a scrivere P(n+1)=P(n) più, meno, per, diviso "qualcosa".

 

A questo punto scatta l'ipotesi induttiva e vado a sostituire al posto di P(n) la sua espressione e faccio i vari conticini che mi si presentano.

 

Se tutto è andato per il verso giusto dovrei aver ottenuto l'espressione di P(n+1) ottenuta al punto (2b).

 

Fine! Grazie al principio di induzione posso infatti affermare che la mia proprietà vale per ogni n\geq k.

 

Esempio di dimostrazione con il principio di induzione

 

Tenendo bene a mente questo schema andiamo a vedere un esempio: vogliamo dimostrare che per ogni n\geq 1 la somma S(n) dei primi n numeri naturali è S(n)=\frac{n(n+1)}{2}.

 

Siamo di fronte ad una proprietà che deve valere per ogni numero naturale maggiore o uguale ad uno. Utilizziamo quindi il principio di induzione.

 

(1) Base di induzione: verifichiamo che la nostra proprietà vale per il valore iniziale che in questo caso è k=1

 

Andiamo quindi a sostituire 1 al posto di n all'interno della nostra proprietà ottenendo:

 

S(1)=\frac{1(1+1)}{2}=1

 

che è ovviamente vera in quanto "la somma dei primi uno numeri naturali è uno" .

 

(2) Passo induttivo: supponiamo che sia vera la nostra proprietà per n, ovvero supponiamo che sia vero:

 

S(n)=\frac{n(n+1)}{2} [ipotesi induttiva]

 

e proviamo che l'ipotesi induttiva rende vera la nostra proprietà per n+1. Ricaviamo esplicitamente tale proprietà andando a sostiuire n+1 al posto di n ottenendo:

 

(\spadesuit)\ \ \ S(n+1)=\frac{(n+1)(n+1+1)}{2}=\frac{(n+1)(n+2)}{2}=\frac{n^2+3n+2}{2}

 

che è quello che dobbiamo dimostrare.

 

Fin'ora (e sarà sempre così) è stato tutto meccanico. Questo è il punto più difficile. Cercare cioè di scrivere S(n+1) come S(n) più, meno, per, diviso "qualcosa"

 

In questo caso basta ricordare cos'è S(n+1). Esso rappresenta la somma dei primi n+1 numeri naturali. Come si ottiene tale somma? In questo modo:

 

S(n+1)=\overbrace{1+2+3+ ..... + n}^{=S(n)}+(n+1)

 

allora

 

S(n+1)=S(n)+(n+1)

 

Siamo quindi riusciti a scrivere S(n+1) come S(n) più "qualcosa".

 

A questo punto rimane solo da fare i conti andando a sostituire al posto di S(n) la sua espressione (stiamo utilizzando cioè l'ipotesi induttiva) e vedere se otteniamo la stessa cosa ottenuta in (\spadesuit):

 

S(n+1)=S(n)+(n+1)=\frac{n(n+1)}{2}+(n+1) = \frac{n(n+1)+2(n+1)}{2}=\frac{n^2+3n+2}{2} 

 

Il risultato è lo stesso di (\spadesuit) e quindi, per il principio di induzione possiamo affermare che proprietà è vera per ogni n\geq 1. Fine! Laughing

 


 

Per questa lezione è tutto! Solitamente si conclude una lezione assegnando degli esercizi. Io mi esulo dal farlo perché utilizzando l'apposita barra di ricerca ne troverete a decine di esercizi svolti e se ancora doveste avere problemi c'è sempre il Forum Laughing

 

Buona Matematica a tutti!

Galois

 

Esercizi correlati..........Lezione successiva


Tags: principio di induzione - come effettuare le dimostrazioni con il principio di induzione.