Matematica Discreta - Appunti parte 2

Continuazione della Volta Precedente

(Con il professore Acquistapace)

Eravamo rimasti con un esempio: In quale dire:

P(m) se m >14

allora m=3 + b·8

dove a e b sono degli interi maggiori o minori di zero, quindi a,b > 0.

Questo è un esempio in cui l'induzione semplice non funziona perché non ci dice che per il passo base come dato n₀=1 verrà la formula che muta. Dal fatto che m deve essere come un certo multiplo di 8 più un certo numero che adesso vediamo di fare un esempio di 8.

Per esempio se prendiamo un numero 45 che si riduce a:

45 = 3·5+0·8

quindi il numero 46

46 = 3·7+2·8

Non c'è nulla interessante tra i due numeri non si può dire che si può dimostrare per induzione. L'induzione che l'abbiamo presentato non funziona perché il passo base si sarà con 14.

14 = 6·8 - 2·3 + 1·8

Quindi il passo base ci rimane anche se il passo monito:

Perché da 14 non ci riduciamo 15 e non ci riduciamo 16. Quindi sembrerebbe che non ci si fa. Adesso vediamo il ragionamento che ne può tenere con passo?

Potrebbe essere che da 14 abbiamo ottenuto meno con per 15/16 come possiamo ridurre con il 17? Vediamolo che:

17 = 3·3 + 8·1

Da cosa sta condizione ridotta?

Dal fatto che 17-3·3=1·8=14

Quindi nel calcolo otteniamo una specie di induzione diremo che dice nel calcolo che x è ridotto P(m) allora c'è ver = P(m) 3 ed è verità P(m)+θ.

Prescindiamo da questo fatto.

Allora diciamo che se a se prendo m=14 se a somm... allora divento che ho disposizione avere 15, 16.

Perché il passo è 3.

Pertanto il periodo che stiamo tenendo o 14 2·8.

Quindi riducendo il passo a somm· 8:

m=14 certo a pure di 3 un minimo K (dato che m+k diventa · n =3).

Quindi ho trovato una k tale che la differenza che un minimo che ho fatto.

Vediamo che:

14 < k ≤ 16