Dimostrazione per Induzione
Eh..............si , sono di nuovo quì ad elemosinare il vostro "Sapere".
Quest'oggi vorrei imparare la "Dimostrazione per Induzione".
Cominciamo con un esempio:
Sia f : N->N così definita f(0)= 1 , f(n+1)= f(n) + 2.
Dimostrare che per ogni "n" appartenente ad N f(n) è dispari.
...come procedereste voi?
Io riesco a dimostrarlo solo per i casi precisi in cui n ha un valore, ma poi quando devo costruire il caso generale con "n" non sò come fare
fare.
Bemipefe
Quest'oggi vorrei imparare la "Dimostrazione per Induzione".
Cominciamo con un esempio:
Sia f : N->N così definita f(0)= 1 , f(n+1)= f(n) + 2.
Dimostrare che per ogni "n" appartenente ad N f(n) è dispari.
...come procedereste voi?
Io riesco a dimostrarlo solo per i casi precisi in cui n ha un valore, ma poi quando devo costruire il caso generale con "n" non sò come fare
fare.
Bemipefe
Risposte
Sapevo di questo tipo di contraddizzione, cioè che negando da n in poi si nega anche il caso base.
Vediamo se ho imparato il metodo di dimostrazione per induzione:
Dimostrare per ogni n : n ha come cifra finale 0, che è un multiplo di 5.
Si inizia con il formalizzare il tutto....
- n appartiene ai naturali e soddisfa la proprietà dello zero Z.
-n /5 = x AND x appartiene a N
-n mod 5 = 0
CASO BASE:
-0 appartiene a N e Z(0) è vera quindi VERO
-0 /5 = 0 , soluzione intera appartenente a N VERO
-0 mod 5 = 0 VERO
INDUZIONE:
Si assume vera la proprietà per un "n" generico, per cui valgono tutti i casi della proprietà.
Si dimostra per il successivo di n la proprietà...
S(n) è il successivo di n che rispetta la proprietà Z e che deve soddisfare la proprietà oggetto di dimostrazione.
S(n) = (n+10) in quanto quest'ultimo è il successivo di "n" che soddisfa la proprietà Z
-(n+10) ....in oltre è sicuramente naturale in quanto n è un naturale , così come 10 , dunque anche n+10 è un naturale.
-(n+10)/5 = x ed è naturale in quanto....
-(n+10) mod 5 = 0 poichè n mod 5 = 0 poi 10 mod 5 = 0 quindi (n+10) mod 5 = 0
Bemipefe
Vediamo se ho imparato il metodo di dimostrazione per induzione:
Dimostrare per ogni n : n ha come cifra finale 0, che è un multiplo di 5.
Si inizia con il formalizzare il tutto....
- n appartiene ai naturali e soddisfa la proprietà dello zero Z.
-n /5 = x AND x appartiene a N
-n mod 5 = 0
CASO BASE:
-0 appartiene a N e Z(0) è vera quindi VERO
-0 /5 = 0 , soluzione intera appartenente a N VERO
-0 mod 5 = 0 VERO
INDUZIONE:
Si assume vera la proprietà per un "n" generico, per cui valgono tutti i casi della proprietà.
Si dimostra per il successivo di n la proprietà...
S(n) è il successivo di n che rispetta la proprietà Z e che deve soddisfare la proprietà oggetto di dimostrazione.
S(n) = (n+10) in quanto quest'ultimo è il successivo di "n" che soddisfa la proprietà Z
-(n+10) ....in oltre è sicuramente naturale in quanto n è un naturale , così come 10 , dunque anche n+10 è un naturale.
-(n+10)/5 = x ed è naturale in quanto....
-(n+10) mod 5 = 0 poichè n mod 5 = 0 poi 10 mod 5 = 0 quindi (n+10) mod 5 = 0
Bemipefe
vorrei mettere in luce una elegante variante del principio di induzione:
-si dimostri la tesi per il caso base
-si supponga falsa la tesi per il caso n
-se si dimostra che la tesi è falsa anche per il caso n-1 allora la tesi è vera.
questo perchè iterando il procedimento sarebbe falsa anche per il caso base e si otterrebbe una contraddizione.
ad esempio, nel primo esercizio, la tesi è banalmente vera per il caso base; supponiamo allora f(n+1) pari, allora deve essere anche f(n) pari, da cui l'assurdo; quindi f(n) è dispari per ogni n.
ciao, ubermensch
-si dimostri la tesi per il caso base
-si supponga falsa la tesi per il caso n
-se si dimostra che la tesi è falsa anche per il caso n-1 allora la tesi è vera.
questo perchè iterando il procedimento sarebbe falsa anche per il caso base e si otterrebbe una contraddizione.
ad esempio, nel primo esercizio, la tesi è banalmente vera per il caso base; supponiamo allora f(n+1) pari, allora deve essere anche f(n) pari, da cui l'assurdo; quindi f(n) è dispari per ogni n.
ciao, ubermensch
Grazie Platone !
Bemipefe
Bemipefe
In questo caso bsoga usare l'induzione fofte.
Voglio dimostrare che la proprieta' e' vera per n supponendo che sia vera per tutti gli interi < di n.
n=p1*p2*...*pm (per motivi di semlicita' d notazione ho tralasciato gli esponenti).
Considero il numero naturale s=p1*p2*...*p(m-1). Si ha che s<=n/2
Per l'ipotesi induttiva m-1<=log_2(s-1) allora m<=log_2(s-1)+1 = log_2(s-1)+log_2(2) = log_2(2*s) <= log_2(n).
Platone
Voglio dimostrare che la proprieta' e' vera per n supponendo che sia vera per tutti gli interi < di n.
n=p1*p2*...*pm (per motivi di semlicita' d notazione ho tralasciato gli esponenti).
Considero il numero naturale s=p1*p2*...*p(m-1). Si ha che s<=n/2
Per l'ipotesi induttiva m-1<=log_2(s-1) allora m<=log_2(s-1)+1 = log_2(s-1)+log_2(2) = log_2(2*s) <= log_2(n).
Platone
Avrei bisogno di aiuto con quest'altra dimostrazione:
Si dimostri per induzione che ogni numero naturale "n" maggiore di 1 si scompone in al più "x" fattori primi con
x =log_2(n).
Quindi x <= del numero di fattori primi.
CASO BASE:
log_2(2) = 1 ---> x = 1 fattore primo , vero in quanto x <= dei fattori primi di 2
Bemipefe
Si dimostri per induzione che ogni numero naturale "n" maggiore di 1 si scompone in al più "x" fattori primi con
x =log_2(n).
Quindi x <= del numero di fattori primi.
CASO BASE:
log_2(2) = 1 ---> x = 1 fattore primo , vero in quanto x <= dei fattori primi di 2
Bemipefe
Attenzione.
il passo induttivo non e' quello che hai scritto tu (queela non e' niente, hai solo verificato "a mano" che la proposizione e' vera per un po' di naturali), ma e' cio' che hai chiamato induzione.
Inoltre anche qui ci sono delle imprecisioni concettuali; anzitutto supponendo che la proprieta' sia vera per tutti gli interi da 0 a n, stai usando quello che si chiama inuzione debole: in questo caso non serve, e quindi "conviene" usare l'induzione forte, ossia supporre che la proprieta' sia vera solo per un determinato n, e non anche per tutti quelli precedenti (daltronde in questo caso il fatto che sia vera anche per i precedenti non viene usato e quindi non va la pena supporlo), e dimostrare che e' vera anche per n+1.
Il modo in cui lo hai dimostrato tu e' corretto, ma non vedo la necessita' di introdurre le relazioni di congruenza (e' evidente anche senza che sommando un numero pari a uno dispari ottengo ancora un numero dispari; se poi questo numero pari e' il 2, ottengo il numero dispari successivo).
Infine e' sbagliato affermare che "se per "n" è vera allora deve essere vera anche per n+1", questo e' quello che devi dimostrare. Mentre il principio di induzione (forte) afferma che: data la proprieta' P(x), se P(0) e' vera, e SE (questo e' quello che bisogna dimostrare) suppostavera P(n) segue che e' vera anche P(n+1), allora la proprieta' e' vera per ogni n appartenente a N.
Platone
il passo induttivo non e' quello che hai scritto tu (queela non e' niente, hai solo verificato "a mano" che la proposizione e' vera per un po' di naturali), ma e' cio' che hai chiamato induzione.
Inoltre anche qui ci sono delle imprecisioni concettuali; anzitutto supponendo che la proprieta' sia vera per tutti gli interi da 0 a n, stai usando quello che si chiama inuzione debole: in questo caso non serve, e quindi "conviene" usare l'induzione forte, ossia supporre che la proprieta' sia vera solo per un determinato n, e non anche per tutti quelli precedenti (daltronde in questo caso il fatto che sia vera anche per i precedenti non viene usato e quindi non va la pena supporlo), e dimostrare che e' vera anche per n+1.
Il modo in cui lo hai dimostrato tu e' corretto, ma non vedo la necessita' di introdurre le relazioni di congruenza (e' evidente anche senza che sommando un numero pari a uno dispari ottengo ancora un numero dispari; se poi questo numero pari e' il 2, ottengo il numero dispari successivo).
Infine e' sbagliato affermare che "se per "n" è vera allora deve essere vera anche per n+1", questo e' quello che devi dimostrare. Mentre il principio di induzione (forte) afferma che: data la proprieta' P(x), se P(0) e' vera, e SE (questo e' quello che bisogna dimostrare) suppostavera P(n) segue che e' vera anche P(n+1), allora la proprieta' e' vera per ogni n appartenente a N.
Platone
Vediamo se ho capito:
CASO BASE:
f(0) = 1
PASSO INDUTTIVO:
f(1) = f(0)+2 = 3
f(2) = f(1) +2 = 5
.....
...
INDUZIONE:
Suppongo vera la proprietà da 0 ad un certo valore "n".
Quindi se per "n" è vera allora deve essere vera anche per n+1......quindi f(n+1) = f(n) +2.
Supponendo la proprietà vera fino a n ho automaticamente affermato che f(n) mod 2 = 1.
Dunque f(n+1) = f(n) + 2 = X che è sicuramente disparo.
Così no!?.................. più tardi vi posto altri esempi così faccio un pò di pratica.....
Bemipefe
CASO BASE:
f(0) = 1
PASSO INDUTTIVO:
f(1) = f(0)+2 = 3
f(2) = f(1) +2 = 5
.....
...
INDUZIONE:
Suppongo vera la proprietà da 0 ad un certo valore "n".
Quindi se per "n" è vera allora deve essere vera anche per n+1......quindi f(n+1) = f(n) +2.
Supponendo la proprietà vera fino a n ho automaticamente affermato che f(n) mod 2 = 1.
Dunque f(n+1) = f(n) + 2 = X che è sicuramente disparo.
Così no!?.................. più tardi vi posto altri esempi così faccio un pò di pratica.....
Bemipefe
Guarda, e' molto semplice.
Passo pase: f(0)=1 disapari. ok
passo indutivo: supponiamo che l'enunciato sia vero per n e dimostriano che e' vero per n+1.
f(n+1)= f(n) + 2, ma per ipotesi f(n) e' dispari, e un numero dispari + 2 e' ancora dispari.
Allora per il principio di induzione l'enunciato e' vero per ogni n appartenente a N.
Platone
Passo pase: f(0)=1 disapari. ok
passo indutivo: supponiamo che l'enunciato sia vero per n e dimostriano che e' vero per n+1.
f(n+1)= f(n) + 2, ma per ipotesi f(n) e' dispari, e un numero dispari + 2 e' ancora dispari.
Allora per il principio di induzione l'enunciato e' vero per ogni n appartenente a N.
Platone
Accedi a tutti gli appunti
Tutor AI: studia meglio e in meno tempo