Principio d'induzione

[snooze89]

Ciao a tutti. Oggi abbiamo fatto il principio di induzione, ma onestamente non è che l'abbia capito molto... Potreste mica spiegarmelo passo per passo (anche le cose più ovvie o semplici) e facilmente?

Vi faccio anche un esempio di dimostrazione per induzione...
Io ho capito che noi abbiamo un A(n) = un predicato

Esempio:
$A(n) = 2^n > n$

Il primo passo, quello più semplice, è porre n=0 o, il prof ci ha detto, ad un qualsiasi numero intero

$A(1) = 2^1 > 1$

E fino a qui è verificato e anche molto banale

Il passo successivo è quello di porre A(n+1) ed è qui che mi perdo...
Vi ringrazio veramente, spero voi possiate spiegare questo principio in maniera elementare in modo tale che poi io possa applicarlo in altre formule...

[Lord K]

Preso per vero $A(n)$ nel caso da te citato si prosegue con:

$A(n+1)= 2^(n+1)>n+1$

$2^(n+1)=2*2^n> text{ [per il passo precedente] }>2*n > n+1$

Conclusa la dimostrazione.

[adaBTTLS1]

devi supporre che A(n) sia vero e dimostrare che da questo segue che anche A(n+1) è vero.
è importante aver esplicitato A(1): 2>1, perché ora puoi supporre n>=1.
devi dare per buono $A(n): 2^n>n$ e passare a dimostrare $A(n+1): 2^(n+1)>n+1$
ma $2^(n+1)=2^n*2>n*2$ per l'ipotesi induttiva. se $n>=1$, $2*n=n+n>=n+1$, quindi, riepilogando,
$2^(n+1)=2^n*2>n*2=n+n>=n+1=>2^(n+1)>n+1$
quindi poiché vale A(1), se vale A(n) vale anche A(n+1). [vale anche A(0): 1>0, ma non era sufficiente per la dimostrazione del caso generale]
dunque A(n) vale $AA n in NN$
spero di essere stata chiara. ciao.

[Dorian1]

Giuseppe Peano postulò la seguente proposizione, definendo l'insieme dei numeri naturali $NN$...

"Peano":
Se $S$ è un sottinsieme di $NN$ contenente $0$ e tale che $AAk in S => k+1 in S$, allora $S=NN$

...la quale ci fornisce un'efficace tecnica di dimostrazione.
Supponiamo di avere una famiglia di proposizioni $P(n)$, ad esempio:

se l'insieme $H$ ha $n$ elementi, l'insieme delle sue parti ha $2^n$ elementi.

E' chiaro che, variando $n in NN$, otteniamo di volta in volta una proposizione diversa...

$P(0)$=se $H$ ha $0$ elementi, l'insieme delle sue parti ha $1$ elemento
$P(1)$=se $H$ ha $1$ elemento, l'insieme delle sue parti ha $2$ elementi
...

e che una verifica "a mano" di tutte le proposizione non è possibile.
Quindi, detto $K$ il seguente insieme:

${n in NN | P(n) è vera}$

...possiamo seguire questo ragionamento. Se $P(0)$ è vera, $0 in K$. Inoltre se la validità della $n$-esima proposizione implica la validità della $n+1$-esima (in simboli $P(n)=> P(n+1)$) abbiamo che $K$ ha la proprietà: $k in K => k+1 in K$ e quindi, per l'assioma di Peano, $K=NN$. Cioè $P(n)$ è vera $AA n in NN$.

Ecco quindi come si usa questo strumento:
(1) Dimostro "a mano" la prima proposizione della famiglia (base dell'induzione);
(2) Deduco la $n$-esima proposizione, ipotizzando la $n-1$-esima;

[adaBTTLS1]

... sono arrivata tardi ...