Principio di induzione finita

[Nausicaa912]

Non mi è molto chiaro questo principio.
Sia K un sottinsieme di N. Se K soddisfa le condizioni
1. 1 $in$ K
b. n $in$ K $\Rightarrow$ n+1 $in$ K

allora K=N

poi fa un esempio
proviamo che per ogni k $in$ N vale
$1...+ k= k(k+1)/2$

si deve verificare che k=1 vlae e poi per k=n e per k=n+1

ma perchè? Non mi è chiaro il passaggio... Qualcuno potrebbe spiegarmi meglio?

[Gi81]

Il principio di induzione serve per dimostare le proprietà sui numeri naturali.

Chimiamo $P$ una proprietà che vogliamo dimostrare su tutti i numeri naturali.
[nel nostro esempio $P$: $1+2+3+.....+(k-1)+k=(k(k+1))/2$]

Diremo che $P(n)$ è vera se la proprietà $P$ vale per il numero naturale $n$
[nel nostro caso, per esempio $P(3)$ è vera perchè $1+2+3=6=(3*(3+1))/2$]

Il problema è che, ovviamente, i numeri naturali sono infiniti
Se dunque volessimo dimostrare che la proprietà $P(n)$ è vera $AA n in NN$ facendone la verifica uno alla volta, non finiremmo mai.

Ecco che ci viene in aiuto il principio di induzione
Dice questo:
Se si vuole dimostrare una proprietà $P$ sui numeri naturali, bastano $2$ verifiche da fare:
1) Dimostrare che vale

$P(1)$

cioè verificare che la proprietà vale per il primo elemento dell'insieme.

2) Dimostrare il seguente principio: Sia $n in NN$ generico;

Se $P(n)$ vale, allora vale anche $P(n+1)$

cioè, verificare che se la proprietà vale per un numero generico, allora vale anche per il suo successivo.

La prima dimostrazione è chiamata base dell'induzione, la seconda passo induttivo

Una vola che hai fatto queste due dimostrazioni, hai finito.
Infatti, hai che $P(1)$ vale, perchè l'hai dimostrato.
Inoltre anche $P(2)$ vale, perchè hai dimostrato che se $P$ vale per un numero , vale anche per il suo successivo.
Ma allora vale anche $P(3)$... E anche $P(4)$.... E anche $P(5)$... ecc ecc
Questa è la potenza della dimostrazione per induzione.
Spero di essere stato sufficientemente chiarificatore. Nel caso ti sfugga ancora qualcosa, chiedi pure


Ora andiamo all'esercizio:
1) Dimostra che $1+2+3+.....+(k-1)+k=(k(k+1))/2$ vale per $k=1$ [è molto semplice]
2) Dimostra che se vale $1+2+3+.....+(n-1)+n=(n(n+1))/2$, allora vale anche $1+2+3+.....+n+(n+1)=((n+1)(n+2))/2$

Prova a farlo e posta ciò che ti viene fuori.

[Nausicaa912]

grazie, sei stato chiaro. Ma allora, che serve quella premessa di K? è questo che non capisco...

[Gi81]

"Nausicaa91":Sia $K sube NN$.
Se $K$ soddisfa le condizioni
1. $1 in K$
2. $n in K \Rightarrow n+1 in K
allora $K=NN$

Sinceramente, me lo chiedo anch'io . Semplicemente, è una proprietà dei numeri naturali .
Con il principio di induzione c'entra poco o nulla. Sei sicura che sia collegata all'esercizio?

[Nausicaa912]

"Gi8":[quote="Nausicaa91"]Sia $K sube NN$.
Se $K$ soddisfa le condizioni
1. $1 in K$
2. $n in K \Rightarrow n+1 in K
allora $K=NN$

Sinceramente, me lo chiedo anch'io . Semplicemente, è una proprietà dei numeri naturali .
Con il principio di induzione c'entra poco o nulla. Sei sicura che sia collegata all'esercizio?[/quote]
Beh, io pensavo ci fosse un collegamento che mi sfuggiva perchè dopo questa proposizione in cui spiega questA proprietà di N, c'è scritto: "Esempio" e viene descritta l'induzione.

[cirasa]

"Gi8":[quote="Nausicaa91"]Sia $K sube NN$.
Se $K$ soddisfa le condizioni
1. $1 in K$
2. $n in K \Rightarrow n+1 in K
allora $K=NN$

Sinceramente, me lo chiedo anch'io . Semplicemente, è una proprietà dei numeri naturali .
Con il principio di induzione c'entra poco o nulla. Sei sicura che sia collegata all'esercizio?[/quote]

C'entra eccome! E' la traduzione del principio di induzione in simboli:
infatti se vuoi dimostrare una proprietà $P(n)$ per ogni numero naturale $n$, allora poni
$K={n\in NN:\ P(n)" è vera"}$
$K$ è ovviamente un sottoinsieme di $NN$.
Supponiamo di aver mostrato che
- $P(1)$ è vera, cioè che $1\in K$;
- $P(n)" vera"\Rightarrow\ P(n+1)" vera"$, cioè che $n in K \Rightarrow n+1 in K$.
Allora la proprietà citata da "Nausicaa91" (che è appunto il principio di induzione) ti permette di stabilire che $K=NN$, cioè che $P(n)$ è vera per ogni $n$.

[Nausicaa912]

AH! Beh, adesso è tutto molto più lineare. Ma è una cosa così scontata? Come l'hai scritta tu è davvero facile da capire... Questi professori universitari ci sopravvalutano un po' ;D

[e3353cdc139f9576d1418ef5ef3cff2aac614a86]

"Nausicaa91":Questi professori universitari ci sopravvalutano un po' ;D

Non credo che sia come dici. Semplicemente vi mettono giù il principio di induzione dicendovi che è molto importante e che bisogna capirlo bene, e quello che spesso recepiscono gli studenti è che si tratta di un concetto difficile. A pochi viene in mente che non è affatto difficile!

[Nausicaa912]

Infatti il principio di induzione mi era stato spiegato già al liceo, l'anno scorso. Quello che mi era ostico era il collegamento con la la proposizione precendente.
Comunque adesso, grazie a voi, è tutto chiaro.

[gugo82]

"Gi8":[quote="Nausicaa91"]Sia $K sube NN$.
Se $K$ soddisfa le condizioni
1. $1 in K$
2. $n in K \Rightarrow n+1 in K
allora $K=NN$

Sinceramente, me lo chiedo anch'io . Semplicemente, è una proprietà dei numeri naturali .
Con il principio di induzione c'entra poco o nulla. Sei sicura che sia collegata all'esercizio?[/quote]
Azz... Ma questo è il principio d'induzione!

Pensateci un attimo: quando volete provare che una proprietà [tex]$P(n)$[/tex] vale per tutti gli [tex]$n\in \mathbb{N}$[/tex], praticamente dovete dimostrare che l'insieme:

[tex]$K:=\{ n\in \mathbb{N}:\ \text{$P(n)$ è vera}\}$[/tex]

coincide con l'insieme [tex]$\mathbb{N}$[/tex].
Come lo fate? Beh, sfruttando il principio d'induzione come citato più sopra!