Principio di Induzione Forte

[minepica]

Salve, domani ho la seconda prova intercorso di Metodi Matematici Per l'informatica e non mi è chiara l'induzione forte/completa!
Ad esempio:
P(n): "Un'affrancatura di n centesimi può essere composta da francobolli di 3 centesimi e francobolli di 5 centesimi". L'esercizio ha l'obbiettivo di dimostrare che P(n) è vera per ogni n ≥ 8!

[axpgn]

La versione "forte" dell'induzione presuppone che nel passo induttivo si assuma non solo che $P(n)$ sia vero ma lo siano anche $P(n_0), P(n_0+1), ..., P(n-1)$; questo perché nella dimostrazione del passo induttivo è necessario che siano veri anche questi.

Nel tuo caso, assunto per il passo induttivo quanto detto, si dimostra che un francobollo da $n+1$ centesimi può essere "costruito" con un francobollo da tre centesimi aggiunto ad uno di $n-2$ centesimi e quest'ultimo esiste per ipotesi induttiva.
Però non è tutto ...
Il passo base non è solo dimostrare che $P(n)$ è vera per $n_0=8=(3+5)$ ma almeno anche per $9=3+3+3$ e $10=5+5$; questo perché noi abbiamo sì dimostrato che $n+1=3+(n-2)$ ma se l'applichiamo a $n+2=10$ dobbiamo aver dimostrato anche che è vera per $n-1=7$ che invece non lo è ... perciò per "andare sul sicuro" la dimostriamo direttamente per $n=8, n=9, n=10$ (nel passo base) e siamo a posto ... ok?

Cordialmente, Alex

[minepica]

Ciao Alex, ti ringrazio ora mi è più chiaro ! Sapresti consigliarmi come posso capire quando usare l'induzione matematica e quando l'induzione forte?? Le sostanziali differenze/vantaggi quali sono?? So che in alcuni casi è più comodo usare una ed in altri e più comodo usare l'altra e che in ogni caso da una e possibile passare all'altra!

In oltre dovrei capire anche l'induzione strutturale che non mi è chiara per niente !

Grazie mille in anticipo !!!

[axpgn]

Sinceramente non saprei ... per me è questione di esperienza, di "colpo d'occhio" ... tieni conto che spesso esistono metodi diversi per dimostrare qualcosa, quale sia il migliore da adottare lo vedi dopo ...