.dsy:it. (http://www.dsy.it/forum/)
- Logica matematica (http://www.dsy.it/forum/forumdisplay.php?forumid=246)
-- [help] Dimostrazione per Induzione (http://www.dsy.it/forum/showthread.php?threadid=20708)

Dimostrazione per Induzione

Salve !

Vorrei sapere se qualcuno sà in che modo si debba partire nella dimostrazione per induzione........

.....bisogna fare uso esclusivamente delle variabili n +1 , n+2 ........oppure è meglio utilizzare il risultato , cioè il valore numerico diretto.

Ad esempio se parto (per la dimostrazione) dal valore 0 , e poi partendo da questo valore n estendo la dimostrazione ad n+1........

.....ad n+1 devo usare il valore 1 = (0+1) oppure devo usare (n+1)

.......in questo caso però diventa un casino gia rappresentare 2 cioè n+2 = [(n+1) +1]..........se poi voglio andare avanti?


Non avreste un esempio pratico e semplice per capire la tecnica di dimostrazione?

GRAZIE Ciao!

__________________
_/\/\/\Bemipefe/\/\/\_

allora, la dimostrazione x induzione funziona così: lavorando in un insieme ordinato in cui puoi stabilire un minimo (se no non si può fare) prima dimostri che la regola vale per l'elemento + piccolo, dopodichè dimostri che se la regola vale fino a un certo n allora vale anche per il successivo di n (nota: dico "il successivo" perchè non è detto che il successivo di n in un insieme sia n+1)
esempio:

"tutti i numeri naturali che finiscono con 0 sono multipli di 5, cioè della forma k*5 dove k è un naturale"

l'insieme dei numeri naturali che finiscono con zero è ordinato e il minimo è zero

primo passo: dimostro che 0 è multiplo di 5 (banale)

secondo passo: se un certo numero n che finisce con zero è multiplo di 5, allora devo dimostrare che anche il naturale che finisce con zero successivo a n (che ottengo facendo n+10) sarà divisibile per 5, cioè devo dimostrare che:
k*5 + 10 = h*5
cioè essendo n nella forma k*5 (lo assumo per ipotesi induttiva) dimostro che il suo successivo ( cioè n + 10 cioè k*5 + 10) rispetta anch'esso la regola (cioè è nella forma h*5)
per cui svolgo il 2° passo facendo
k*5 + 10 = k*5 + 2*5 = (k+2)*5
k+2 è un naturale e lo posso chiamare h, per cui ho k*5 + 10 = h*5

CVD

spero di non averti incasinato le idee

Ok fin quì ci sono ........però il problema è che non sò quando la dimostrazione è finita e con quale prova si deve ritenere tale !?

__________________
_/\/\/\Bemipefe/\/\/\_

hai finito quando hai completato entrambi i passi
passo 1: dimostri che la proprietà vale sempre per il primo dell'insieme
passo 2: parti dall'ipotesi che la proprietà valga per tutti gli elementi fino a n, per cui ti scriverai per esteso la proprietà di uno di questi, ad esempio P(n) e la "modifichi" un po', nel senso la riscrivi in forme equivalenti, finchè non assume la forma P(n+1), cioè finchè non costituisce una prova della validità della proprietà per il successivo di n
ad esempio nella dimostrazione che ho fatto prima P(n) è "n è un multiplo di 5" o detto + formalmente n=k*5 mentre P(n+1) è "il successivo di n nell'insieme è un multiplo di 5" oppure n+10=h*5
nel momento in cui riesci a trasformare P(n) in P(n+1) (cioè nel nostro caso trasformare n=k*5 in n+10=h*5) hai finito la tua dimostrazione

Ok vediamo se ho capito........ti faccio adesso un esempio io:

Si dimostri per induzione che ogni numero naturale "n" maggoire di 1 si scompone in un numero <= x di fattori primi dove x = log_2;

...io avrei fatto così

Caso base :
S(1) = x >1 = successivo di 1 = 2 = n
2 essendo numero primo può essere scomposto in 0 fattori primi
se la proprietà vale log_2(1) = x >= 0 (è così è infatti, poichè x=0)

Caso Induttivo:
S(n) = x > n = successivo di n = 3 = n+1
3 essendo numero primo è scomponibile in 0 fattori primi
se la prorpietà vale log_2(1) = x >= 0
(è così è infatti x = 1,6 circa e il numero di fattori primi è <= x)

......dopo ciò tu cosa avresti fatto ? tu dici di far valere la proprietà fino ad un "n " "generico"......ma come faccio a dimostrare che la proprietà vale per un "n" generico ? (Ad esempio come faccio a sapere che log_2(n) = x con x>= al numero di fattori primi di n, se non assegno ad "n" stesso un valore ?)

CIAO!

__________________
_/\/\/\Bemipefe/\/\/\_

Nel testo dell'esercizio c'è log_2(n) e non log_2

....una svista Scusa

CIAO!

__________________
_/\/\/\Bemipefe/\/\/\_

no allora, non devi sostituire i numeri uno per uno, se no vai avanti all'infinito
tu fai il caso base dove dimostri che la proprietà vale per 2 (il primo dell'insieme)
dopo fai il caso induttivo in cui per ipotesi vale fino a n (un generico n, non devi sostituirci un numero), e partendo da quello devi dimostrare che vale anche per n+1
a questo punto ti chiederai, ma come faccio a convincermi che con questo metodo vale sempre, sia per 2 che per 3 che per 376438796?
il caso induttivo ti dice che SE hai dimostrato la proprietà fino a un certo numero ALLORA vale anche per il successivo. tu nel caso base l'hai dimostrata fino a 2
vale fino a 2 => allora vale anche per 3
vale fino a 3 => allora vale anche per 4
vale per 4 ...
e così all'infinito, solo che se ti metti a fare 2,3,4,5... come casi distinti non ti passa più, col metodo induttivo sottintendi questa catena di inferenze, ecco perchè usi un n generico, perchè così può valere come 2, come 3 o come 7684760

per quanto riguarda la specifica dimostrazione dei fattori primi ora non mi viene in mente come fare il caso induttivo, ci penso un po' e se i cricetini nella testa si svegliano la posto qua

cricetini attivi nella dimostrazione ho usato per comodità n-1 e n al posto di n e n+1 ma è la stessa cosa

caso base: S(2) --> la proprietà vale per 2? si! perchè 2 è primo quindi x=1 (cioè il 2 si scompone in 1 solo fattore primo, che è il 2 stesso) e in effetti x<=log_2(2) che è appunto 1

caso induttivo: assumendo che valga la proprietà per i primi n-1 numeri, dimostro che vale anche per n (ASSOLUTAMENTE non sostituire un numero a n, dev'essere un caso generico)
n può essere primo (in tal caso la proprietà è banalmente vera) o non primo, in tal caso avrà un certo numero di divisori, questi divisori non possono essere + grandi di n/2 ciascuno, e visto che siamo pessimisti prendiamo il caso in cui uno dei divisori sia proprio n/2. per ipotesi induttiva abbiamo che la proprietà vale per tutti gli interi fino a n-1, per cui vale anche per n/2, per cui n/2 verrà scomposto in log_2(n/2) fattori primi nel caso peggiore.
a questo punto, in quanti fattori verrà scomposto n? n lo si ottiene facendo n/2 * 2 quindi ha come fattori primi il 2 + tutti i fattori primi di n/2, che abbiamo appena detto essere log_2(n/2)
allora il famoso x sarà al massimo log_2(n/2) + 1 e applicando un po' di proprietà dei logaritmi abbiamo che:
log_2(n/2) + 1 = log_2(n/2) + log_2(2) = log_2( (n/2)*2 ) = log_2(n)
CVD

Grazie Polsy !
Adesso penso di avere acquisito il metodo di dimostrazione per induzione! .........una delle cose di logica che mi mancavano.........oltra al Sistema Deduttivo di Hilbert .....che a quanto pare studiamo solo noi della facoltà SMFN di Roma.....

....speriamo di no, altrimenti a chi chiedo spiegazioni?

__________________
_/\/\/\Bemipefe/\/\/\_

prego! mi fa piacere che ti sia stato utile
purtroppo hilbert non l'ho fatto e non ne so nulla... se proprio sei in crisi magari vai a ricevimento dal tuo prof di logica e fattelo un po' spiegare da lui

.....si grazie, avevo già preso in considerazione il fatto di andare dal Professore........solo che devo farmi 1 ora e mezzo di viaggio all'andata e al ritorno e poi dovrei arrivare a piedi al Dipartimento di Informatica, e con questo caldo non ne ho voglia .......però alla fine credo che sia l'unica soluzione ......CIAO!

__________________
_/\/\/\Bemipefe/\/\/\_

Allora .......ancora Induzione..... vediamo se ho imparato.

Una cosa semplice........ dimostrare che perogni N (escluso 0) vale 0/n = 0

base dell'induzione:

Passo 1 - 0/1 = 0

Passo 2 - 0/2 = 0

.....

Principio Induttivo:

Ammettendo che la proprietà valga per un generico (n-1) , cioè:

Passo (n-1) - 0/(n-1) = 0

allora deve valere anche per s[(n-1)] (successivo di n-1), e sapendo che s[(n-1)] = (n-1)+1 si avrà:

Passo (n-1)+1 - 0/(n-1)+1 = Passo n - 0/n = 0


Così può andare?

__________________
_/\/\/\Bemipefe/\/\/\_

Originally posted by Bemipefe
Allora .......ancora Induzione..... vediamo se ho imparato.

Una cosa semplice........ dimostrare che perogni N (escluso 0) vale 0/n = 0

base dell'induzione:

Passo 1 - 0/1 = 0

Passo 2 - 0/2 = 0

.....

Principio Induttivo:

Ammettendo che la proprietà valga per un generico (n-1) , cioè:

Passo (n-1) - 0/(n-1) = 0

allora deve valere anche per s[(n-1)] (successivo di n-1), e sapendo che s[(n-1)] = (n-1)+1 si avrà:

Passo (n-1)+1 - 0/(n-1)+1 = Passo n - 0/n = 0


Così può andare?

...ci devi arrivare facendo dei passaggi logici dall'equazione....

__________________
_/\/\/\Bemipefe/\/\/\_

Originally posted by Bemipefe
Il problema è che questi passaggi logici cambiano da dimostrazione a dimostrazione, e non riesco mai a capire quali sono

Nello specifico di questo esercizio, cosa intendi per passaggi logici?

Io ...spremendo un pò le meningi , ho trovato che....

se 0/n-1+1 non fosse 0 ma un generico x, cioè:

0/n-1+1 = x

allora dall'espressione bisognerebbe ricavare 0 = x*(n-1+1)

e ciò altro non porta al fatto che x = 0 cioè che 0/n-1+1 = 0

...così come va?