Capire come funziona il Principio di Induzione

[Programmer1]

Buonasera a tutti cari amici, questi giorni sto cercando di capire come fare dimostrazioni sfruttando il principio di induzione. Ho letto sia su un libro (che non parla quasi per niente di questo argomento) e sia su alcuni siti come fare dimostrazioni in questo modo e nonostante io riesca a fare gli esercizi, ci sono alcune cose che non mi sono chiare:

Il principio di induzione da quel che ho capito serve a dimostrare che una certa proprietà vale da un certo "n" in poi, prendendo come riferimento l'insieme dei numeri naturali.

Prima domanda: perché prendere come riferimento l'insieme N ?

Ho iniziato a fare qualche esercizio per capire un po' come funziona e mi sono ritrovato a dover dimostrare questa uguaglianza per ogni n appartenente ad N:

$(9^(n+1)+2^(6*n+1)) % 11=0$

Quindi mi sta chiedendo di dimostrare se una certa quantità è divisibile per 11. Allora ho provato a risolverlo:

1) Dimostro per il caso base che vale la proprietà, quindi faccio:

$(9^(0+1)+2^(6*0+1))=11$
Quindi è divisibile per 11

2) Assumo che la proprietà valga per n = ad un generico n e nel frattempo mi rendo conto di poter scrivere l'uguaglianza come:

$9^(n+1)+2^(6*n+1)=11⋅k$
$9^(n+1)=11⋅k−2^(6*n+1)$

3) Dimostro che vale per n+1, perché il principio dice che se la proprietà vale per n allora vale anche per n+1

Ecco quindi un'altra cosa che non capisco: perché devo andare a dimostrare che vale per n+1? E soprattutto perché implicitamente si deve intuire che se vale per n+1 allora vale sicuramente anche per n?
Cioè, voglio dire, non mi ritrovo nella condizione in cui ho che A implica B e non posso sapere se B implica A? Sono confuso...


Ho sostituito "n" con "n+1"

$9^(n+2)+2^(6*n+7)=11⋅h$

Poi ho cercato di ricondurmi all'ipotesi induttiva quindi innanzitutto ho scritto:

$9^(n+2)=9^(n+1)⋅9$

E anche:

$2^(6*n+7)=2^(6*n+1)⋅2^6$

Potendo ora sostituire ciò che ho dedotto per ipotesi induttiva scrivo:

$(11*k−2^(6*n+1))⋅9+2^(6*n+1)*2^6=11*h$
$=99*k−9⋅2^(6*n+1)+2^6*2^(6*n+1)=11*h$
$=99*k+55*2^(6*n+1)=11*h$
$=11*(9*k+5*2^(6*n+1))=11*h$




E così si vede che è divisibile per 11 essendo un suo multiplo...e quindi tutto quello che ho scritto come fa a dimostrare che vale veramente per tutti? Avendolo solo dimostrato per n+1 come faccio ad essere proprio certo che valga per tutti quanti?

PS. Se ho fatto qualche errore scusatemi

[feddy]

TI consiglio di dare una letta alla prima pagina di questa dispensina, dove viene dimostrato perché funziona e perché si usino i naturali.

[axpgn]

Diciamo che non è il principio di induzione che fa riferimento all'insieme $NN$, piuttosto è l'insieme dei naturali che ha il P.I.M. nel suo DNA ... ... è proprio un elemento costitutivo ...

"Programmer":3) Dimostro che vale per n+1, perché il principio dice che se la proprietà vale per n allora vale anche per n+1

No, il P.I.M. dice un'altra cosa e cioè che ipotizzando vera la proprietà per l'indice $n$ se si riesce a dimostrarne la validità per l'indice $n+1$ allora hai dimostrato il "passo induttivo".

"Programmer":...e quindi tutto quello che ho scritto come fa a dimostrare che vale veramente per tutti? Avendolo solo dimostrato per n+1 come faccio ad essere proprio certo che valga per tutti quanti?

Pensa ad una lista ordinata, la quale, come tutte le liste, ha un "primo della lista"; dimostrando la validità del passo base e del passo induttivo in pratica ottieni questo:
- la proprietà è vera per il "primo della lista" (passo base)
- se è vera per il primo della lista, allora è vera per il secondo della lista (passo induttivo) ma noi sappiamo che è vera per il primo (vedi sopra) quindi è vera per il secondo.
- se è vera per il secondo della lista, allora è vera per il terzo della lista (passo induttivo) ma noi sappiamo che è vera per il secondo (vedi sopra) quindi è vera per il terzo.
- se è vera per il terzo della lista, allora è vera per il quarto della lista (passo induttivo) ma noi sappiamo che è vera per il terzo (vedi sopra) quindi è vera per il quarto.
- se è vera per il quarto ... ad libitum ...

Cordialmente, Alex

[Programmer1]

Vi ringrazio per l'aiuto, ora ho le idee un po' più chiare...però c'è un'altra cosa che vorrei sapere...ovvero, una certa proprietà può essere falsa, come mi accorgo che lo è usando il principio di induzione? Nel senso, dai miei calcoli, dopo aver provato a dimostrare la proprietà, se vedo che non arrivo da nessuna parte (nei casi di dimostrazioni un po' più complicate ma sempre di base, tipo quella che ho scritto) devo considerare falsa la proprietà? Oppure c'è un altro modo per sapere la verità?
Comunque grazie mille ancora

[axpgn]

Il P.I.M. si usa per dimostrare la validità di una proprietà non per smentirla, il fatto che non si riesca a dimostrare qualcosa con il P.I.M. non implica che questo qualcosa sia falso; in generale la si usa per confermare una congettura che in qualche modo sia legata ai naturali (non necessariamente numerica)

[gugo82]

Segnalo questo mi vecchio post e pure quest'altro mio vecchio post, che potrebbero risultare interessanti.

[Programmer1]

Grazie a tutti, credo di aver capito finalmente