Gli infiniti di Cantor. Parte quinta.Intermezzo: l'induzione matematica.

01/05/16

Gli infiniti di Cantor. Parte quinta.Intermezzo: l'induzione matematica.

Categorie: Matematica Teoria degli insiemi Scritto da: Umberto Cibien Commenti:2

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

 

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.

domino
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 ...

 

Articoli precedenti:

CANTOR parte Terza, gli insiemi numerabili

CANTOR parte Seconda: Corrispondenze e funzioni

CANTOR parte prima, gli insiemi

Cantor parte Quarta ; L'albergo di Cantor

 

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

Articoli correlati

2 commenti

  1. Arturo Lorenzo
    02/05/2016 at 08:48

    Dimostriamo che

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

    P(1) è vera. Infatti:

    \sum_{k=1}^{1}(2k-1)=2-1=1

    e

    n^{2}=1^{2}=1

    Assumiamo che sia vera P(n). Verifichiamo che è vera anche P(n+1):

    \sum_{k=1}^{n+1}(2k-1)=\sum_{k=1}^{n}(2k-1)+\left [ 2(n+1)-1 \right ]=n^{2}+2n+1=(n+1)^{2}

    Allora, per il principio di induzione, la (1) è vera per ogni n \geq 1.

     

     

  2. Umberto
    02/05/2016 at 09:57

    Perfetto! grazie Arturo

Lascia un commento

*

:wink: :twisted: :roll: :oops: :mrgreen: :lol: :idea: :evil: :cry: :arrow: :?: :-| :-x :-o :-P :-D :-? :) :( :!: 8-O 8)

 

Questo sito usa Akismet per ridurre lo spam. Scopri come i tuoi dati vengono elaborati.