Esercizi: Dimostrazioni per induzione

Verifica che la formula $1 + 2 + \dots + n = \dfrac{n(n+1)}{2}$ è vera per $n = 1$, $n = 2$ e $n = 5$.

Per la proprietà $P(n)$: «$2^n > n$», scrivi il passo base per $n = 1$ e l'enunciato dell'ipotesi induttiva e della tesi induttiva per il passo $n \to n+1$.

Calcola la somma dei primi 6 numeri dispari e verifica che coincide con $6^2$.

Dimostra per induzione che per ogni $n \ge 1$:

$1 + 3 + 5 + \dots + (2n-1) = n^2$

Dimostra per induzione che per ogni $n \ge 1$ il numero $4^n - 1$ è divisibile per 3.

Dimostra per induzione che per ogni $n \ge 1$:

$1^2 + 2^2 + \dots + n^2 = \dfrac{n(n+1)(2n+1)}{6}$

Dimostra per induzione che $2^n > n^2$ per ogni intero $n \ge 5$. Spiega perché il passo base non può essere $n=1$.

Dimostra per induzione la disuguaglianza di Bernoulli: per $x > -1$ e ogni intero $n \ge 1$ vale $(1+x)^n \ge 1 + nx$.

Considera la «dimostrazione» seguente: «Tutti i cavalli di un gruppo di $n$ cavalli hanno lo stesso colore». Base: $n=1$ vera. Passo: dati $n+1$ cavalli, togliendone uno i restanti $n$ hanno lo stesso colore; togliendone un altro idem; quindi tutti hanno lo stesso colore. Individua l'errore nel passo induttivo e spiega per quale valore di $n$ il ragionamento fallisce.