Gli infiniti di Cantor (5): L'induzione matematica

In ricordo di Umberto Cibien, prematuramente scomparso, riproponiamo alcuni dei suoi migliori articoli.

Questo articolo cosituisce un "intermezzo" necessario a fornire strumenti utili per la prosecuzione dello studio degli infiniti di Cantor.

L'induzione matematica

Il metodo di induzione matematica si applica nel contesto dei numeri naturali e consiste nel dimostrare che se una certa proprietà vale per un certo numero naturale $n_{0}$ , e supponendo che sia valida per n si dimostra che è valida per n+1 allora vale per tutti i numeri naturali $n\geq n_{0}$ .

Definiamo formalmente Il principio di induzione:

Sia P(n) è una certa proprietà che dipende da n. Se:

1)P(n) è vera per un certo numero naturale $n_{0}$ (cioè $P(n_{0})$ ) è vera

2) Qualsiasi sia $n\geq n_{0}$ P(n) vera implica anche P(n + 1) vera,

allora P(n) `e vera per ogni $n\geq n_{0}$

Il punto 1) viene detto anche base dell'induzione, il punto 2) passo induttivo.

Una giustificazione intuitiva di tale principio, può essere la seguente:

se sappiamo che P(0) è vera, per il passo induttivo è vera anche P(1), ma allora anche P(2) e così via. Dato un n qualsiasi, con un numero finito di passaggi riusciamo a dimostrare che è vera anche P(n) :

P(0)-->P(1)--->P(2)---> ......---> P(n).

Non possiamo dimostrare il principio di induzione; esso fa parte della teoria assiomatica dei numeri naturali del matematico Italiano Giuseppe Peano. Notiamo però che è fortemente intuitivo, e il suo funzionamento si chiarisce meglio con degli esempi.

metaforicamente l'induzione matematica può essere rappresentata con l'effetto domino esteso all'infinito

1) La somma dei primi n numeri naturali

Vogliamo dimostrare che $S_{n}=1+2+3+4+...n=\frac{n(n+1)}{2}$ (questa è la proprietà P(n) da dimostrare)

per ogni $n\geq 1$

sappiamo che per n=1 è vera: infatti:

$S_{1}=\frac{1\cdot (1+1)}{2} =1$ quindi il caso base P(1) è vero.

Passo induttivo: supponiamo

$S_{n}=\frac{n(n+1)}{2}$ cioè se ammettiamo che è vera P(n)(passo induttivo) dobbiamo dimostrare che è vera P( n+1), ovvero:

$S_{n+1}=\frac{(n+1)(n+2)}{2}$ (al posto di n devo mettere n+1, e al posto di n+1 n+1+1=n+2)

ma:

$S_{n+1}=S_{n} +(n+1)=\frac{n(n+1)}{2}+(n+1)=\frac{n(n+1)+2(n+1)}{2}$

quindi , raccogliendo (n+1):

$Sn+1=\frac{(n+1)(n+2)}{2}$

quindi P(n+1) è vera. Ma allora è vera per ogni $n\geq 1$

2) Somma dei termini di una progressione geometrica.

Vogliamo dimostrare che, per ogni $n\geq 0$

$1+a+a^{2}+a^{3}+...a^{n}=\sum_{k=0}^{n}a^{k}=\frac{1-a^{n+1}}{1-a}$ (ricordiamo che $a^{0}=1$ )

Caso base, n=0

$\sum_{k=0}^{0}a^{k}=a^{0}=1$ = $\frac{1-a^{1}}{1-a}$

quindi P(0) è vera.

assumiamo P(n) vera (ipotesi induttiva):

$\sum_{k=0}^{n+1}a^{k}=\sum_{k=0}^{n}a^{k}+a^{n+1}=\frac{1-a^{n+1}}{1-a} + a^{n+1}=\frac{1-a^{n+1}+a^{n+1}-a^{n+2}}{1-a}$

quindi $\sum_{k=0}^{n+1}a^{k}=\frac{1-a^{n+2}}{1-a}$ cioè P(n+1) è vera. Ma allora è vera per ogni $n\geq 0$

Notiamo un fatto; il principio di induzione ci permette di dimostrare in modo rigoroso la validità di una formula, ma solo l'intuito ci permette di ipotizzare il risultato.

Vorrei che qualcuno provasse a dimostrare questa formula:

$\sum_{k=1}^{n}(2k-1)=n^{2}$ per ogni $n\geq 1$

Funzioni definite con il metodo di induzione: le funzioni ricorsive.

Il metodo induttivo si può applicare anche per definire una funzione sui numeri naturali dando il suo valore per 0 (o per un altro numero naturale iniziale), e fornendo la regola per passare da n ad n + 1. Tali funzioni si chiamano ricorsive; una funzione è ricorsiva quando chiama se stessa.
L’esempio più noto è quello della funzione n! ( n fattoriale) che altro non è che il prodotto dei primi n numeri interi : $n!=1\cdot 2\cdot 3\cdot 4\cdot ...n$

Possiamo considerare il fattoriale come una funzione di f:N--->N che associa ad n f(n)=n!

si definisce il suo valore per 0: 0! = 1 (per convenzione)

Poi si passa a (n + 1)! =n! (n + 1)

Vediamo subito che la definizione corrisponde proprio al fattoriale.

infatti $(n+1)!=1\cdot 2\cdot 3\cdot ...\cdot n\cdot (n+1)$ ; ma $1\cdot 2\cdot 3\cdot ...\cdot n=n!$ , quindi $(n+1)!= n!\cdot (n+1)$

La chiamata a n! chiede alla funzione di risolvere un calcolo più semplice di quello iniziale (il valore è più basso), ma è sempre lo stesso problema La funzione continua a chiamare se stessa fino a raggiungere il valore 1! (o O!) che sa risolvere immediatamente.

$5!=5\cdot 4!=20\cdot 3!=60\cdot 2!=120\cdot 1!=120$

La successione di Fibonacci

l'esempio del fattoriale però non mostra completamente l'importanza delle funzioni definite per ricorrenza. Infatti possiamo calcolare il fattoriale come abbiamo sempre fatto, moltiplicando i primi n numeri interi. Nel caso seguente invece la definizione può essere data solo in modo ricorsivo.

Ricordiamo che una successione di numeri naturali altro non è che una funzione di N-->N

La successione di Fibonacci, (che indichiamo con F: N-->N) è una successione di numeri interi positivi in cui ciascun numero è la somma dei due precedenti. Chiaramente riusciamo a fare questo se n>=3

Poniamo:

F(1)=1, F(2)=1

$F_{n}=F_{n-1}+ F_{n-2}$ per n>=3

Per calcolare un termine della successione è necessario procedere in modo iterativo, calcolando prima i precedenti, non possiamo farlo in modo diretto. Per esempio vogliamo calcolare F(6):

F(6)=F(5) + F(4)

F(5)=F(4) +F(3)

F(4)=F(3) + F(2)

F(3)=F(2) + F(1)

quindi: F(3)=2, F(4)=2+1=3, F(5)=3+2=5, F(6)=5+3=8

I primi termini della successione di Fibonacci sono: 1,1,2,3,5,8,13,21,34,55,89,144 ...

Indice di tutti gli articoli di Umberto presenti in archivio-Matematica

L	M	M	G	V	S	D
				1	2	3
4	5	6	7	8	9	10
11	12	13	14	15	16	17
18	19	20	21	22	23	24
25	26	27	28	29	30

Gli infiniti di Cantor (5): L'induzione matematica

Articoli correlati

(Q) Un semplice esponente ... **

Soluzioni dello scontro evitato **/***

Evitiamo uno scontro **/***

Il Problema di Apollonio e le "sue" coniche. 4 ***

Lascia un commento Cancel Reply

Soluzioni dello scontro evitato /*

Evitiamo uno scontro /*