[Risolto] Esercizio sul principio di induzione

Il principio di induzione detto anche procedimento induttivo, è una tecnica di dimostrazione che trova impiego nella maggior parte dei teoremi matematici. Esso può dividersi in due forme chiamate rispettivamente $1°$ $forma$ e $2°$ $forma$. Prima di dimostrare la proposizione cerchiamo di dire qualcosa in merito su questo principio di induzione e vediamo perché è così importante.

Il ragionamento induttivo procede dal particolare al generale e consta solitamente di premesse di ordine particolare, da cui si traggono conclusioni di ordine generale. Ecco un esempio :

"$Socrate$ $è$ $un$ $uomo$ $mortale$"

"$Platone$ $è$ $un$ $uomo$ $mortale$"

"$Aristotele$ $è$ $un$ $uomo$ $mortale$"

$Dunque$ : $Probabilmente$ $tutti$ $gli$ $uomini$ $sono$ $mortali$.

Le premesse dell'argomentazione induttiva, però non garantiscono in maniera assoluta la verità della conclusione; al massimo ce ne forniscono una garanzia probabilistica. In sintesi, se le premesse di un argomento induttivo sono tutte vere, la conclusione non è necessariamente vera, ma presenta soltanto un certo grado di probabilità di esserlo. Per questa ragione, qualche logico esclude che abbia senso parlare di validità o invalidità per un ragionamento induttivo, perché si realizza in esso una relazione stretta tra la verità delle premesse e la verità della conclusione. Ma dunque non possiamo non porci la seguente domanda: Come è possibile dimostrare attraverso un ragionamento induttivo che una proprietà valga per ogni numero intero positivo se le premesse non garantiscono necessariamente la verità nella conclusione?

Ebbene molti matematici e logici dopo anni di dibattiti su questo problema dell'induzione sono arrivati finalmente ad una conclusione definitiva. Hanno pensato di legare in qualche modo ragionamenti induttivi e deduttivi. Come abbiamo già menzionato, non è possibile stabilire a priori la verità della nostra conclusione poiché le premesse non ce lo consentono. Se invece le nostre premesse fossero fondate ovvero si dà per scontata o di per sé evidente la verità universale delle premesse si può far seguire necessariamente la conclusione. Riprendendo l'esempio precedente possiamo subito concludere che tutti gli uomini sono mortali poiché ci stiamo basando sulla proposizione universalmente vera e cioè che ogni uomo è mortale.

Fatte queste premesse cerchiamo di dimostrare la nostra proposizione ma vediamo prima cosa ci dice il principio di induzione :

$Principio$ $di$ $induzione$ $\bigl($ $1°$ $forma$ $\bigr)$

$Supponiamo$ $che$ $P$$\bigl($$n$$\bigr)$ $sia$ $un$ $predicato$ $unario$ $che$ $dipende$ $da$ $un$ $numero$ $intero$ $n$ $\in$ $N$. $Se$, $dato$ $un$ $numero$ $intero$ $n_{0}$, $vale$ $che$ :

$\bigl($ $i$ $\bigr)$  : $P$$\bigl($$n_{0}$$\bigr)$ $è$ $vera$  $\bigl($ $base$ $dell$' $induzione$ $\bigr)$;

$\bigl($ $ii$ $\bigr)$  : $\forall$ $k$  $\geq$  $n_{0}$,  $è$   $vera$  $l$'$implicazione$   $P$$\bigl($ $k$ $\bigr)$   $\Longrightarrow$   $P$$\bigl($ $k$ $+$ $1$ $\bigr)$;

$\bigl($ $P$$\bigl($ $k$ $\bigr)$  $si$ $chiama$ $ipotesi$ $induttiva$  $invece$  $P$$\bigl($ $k$ $+$ $1$ $\bigr)$ $si$ $chiama$ $passo$ $induttivo$   $\bigr)$;

Verifichiamo la base dell'induzione per $n$ $=$ $0$ :

$P$$\bigl($ $0$ $\bigr)$ $=$ $\sum\limits_{k = 0}^{0}{ \displaystyle\frac{5^{k} }{ 4^{k} } }$ $=$ $\displaystyle\frac{5^{0} }{ 4^{0} }$ $=$ $1$  

$P$$\bigl($ $0$ $\bigr)$ $=$ $\displaystyle\frac{5^{n + 1}}{ 4^{n} }$ $-$ $4$ $=$ $\displaystyle\frac{5^{1}}{ 4^{0} }$ $-$ $4$ $=$ $5$ $-$ $4$ $=$ $1$

Ora non ci resta che verificare il passo induttivo e cioè :

$\forall$$n$ $\geq$ $1$ deve risultare vera l'implicazione $P$$\bigl($ $n$ $\bigr)$ $\Longrightarrow$ $P$$\bigl($ $n$ $+$ $1$ $\bigr)$. Dunque poniamo

$P$$\bigl($ $n$ $\bigr)$ $:$$=$ $\Biggl($ $\sum\limits_{k= 0}^{n}{ \displaystyle\frac{5^{k} }{ 4^{k} } }$ $=$ $\displaystyle\frac{5^{n + 1}}{ 4^{n} }$ $-$ $4$ $\Biggr)$ e $P$$\bigl($  $n$ $+$ $1$ $\bigr)$ $:$$=$ $\Biggl($ $\sum\limits_{k= 0}^{n + 1}{ \displaystyle\frac{5^{k} }{ 4^{k} } }$ $=$ $\displaystyle\frac{5^{n + 2}}{ 4^{n + 1} }$ $-$ $4$ $\Biggr)$

Per far ciò assumiamo vera la nostra ipotesi induttiva e procediamo spezzando la somma in questo modo :

$\sum\limits_{k= 0}^{n + 1 }{ \displaystyle\frac{5^{k} }{ 4^{k} } }$ $=$ $\Biggl($ $\sum\limits_{k= 0}^{n }{ \displaystyle\frac{5^{k} }{ 4^{k} } }$  $\Biggr)$ $+$  $\displaystyle\frac{ 5^{n+1} }{ 4^{n+1} }$

Ma per l'ipotesi induttiva sappiamo che :     $\sum\limits_{k= 0}^{n}{ \displaystyle\frac{5^{k} }{ 4^{k} } }$ $=$ $\displaystyle\frac{5^{n + 1}}{ 4^{n} }$ $-$ $4$    Ne consegue che :

$\sum\limits_{k= 0}^{n + 1 }{ \displaystyle\frac{5^{k} }{ 4^{k} } }$ $=$ $\displaystyle\frac{ 5^{n+1} }{ 4^{n} }$ $-$ $4$ $+$ $\displaystyle\frac{ 5^{n+1} }{ 4^{n+1} }$  $\iff$ $\sum\limits_{k= 0}^{n + 1 }{ \displaystyle\frac{5^{k} }{ 4^{k} } }$ $=$ $\displaystyle\frac{ 5^{n+1} \cdot 5 }{ 4^{n + 1} }$ $-$ $4$ $=$ $\displaystyle\frac{ 5^{n+2} }{ 4^{n + 1} }$ $-$ $4$

Ma questo è ciò che volevamo dimostrare. Dunque la proprietà e verificata per tutti i numeri naturali.

"P" e "p" come proposizione, non come polinomio; "≡" come definito o equivalente.
------------------------------
La tesi
* P(n) ≡ Σ [k = 0, n] 5^k/4^k = 5^(n + 1)/4^n - 4 = 5*(5/4)^n - 4
è l'istanza p(4, n) della generica identità
* p(m, n) ≡ Σ [k = 0, n] ((m + 1)/m)^k = (m + 1)*((m + 1)/m)^n - m
---------------
Per la tesi generalizzata si ha, con due o tre calcoletti,
* p(m, 0) ≡ 1 = (m + 1)*1 - m: Vera
* p(m, 1) ≡ 1 + (m + 1)/m = (m + 1)*((m + 1)/m)^1 - m: Vera
* p(m, 2) ≡ 1 + (m + 1)/m + ((m + 1)/m)^2 = (m + 1)*((m + 1)/m)^2 - m: Vera
la VERIFICA DEL CASO BASE.
------------------------------
PER IL CASO INDUTTIVO
Ipotesi: p(m, n) è vera
Tesi: p(m, n) → p(m, n + 1)
Dimostrazione:
---------------
A) Costruzione del primo membro di p(m, n + 1)
* Σ [k = 0, n + 1] ((m + 1)/m)^k =
= (Σ [k = 0, n] ((m + 1)/m)^k) + ((m + 1)/m)^(n + 1) =
= ((m + 1)*((m + 1)/m)^n - m) + ((m + 1)/m)^(n + 1) =
= (m + 1)*((m + 1)/m)^n + ((m + 1)/m)*((m + 1)/m)^n - m =
= (m + 1 + (m + 1)/m)*((m + 1)/m)^n - m =
= ((m + 1)^2/m)*((m + 1)/m)^n - m
---------------
B) Sviluppo del secondo membro di p(m, n + 1)
* (m + 1)*((m + 1)/m)^(n + 1) - m =
= (m + 1)*((m + 1)/m)*((m + 1)/m)^n - m =
= ((m + 1)^2/m)*((m + 1)/m)^n - m
---------------
C) CONCLUSIONE
Per la dimostrata eguaglianza delle espressioni finali dei punti A e B, e per la verificata verità del caso base, la tesi generalizzata risulta dimostrata per induzione. Ne deriva la verità della tesi particolare per m = 4.