INDUZIONE

[matematicoestinto]

Ciao a tutti... ancora non mi sono cominciati i corsi, ma sfoglianfo il libro di Geometria del corso di ingegneria ho trovato fra le prime pagine uan dimostrazione per induzione..

Qualcuno potrebbe spiegarmi meglio il procedimento induttivo? Potete farmi un semplice esempio? Io l'ho trovata per dimostrare che le permutazioni di n oggetti sono in nemero n!


GRAZIE

[pingo1]

il principio di induzione ci dice che se una proprietà è vera per n=1 è vera anche per il valore successivo ossia n=2; se è vera per n=2 allora è vera anche per n=3 e così via.
in generale data una proposizione P(n) il cui enunciato dipende da n , con n numero naturale maggiore o uguale a 1,se
1) è vera per n=1
2) supposta vera per n, è vera anche per n+1
allora P(n)è vera per ogni n maggiore o uguale a 1.

consideriamo la somma delle prime n potenze di 2 , apartire da 2^0. Si può dimostrare che la somma è uguale a 2^n-1.
Per esempio se n=3
2^0+2^1+2^2=1+2+4=7 e quindi 2^3-1=8-1=7
per dim. per induzione :primo passo
Dim. che è vera per n=1. infatti ,la somma si riduce a 2^0=1 e anche 2^n-1vale 2^1-1=1
secondo passo
dimostriamo che supposta vera la proprietà per un generico valore n, essa è vera anche per n+1, ossia il valore seguente. per ip. è vero:
2^0+2^1+2^2+....2^(n-1)=2^n-1
sommiamo ad ambo i membri 2^n
2^0+2^1+2^2+....2^(n-1)+2^n=2^(n-1)+2^n
questa si può anche scrivere
2^0+2^1+2^2+....2^(n-1)+2^[(n+1)-1]=2*2^n-1
2^0+2^1+2^2+.....+2^[(n+1)-1]=2^(n+1)-1

[fireball1]

Esempio più banale possibile; proviamo che:
$sum_(k=1)^n k = (n(n+1))/2
procedendo per induzione su $n$.
Chiamiamo $ccP_n$ la formula che vogliamo dimostrare.
Si verifica immediatamente che $ccP_1$ è vera.
Volendo si può verificare anche $ccP_2$, $ccP_3$ tanto
per avere un'idea del significato della formula.
A questo punto si può fare l'ipotesi induttiva;
ciò equivale ad affermare la seguente proposizione:
"Sia $sum_(k=1)^(n-1) k = (n(n-1))/2$. Allora, $sum_(k=1)^n k = (n(n+1))/2$".
e dobbiamo dimostrare quest'ultima proposizione,
ovvero, dobbiamo provare che $ccP_(n-1) => ccP_n$
assumendo per vera $ccP_(n-1)$ (questa infatti è l'ipotesi induttiva).
Allora, per l'ipotesi induttiva abbiamo:
$sum_(k=1)^n k = sum_(k=1)^(n-1) k + n = (n(n-1))/2 + n = (n(n+1))/2
ed ecco dimostrata la formula che fornisce il valore
della somma dei primi n numeri interi, nota a Gauss all'età di soli 7 anni!