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₍₁₎ è 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 ∈ ℕ

$\sum _{r=1}^n\left(4r+3\right)$

Tramite qualche tentativo cerchiamo di capire il senso della serie:

1. P₍₁₎ = 7
2. P₍₂₎ = P₍₁₎ + 11 = 18
3. P₍₃₎ = P₍₂₎ + 15 = 33
4. P₍₄₎ = P₍₃₎ + 19 = 52
5. P₍₅₎ = P₍₄₎ + 23 = 75
6. P₍₆₎ = P₍₅₎ + 27 = 102
7. P_(...) = P_(...) + ... = ...

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

Dimostriamo che

$\sum _{r=1}^n\left(4r+3\right)=2n^2+5n$

Base

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

Passo induttivo

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

$\sum _{r=1}^k\left(4r+3\right)=2n^2+5n$

Dobbiamo dimostrare che vale anche per k+1.

$\sum _{r=1}^{k+1}\left(4r+3\right)=\stackrel{\text{Ipotesi induttiva}}{\sum _{r=1}^k\left(4r+3\right)}+4\left(k+1\right)+3$

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

$\stackrel{\text{Ipotesi induttiva}}{2k^2+5k}+4\left(k+1\right)+3=2k^2+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:

$2k^2+9k+7=\stackrel{\text{Pezzo 1}}{2k^2+4k+2}+\stackrel{\text{Pezzo 2}}{5k+5}$

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

$2k^2+4k+2=2\left(k^2+2k+1\right)=2{\left(k+1\right)}^2$

[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 ax²+bx+c:

$x=\frac{-b\pm \sqrt{b^2-4ac}}{2a}$

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

L'espressione

$k^2+2k+1$

trova gli zeri così:

$\mathrm{zeri}=\frac{-2\pm \sqrt{2^2-4}}{2}$

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)².

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)²+5(k+1), che è esattamente quanto stavamo cercando.

Serie $\sum _{r=1}^n{r}^3$

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³ = 1
2. P₍₂₎ = P₍₁₎ + 2³ = 9
3. P₍₃₎ = P₍₂₎ + 3³ = 36
4. P₍₄₎ = P₍₃₎ + 4³ = 100
5. P₍₅₎ = P₍₄₎ + 5³ = 225
6. P₍₆₎ = P₍₅₎ + 6³ = 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²
2. P₍₂₎ = 3²
3. P₍₃₎ = 6²
4. P₍₄₎ = 10²
5. P₍₅₎ = 15²
6. P₍₆₎ = 21²

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

$\frac{n\left(n+1\right)}{2}$

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

$\sum _{r=1}^n{n}^3={\left(\frac{n\left(n+1\right)}{2}\right)}^2$

Base

P₍₁₎ è vero, poiché 1³ = (1x(1+1)/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:

$\sum _{n=1}^k{n}^3+{\left(k+1\right)}^3$

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

${\left(\frac{k\left(k+1\right)}{2}\right)}^2+{\left(k+1\right)}^3$

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

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

${\left(\frac{k\left(k+1\right)}{2}\right)}^2=\left(\frac{k\left(k+1\right)}{2}\right)·\left(\frac{k\left(k+1\right)}{2}\right)={\left(k+1\right)}^2·\frac{k^2}{4}$

[/su_spoiler]
[su_accordion]

Otteniamo

${\left(k+1\right)}^2·\left(\frac{k^2}{4}+k+1\right)$

Metto a fattor comune la seconda espressione:

${\left(k+1\right)}^2·\left(\frac{k^2+4k+4}{4}\right)$

k²+4k+4 è (k+2)² e 4 è 2²:

${\left(k+1\right)}^2·\left(\frac{{\left(k+2\right)}^2}{2^2}\right)$

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

${\left(\frac{\left(k+1\right)·\left(k+2\right)}{2}\right)}^2$

Che è esattamente P_k+1