backup del Post

Induzione alla rovescia

Probabilmente sapete cos’è l’induzione matematica: un processo per cui per dimostrare che una proprietà vale per tutti i numeri interi la si dimostra in un caso particolare, tipicamente per n=1, e poi si dimostra che se vale per k allora vale per k+1. Tutto qua, il lavoro è finito. Infatti, preso un numero grande a piacere, ci si arriverà passo passo: quello che conta è avere abbastanza pazienza. Ci sono anche alcune varianti dell’induzione: per esempio, si può partire da un numero maggiore di 1 (per esempio per dimostrare che la somma degli angoli di un n-gono è n−2 angoli piatti bisogna per forza partire dai triangoli); oppure per dimostrare che la proprietà vale per k+1 si può chiedere come ipotesi che essa sia valida per tutti i numeri da 1 a k. Ma fondamentalmente non cambia molto. Quello che si fa è andare verso l’alto: usare numeri sempre maggiori. Un’induzione alla rovescia non può funzionare: che senso avrebbe tornare all’indietro, se dobbiamo arrivare fino all’infinito? Infinito meno uno che cos’è? Beh: esiste un caso in cui si fa effettivamente induzione all’indietro!

Cauchy, nel suo Cours d’analyse, ha usato l’induzione alla rovescia per dimostrare che la media aritmetica di n numeri positivi, cioè la loro somma divisa per n, è sempre maggiore o uguale della loro media geometrica, vale a dire la radice n-sima del loro prodotto. Ecco la sua dimostrazione. Per cominciare, se abbiamo due numeri a e b, sappiamo che il quadrato della loro differenza, essendo un quadrato, è maggiore o uguale a zero:

(a − b)² ≥ 0

Facendo la moltiplicazione, spostando il termine 2ab e dividendo per due otteniamo

(a² + b²)/2 ≥ ab

Abbiamo così dimostrato la nostra ipotesi per due numeri positivi qualsiasi a² e b² (non devo spiegare perché sono “qualsiasi”, vero?). Primo passo fatto.

Il secondo passo induttivo mostra come raddoppiando il numero di termini la disuguaglianza vale ancora. Se sappiamo che

(a₁ + a₂ + … + a_n)/n ≥ ⁿ√(a₁a₂ … a_n)

possiamo sostituire a tutti gli a_i l’espressione (a_i1 + a_i2)/2. A sinistra abbiamo la media aritmetica di 2n termini; a destra, sostituendo a ciascuno dei (a_i1 + a_i2)/2 il minor valore √(a_i1a_i2), otteniamo la media geometrica di 2n termini. Insomma sappiamo che la nostra ipotesi è vera per n = 2, 4, 8, 16, 32 … E per gli altri valori? Si torna indietro!

Riprendiamo la nostra formula per n generico, cioè

(a₁ + a₂ + … + a_n)/n ≥ ⁿ√(a₁a₂ … a_n)

e sostituiamo a a_n la media aritmetica degli altri n−1 elementi. Il lato sinistro dell’uguaglianza diverrà la media aritmetica dei primi n−1 elementi; il fattore che rimane nel lato destro si elimina elevando prima ambo i membri alla potenza n e semplificando. Prendendo infine la radice n−1-sima otteniamo la nostra tesi induttiva. Un po’ di montagne russe, insomma, e abbiamo tutto!