Matematica discreta / 5 - 12/10/2015

Una delle formulazioni del principio di induzione è il seguente:dati m, n ∈ ℕ, non è possibile che m < n < m+1In altre parole, tra due numeri consecutivi non esiste alcun altro numero.Tolto il PdI, gli altri assiomi sono validi anche per altri insiemi, come ℤ+ e ℝ+ (gli interi e i reali positivi).
Il PdI si esprime in modo equivalente con la forma riportata sopra (in parole povere: tra due naturali consecutivi non ci sono altri numeri) e con quella descritta nella lezione precedente:Supponiamo che P(n) sia un enunciato tale che:

  • Se P(1) è vero (base dell'induzione)
  • Se (se P(k) è vero allora è vero anche P(k+1)) è vero (passo induttivo)

Allora P(k) è vero ∀ k∈ℕ

La base è un semplice calcolo, mentre il passo induttivo è la prova che il "meccanismo" funziona, a patto che il salto discreto tra due numeri sia di 1 o multipli di 1.

Esempio: dati k, n, r ∈ ℕ

r=1n4r+3

Tramite qualche tentativo cerchiamo di capire il senso della serie:

  1. P(1) = 7
  2. P(2) = P(1) + 11 = 18
  3. P(3) = P(2) + 15 = 33
  4. P(4) = P(3) + 19 = 52
  5. P(5) = P(4) + 23 = 75
  6. P(6) = P(5) + 27 = 102
  7. P(...) = P(...) + ... = ...

(sul come si passi da questa serie di numeri alla formula 2n2+5n è mistero fitto)

Dimostriamo che

r=1n4r+3=2n2+5n

Base

Per dimostrare che P(1) è vero basta applicare 1 a destra e a sinistra:
4·1+3 = 7, e anche 2·12+5·1 = 7, quindi la base è dimostrata.

Passo induttivo

L'ipotesi induttiva dice che per k∈ℕ vale la formula:

r=1k4r+3=2n2+5n

Dobbiamo dimostrare che vale anche per k+1.

r=1k+14r+3=r=1k4r+3Ipotesi induttiva+4k+1+3

Siccome per l'ipotesi induttiva la sommatoria e 2k2+5k sono equivalenti, riscriviamo sostituendo la sommatoria con l'espressione:

2k2+5kIpotesi induttiva+4k+1+3=2k2+9k+7

A questo punto serve un po' di intuito. Vedendo il 9k come 4k + 5k e 7 come 2 + 5 appare improvvisamente evidente una soluzione della dimostrazione:

2k2+9k+7=2k2+4k+2Pezzo 1+5k+5Pezzo 2

Nel primo pezzo, raccogliendo 2, si ottiene un quadrato:

2k2+4k+2=2k2+2k+1=2k+12

[su_accordion]
[su_spoiler title="Come scomporre un'espressione di secondo grado" style="fancy"]
Ricordo la formula per trovare gli zeri di un'espressione di secondo grado del tipo ax2+bx+c:

x=-b±b2-4ac2a

Se questa formula non è chiara, c'è una spiegazione nel riepilogo che feci l'anno scorso.

L'espressione

k2+2k+1

trova gli zeri così:

zeri=-2±22-42

Siccome l'espressione sotto radice da zero (il delta è zero), l'espressione ha una sola soluzione, che è -1. Cambiando di segno la soluzione si ottiene il quadrato: (x+1)2.

Con lo stesso metodo si possono scomporre anche quadrati un po' più complicati, ma non è questa la sede per approfondire.

[/su_spoiler]
[su_accordion]

Nel secondo pezzo, banalmente si raccoglie 5 e si ottiene 5(k+1).

Il risultato finale è 2(k+1)2+5(k+1), che è esattamente quanto stavamo cercando.

Serie

r=1nr3

Stavolta l'obiettivo è cercare di capire qual è la funzione che rappresenta questa serie.

Ispirati da anni di Settimana Enigmistica, proviamo a risolvere la serie per i primi 6 numeri:

  1. P(1) = 13 = 1
  2. P(2) = P(1) + 23 = 9
  3. P(3) = P(2) + 33 = 36
  4. P(4) = P(3) + 43 = 100
  5. P(5) = P(4) + 53 = 225
  6. P(6) = P(5) + 63 = 441

Anche in questo caso bisogna avere un po' di intuito: cosa accomuna tutti questi numeri? Sono quadrati!
La serie può essere riscritta come:

  1. P(1) = 12
  2. P(2) = 32
  3. P(3) = 62
  4. P(4) = 102
  5. P(5) = 152
  6. P(6) = 212

Questa serie dovrebbe far rizzare le antenne di qualunque studente di MD, soprattutto quelli che hanno seguito la lezione precedente, perché la sequenza 1, 3, 6, 10, 15, 21, ... n, è esattamente la somma di tutti i numeri da 1 a n (1+2+3+4+5+...+n), rappresentata dalla formula

nn+12

Quindi la formula che cerchiamo, e che dimostreremo con il PdI, è

r=1nn3=nn+122
Base

P(1) è vero, poiché 13 = (1x(1+1)/2)2

Passo induttivo

Per dimostrare il passo induttivo dobbiamo ipotizzare vero P(k) e dimostrare che se è vero, allora è vero anche P(k+1).

Da una parte dobbiamo considerare P(k+1) come:

n=1kn3+k+13

Siccome abbiamo dato per vero Pk possiamo sostituire la sommatoria con la formula:

kk+122+k+13

[su_accordion]
[su_spoiler title="I passaggi saltati dal prof" style="fancy"]
Vorremmo arrivare a raccogliere (k+1)2.
"estrarre" (k+1)2 da (k+1)3 è facile: (k+1)2 x (k+1)

Per "estrarre" (k+1)2 dalla seconda espressione procediamo così:

kk+122=kk+12·kk+12=k+12·k24

[/su_spoiler]
[su_accordion]

Otteniamo

k+12·k24+k+1

Metto a fattor comune la seconda espressione:

k+12·k2+4k+44

k2+4k+4 è (k+2)2 e 4 è 22:

k+12·k+2222

Siccome tutti i termini sono elevati al quadrato, si può riscrivere così:

k+1·k+222

Che è esattamente Pk+1