Principio di induzione – Esercizi

Home » Principio di induzione – Esercizi

In questo articolo presentiamo una raccolta di esercizi sul principio di induzione.

Il principio di induzione è una proprietà fondamentale dell’insieme $\mathbb{N}$ numeri naturali: esso afferma che se abbiamo un sottoinsieme $U$ di $\mathbb{N}$ contenente lo $0$ e con la proprietà che, se un certo $n$ vi appartiene, allora anche il numero successivo $n+1$ appartiene a $U$ , allora $U$ contiene tutti i numeri naturali. Questa proprietà, a prima vista molto semplice, consente in realtà di dimostrare moltissime proprietà dei numeri naturali e di risolvere numerosi problemi che riguardano tale insieme. In alcune formulazioni dell’aritmetica, esso è infatti il solo strumento dimostrativo di cui $\mathbb{N}$ viene dotato.

In questo articolo presentiamo 55 esercizi di carattere vario, risolti mediante l’applicazione del principio di induzione e le sue varianti. Gli esercizi sono corredati di una o più soluzioni complete, così da offrire al lettore la possibilità di formare la sua attitudine a distinguere quale tecnica sia la più conveniente, nell’affrontare un problema.

Oltre nostro articolo sul principio di induzione per la teoria, consigliamo il seguente materiale su argomenti correlati:

Buona lettura!

Sommario

Leggi...

Questo articolo è una raccolta di esercizi che si possono svolgere applicando il principio d’induzione, di natura e livello di difficoltà vari. Gli argomenti spaziano dalla diretta applicazione del principio alla sua evoluzione in contesti meno classici.

Autori e revisori

Leggi...

Autori: Valerio Brunetti, Chiara Gambicchia, Silvia Lombardi.

Revisori: Valerio Brunetti.

Notazioni

Leggi...

$\mathbb{N}$	Insieme dei numeri naturali;
$\mathbb{Z}$	Insieme dei numeri interi relativi;
$\sum_{k=i}^na_k$	Somma degli elementi $a_k$ al variare dell’indice $k=i\dots n$ ;
$\prod_{k=i}^na_k$	Prodotto degli elementi $a_k$ al variare dell’indice $k=i\dots n$ ;
$\lfloor x \rfloor$	Parte intera inferiore di $x$ ;
$\dfrac{d^nf}{dx^n}(x)$	Derivata $n$ -esima della funzione $f$ calcolata in $x$ .

Introduzione

Leggi...

Questo documento è una raccolta di esercizi dedicati all’applicazione del principio d’induzione. La difficoltà degli esercizi proposti è variegata, in quanto l’obiettivo è quello di imparare ad applicare tale principio in situazioni di complessità diversa. Pertanto si troveranno sia esercizi molto semplici, il cui scopo è quello di interiorizzare il principio d’induzione e capire bene il meccanismo di applicazione, sia esercizi più impegnativi, che puntano a esprimere tutta la potenza dell’induzione da un punto di vista anche più concettuale. Tuttavia, gli esercizi nella dispensa non sono ordinati per difficoltà crescente, ma per tematica e tipologia. Orientativamente l’ordine dei temi dei problemi è il seguente:

$\quad$

sommatorie;

disuguaglianze;

produttorie;

divisibilità;

formule chiuse;

successioni definite per ricorrenza;

“curiosità”.

Lasciatevi sfidare dagli esercizi più divertenti nella raccolta e buon lavoro!

Richiami di teoria

Leggi...

Richiamiamo in questa sezione gli enunciati principali (senza dimostrazioni) riguardanti il principio d’induzione e le sue applicazioni.

Il principio d’induzione, nella sua forma più astratta e generale, afferma che l’insieme dei numeri naturali $\mathbb{N}$ è il più piccolo insieme induttivo, cioè ogni sottoinsieme induttivo (ossia soddisfacente le proprietà dell’elenco sottostante) di $\mathbb{N}$ coincide con $\mathbb{N}$ stesso. In formule quindi l’enunciato è il seguente:

Teorema 1.1 (principio d’induzione). Sia $U\subseteq \mathbb{N}$

tale che

$\quad$

$0\in U;$

$n\in U\implies n+1\in U$ ; ossia se $n$ appartiene all’insieme $U$ , allora anche $n+1$ appartiene a $U$ .

Allora $U=\mathbb{N}$ .

$\quad$

All’atto pratico, questo principio si può applicare per verificare che una data proprietà $\mathcal{P}$ valga per tutti i numeri naturali, semplicemente dimostrando che l’insieme degli $n$ per cui tale proprietà è valida è un insieme induttivo. La verifica avviene in due passi, il passo base e il passo induttivo, ed è formalizzata come segue:

Corollario 1.2 (induzione). Sia $\mathcal{P}(n)$

una proposizione sui numeri naturali tale che

$\quad$

(passo base) $\mathcal{P}(0)$ è verificata;

(passo induttivo) per ogni $n\in\mathbb{N}$ vale l’implicazione $\mathcal{P}(n)\implies\mathcal{P}(n+1)$ .

Allora $\mathcal{P}(n)$ è verificata per ogni $n\in\mathbb{N}$ .

$\quad$

In realtà, non è necessario che il punto di partenza sia proprio $0$ ; se vogliamo infatti dimostrare che solo per i numeri naturali da un certo punto in poi, ovvero per tutti gli $n$ più grandi di un certo elemento iniziale $n_0$ , si può applicare la seguente versione del principio d’induzione generalizzata.

Teorema 1.3 (induzione generalizzata). Sia $\mathcal{P}(n)$

una proposizione sui numeri naturali tale che

$\quad$

(passo base) esiste $n_0\in \mathbb{N}$ per cui $\mathcal{P}(n_0)$ è verificata;

(passo induttivo) per ogni $n\in\mathbb{N}$ tale che $n\ge n_0$ , vale l’implicazione $\mathcal{P}(n)\implies\mathcal{P}(n+1)$ .

Allora $\mathcal{P}(n)$ è verificata per ogni naturale $n\ge n_0$ .

$\quad$

In alcune circostanze, per mostrare $\mathcal{P}(n+1)$ occorre sapere che $\mathcal{P}$ è verificata per tutti i numeri fino ad $n$ . In tal caso possiamo avvalerci del principio di induzione forte seguente.

Teorema 1.4 (induzione forte generalizzata). Sia $\mathcal{P}(n)$

una proposizione sui numeri naturali tale che

$\quad$

(passo base) esiste $n_0\in \mathbb{N}$ per cui $\mathcal{P}(n_0)$ è verificata;

(passo induttivo) per ogni $n\in\mathbb{N}$ tale che $n\ge n_0$ , vale l’implicazione
$\mathcal{P}(k)\; \forall k\leq n\implies\mathcal{P}(n+1).$

Allora $\mathcal{P}(n)$ è verificata per ogni naturale $n\ge n_0$ .

$\quad$

Per approfondire questi risultati e le relative dimostrazioni consigliamo la lettura del materiale messo a disposizione dal team di Qui Si Risolve che potete trovare alle seguenti pagine:

– Il principio di induzione;

– Teoria degli insiemi numerici.

Esercizi

$\quad$

Esercizio 1 $(\bigstar\largewhitestar\largewhitestar\largewhitestar\largewhitestar)$

. Dimostrare la seguente formula, valida per ogni $n$

naturale:

$\mathcal{P}(n):\quad \sum_{k=1}^n k = \dfrac{n(n+1)}{2}.$

Svolgimento.

Per dimostrare che $\mathcal{P}(n)$

è vera per ogni $n\ge 1$

applichiamo il principio di induzione.

Passo base: Mostriamo che $\mathcal{P}(1)$ è vera.

$1 = 1 \,\, \checkmark$

Passo induttivo: Per ipotesi induttiva supponiamo vera $\mathcal{P}(n)$ per un certo $n \geq 1$ e mostriamo che vale $\mathcal{P}(n+1)$ . Osserviamo dunque che

$\sum_{k=1}^{n+1} k = \left(\sum_{k=1}^n k\right) + (n+1) \overset{*}{=} \dfrac{n(n+1)}{2} + n+1 = \dfrac{n(n+1)+2(n+1)}{2} = \dfrac{(n+1)(n+2)}{2},$

dove in $*$ abbiamo usato l’ipotesi induttiva.

Per il principio di induzione, la formula risulta provata.

Esercizio 2 $(\bigstar\largewhitestar\largewhitestar\largewhitestar\largewhitestar)$

. Dimostrare la seguente formula, valida per ogni $n$

naturale:

$\mathcal{P}(n):\quad \sum_{k=1}^n \left(2k-1 \right) = n^2.$

Svolgimento.

Per dimostrare che $\mathcal{P}(n)$

è vera per ogni $n\ge 1$

applichiamo il principio di induzione.

Passo base: mostriamo che $\mathcal{P}(1)$ è vera.

$1 = 1 \,\, \checkmark$

Passo induttivo: per ipotesi induttiva supponiamo vera $\mathcal{P}(n)$ per un certo $n \geq 1$ e mostriamo che vale $\mathcal{P}(n+1)$ . Osserviamo dunque che

$\sum_{k=1}^{n+1}\left(2k-1 \right)= \sum_{k=1}^{n}\left(2k-1 \right)+\left(2 \left(n+1\right) -1 \right) \overset{*}{=}n^2+2n+2-1=n^2+2n+1=\left(n+1 \right)^2,$

dove in $*$ abbiamo usato l’ipotesi induttiva.

Per il principio di induzione, la formula risulta provata.

Esercizio 3 $(\bigstar\largewhitestar\largewhitestar\largewhitestar\largewhitestar)$

. Dimostrare la seguente formula, valida per ogni $n$

naturale:

$\mathcal{P}(n):\quad \sum_{k=1}^n k^2 = \dfrac{n(n+1)(2n+1)}{6}.$

Svolgimento.

Per dimostrare che $\mathcal{P}(n)$

è vera per ogni $n\ge 1$

applichiamo il principio di induzione.

Passo base: mostriamo che $\mathcal{P}(1)$ è vera.

$1 = 1 \,\, \checkmark$

Passo induttivo: mostriamo che $\mathcal{P}(n)\implies \mathcal{P}(n+1)$ , cioè dimostriamo $\mathcal{P}(n+1)$ ipotizzando la validità di $\mathcal{P}(n)$ . A tal fine osserviamo che

$\begin{aligned} \sum_{k=1}^{n+1} k^2 & = \sum_{k=1}^n k^2 + (n+1)^2 =\\ &\overset{*}{=} \dfrac{n(n+1)(2n+1)}{6} + (n+1)^2 = \\ & = \dfrac{(n+1)\big(n(2n+1)+6(n+1)\big)}{6} =\\ & = \dfrac{(n+1)\left(2n^2+7n+6\right)}{6} = \\ & \overset{\diamondsuit}{=} \dfrac{(n+1)(n+2)(2n+3)}{6}, \end{aligned}$

dove in $*$ abbiamo usato l’ipotesi induttiva, mentre in $\diamondsuit$ abbiamo scomposto il trinomio.¹

In virtù del principio di induzione, la proprietà $\mathcal{P}(n)$ è valida per tutti gli $n$ naturali.

Un trinomio del tipo $Ax^2+Bx+C$ con $A,B,C$ reali e $A\neq0$ si scompone come

$Ax^2+Bx+C=A(x-x_1)(x-x_2)$

dove $x_1$ e $x_2$ sono le radici dell’equazione $Ax^2+Bx+C=0$ . ↩

Esercizio 4 $(\bigstar\largewhitestar\largewhitestar\largewhitestar\largewhitestar)$

. Dimostrare la seguente formula, valida per ogni $n\geq 1$

naturale:

$\mathcal{P}(n):\quad \sum_{k=1}^n (2k-1)^2=\dfrac{n(4n^2-1)}{3}.$

Svolgimento.

Dimostriamo la tesi tramite il principio d’induzione.

Passo base: La tesi è vera per $n=1$ , infatti si ha

$1^2=\dfrac{1(4-1)}{3} \quad \checkmark$

Passo induttivo: supponiamo di aver dimostrato la tesi per un certo numero naturale $n$ e deduciamone la validità anche per $n+1$ . Osserviamo intanto che

$(n+1)(4(n+1)^2-1)=(n+1)(2(n+1)-1)(2(n+1)+1)=(n+1)(2n+1)(2n+3);$

quindi ciò che vogliamo dimostrare è che

$\sum_{k=1}^{n+1}(2k-1)^2=\dfrac{(n+1)(2n+1)(2n+3)}{3}=\dfrac{(2n+1)(2n^2+5n+3)}{3}.$

Svolgiamo i conti sfruttando l’ipotesi induttiva nel passaggio $*$ :

$\begin{aligned} \sum_{k=1}^{n+1}(2k-1)^2&=(2n+1)^2+\sum_{k=1}^{n}(2k-1)^2=\\ &\overset{*}{=}(2n+1)^2+\dfrac{n(4n^2-1)}{3}=\\ &=\dfrac{3(2n+1)^2+n(2n-1)(2n+1)}{3}=\\ &=\dfrac{(2n+1)(3(2n+1)+n(2n-1))}{3}=\\ &=\dfrac{(2n+1)(2n^2+5n+3)}{3}. \end{aligned}$

Abbiamo quindi ottenuto l’uguaglianza che volevamo, dimostrando così la validità della proprietà per $n+1$ .

Il principio di induzione quindi implica la tesi dell’esercizio.

Esercizio 5 $(\bigstar\largewhitestar\largewhitestar\largewhitestar\largewhitestar)$

. Dimostrare la seguente formula, valida per ogni $n$

naturale:

$\mathcal{P}(n):\quad \sum_{k=1}^n k^3 = \dfrac{n^2(n+1)^2}{4} .$

Svolgimento.

Per dimostrare che $\mathcal{P}(n)$

è vera per ogni $n\ge1$

applichiamo il principio di induzione.

Passo base: mostriamo che $\mathcal{P}(1)$ è vera.

$1 = 1 \,\, \checkmark$

Passo induttivo: per ipotesi induttiva supponiamo vera $\mathcal{P}(n)$ per un qualche $n \geq 1$ e mostriamo che essa implica $\mathcal{P}(n+1)$ . Osserviamo dunque che

$\begin{aligned} \sum_{k=1}^{n+1} k^3 & = \sum_{k=1}^n k^3 + (n+1)^3 =\\ &\overset{*}{=} \dfrac{n^2(n+1)^2}{4} + (n+1)^3 = \\ & = \dfrac{n^2(n+1)^2+4(n+1)^3}{4} =\\ & =\dfrac{(n+1)^2\left(n^2+4n+4\right)}{4} = \\ & \overset{\diamondsuit}{=} \dfrac{(n+1)^2\left(n+2\right)^2}{4}, \end{aligned}$

dove in $*$ abbiamo usato l’ipotesi induttiva, mentre in $\diamondsuit$ abbiamo scomposto il trinomio.²

Per induzione, la proprietà $\mathcal{P}(n)$ è valida per tutti gli $n$ naturali.

Si osserva che $n^2+4n+4$ è un quadrato di binomio, ovvero $n^2+4n+4=(n+2)^2$ . ↩

Osservazione.

Confrontando le formule di questo esercizio e dell’esercizio 2, si ottiene che per ogni numero naturale $n\ge 1$

vale

$\sum_{k=1}^{n}k^3=\left(\sum_{k=1}^n k\right)^2.$

Esercizio 6 $(\bigstar\largewhitestar\largewhitestar\largewhitestar\largewhitestar)$

. Dimostrare la seguente formula, valida per ogni $n\geq 1$

naturale:

$\mathcal{P}(n):\quad \sum_{k=1}^n (2k-1)^3=n^2(2n^2-1).$

Svolgimento.

Per dimostrare la tesi procediamo per induzione.

Passo base: la tesi è vera per $n=1$ , infatti

$1^3=1=1^2(2\cdot1^2-1). \quad\checkmark$

Passo induttivo: supponiamo per ipotesi induttiva che $\mathcal{P}(n)$ sia vera e dimostriamo $\mathcal{P}(n+1)$ . Osserviamo che l’ipotesi induttiva (nel passaggio $*$ ) ci porta a

(1) $\begin{equation*} \begin{aligned} \sum_{k=1}^{n+1}(2k-1)^3&=(2n+1)^3+\sum_{k=1}^{n}(2k-1)^3=\\ &\overset{*}{=}(2n+1)^3+n^2(2n^2-1)=\\ &=2n^4+8n^3+11n^2+6n+1. \end{aligned} \end{equation*}$

D’altra parte, possiamo verificare che

$(n+1)^2(2(n+1)^2-1)=(n^2+2n+1)(2n^2+4n+1)=2n^4+8n^3+11n^2+6n+1,$

che, insieme a (1), ci dà la tesi.

Esercizio 7 $(\bigstar\bigstar\largewhitestar\largewhitestar\largewhitestar)$

. Dimostrare la seguente formula, valida per ogni $n\geq 0$

naturale:

$\mathcal{P}(n):\quad \sum_{k=0}^n k^4=\dfrac{n(n+1)(2n+1)(3n^2+3n-1)}{30}.$

Svolgimento.

Dimostriamo la tesi tramite il principio d’induzione.

Passo base: verifichiamo che $\mathcal{P}(0)$ sia vera.

$0=0\quad \checkmark$

Passo induttivo: Dimostriamo che $\mathcal{P}(n)\implies\mathcal{P}(n+1)$ . Prima sviluppiamo il prodotto che compare nella tesi:

(2) $\begin{equation*} \begin{aligned} (n+1)(n+2)(2n+3)(3(n+1)^2+3(n+1)-1)&=(n+1)(2n^2+7n+6)(3n^2+9n+5)\\ &=(n+1)(6n^4+39n^3+91n^2+89n+30). \end{aligned} \end{equation*}$

Ora invece partiamo dalla sommatoria e usiamo l’ipotesi induttiva nel passaggio $*$ , trovando

$\sum_{k=0}^{n+1}k^4=(n+1)^4+\sum_{k=0}^{n}k^4\overset{*}{=}\dfrac{30(n+1)^4+n(n+1)(2n+1)(3n^2+3n-1)}{30}.$

Adesso raccogliamo $n+1$ al numeratore e sviluppiamo il resto del prodotto, ottenendo così quanto segue:

$\sum_{k=0}^{n+1}k^4=(n+1)\dfrac{30(n+1)^3+(2n^2+n)(3n^2+3n-1)}{30}=(n+1)\dfrac{6n^4+39n^3+91n^2+89n+30}{30}.$

Combinando questo con (2) abbiamo quindi la tesi.

Esercizio 8 $(\bigstar\largewhitestar\largewhitestar\largewhitestar\largewhitestar)$

. Dimostrare che per ogni $n \ge 2$

naturale vale la seguente uguaglianza:

$\mathcal{P}(n):\quad \sum_{k=2}^n \dfrac{1}{(k-1)k}=\dfrac{n-1}{n}.$

Svolgimento.

Mostriamo due soluzioni per questo esercizio.

Svolgimento diretto.

Osserviamo che possiamo riscrivere il termine generico $a_k$

della sommatoria come

$a_k=\dfrac{1}{k-1}-\dfrac{1}{k}.$

In particolare si può notare che nella sommatoria

$\sum_{k=2}^{n}\dfrac{1}{k-1}-\dfrac{1}{k}$

tutti i termini intermedi si eliminano, lasciando solo il primo e l’ultimo termine; si dice che la serie è telescopica: si rimanda alla soluzione dell’esercizio 14 per una spiegazione più dettagliata di questo meccanismo. Da tale argomentazione segue che

$\sum_{k=2}^{n}\dfrac{1}{(k-1)k}=\sum_{k=2}^{n}\dfrac{1}{k-1}-\dfrac{1}{k}=1-\dfrac{1}{n}= \frac{n-1}{n},$

cioè la tesi.

Svolgimento per induzione.

Per dimostrare che $\mathcal{P}(n)$

è vera per ogni $n\geq 2$

applichiamo il principio di induzione.

Passo base: mostriamo che $\mathcal{P}(2)$ è vera.

$\dfrac{1}{2}=\dfrac{1}{2} \quad \checkmark$

Passo induttivo: per ipotesi induttiva supponiamo vera $\mathcal{P}(n)$ per un certo $n \ge 0$ e mostriamo che essa implica $\mathcal{P}(n+1)$ . Osserviamo che

$\begin{aligned} \sum_{k=2}^{n+1} \dfrac{1}{(k-1)k}&=\dfrac{1}{n(n+1)}+\sum_{k=2}^n \dfrac{1}{(k-1)k}\overset{*}{=}\\ & \overset{*}{=}\dfrac{1}{n(n+1)}+\dfrac{n-1}{n}= \\ & = \dfrac{1+n^2-1}{n(n+1)}=\\ & =\dfrac{n}{n+1}, \end{aligned}$

avendo usato l’ipotesi induttiva nel passaggio $*$ .

Il principio di induzione prova quindi la proprietà $\mathcal{P}(n)$ per ogni naturale $n\ge 2$ .

Esercizio 9 $(\bigstar\bigstar\largewhitestar\largewhitestar\largewhitestar)$

. Dimostrare la seguente formula, valida per ogni $n\geq 1$

naturale:

$\mathcal{P}(n):\quad \sum_{k=2}^n \dfrac{1}{k(k^2-1)}=\frac{1}{4}\left[1-\dfrac{2}{n(n+1)}\right].$

Svolgimento diretto.

La tesi si può ottenere per via diretta osservando che il termine generale della somma si può decomporre come segue:

(3) $\begin{equation*} \begin{split} \sum_{k=2}^{n}\frac{1}{k(k^2-1)} & = \frac{1}{2}\sum_{k=2}^{n} \left(\frac{1}{k(k-1)} - \frac{1}{k(k+1)} \right) \\ & = \frac{1}{2} \left( \frac{1}{2(2-1)} - \frac{1}{n(n+1)} \right) \\ & = \frac{1}{4} \left[1 - \frac{2}{n(n+1)} \right], \end{split} \end{equation*}$

dove la seconda uguaglianza deriva dal fatto che ogni termine col segno negativo per $k$ si cancella con quello positivo relativo all’addendo $k+1$ , ossia la somma è telescopica.

Svolgimento per induzione.

Senza l’osservazione mostrata sopra, la tesi si può dimostrare anche tramite il principio d’induzione.

Passo base: verifichiamo che $\mathcal{P}(2)$ sia vera.

$\frac{1}{2\cdot3}=\frac{1}{6}=\frac{1}{4}\left[1-\frac{2}{2\cdot3}\right]\quad \checkmark$

Passo induttivo: supponiamo per ipotesi induttiva che sia vera $\mathcal{P}(n)$ e dimostriamo che ciò si deduce $\mathcal{P}(n+1)$ .

Partiamo dalla sommatoria e usiamo l’ipotesi induttiva nel passaggio $*$ , trovando

$\begin{aligned} \sum_{k=2}^{n+1}\frac{1}{k(k^2-1)}&=\frac{1}{(n+1)((n+1)^2-1)}+\sum_{k=2}^{n}\frac{1}{k(k^2-1)}=\\ &\overset{*}{=}\frac{1}{4}\left[1-\dfrac{2}{n(n+1)}\right]+\dfrac{1}{(n+1)n(n+2)}=\\ &=\frac{1}{4}\left[1-\dfrac{2}{n(n+1)}+\dfrac{4}{(n+1)n(n+2)}\right]=\\ &=\frac{1}{4}\left[1-\dfrac{2(n+2)-4}{n(n+1)(n+2)}\right]=\\ &=\frac{1}{4}\left[1-\dfrac{2}{(n+1)(n+2)}\right], \end{aligned}$

che è la tesi.

Il principio di induzione implica la conclusione.

Esercizio 10 $(\bigstar\largewhitestar\largewhitestar\largewhitestar\largewhitestar)$

. Dimostrare la seguente formula, valida per ogni $n \ge 1$

naturale:

$\mathcal{P}(n):\quad\sum_{k=1}^{n} 2^k=2^{n+1}-2.$

Svolgimento.

Per dimostrare che $\mathcal{P}(n)$

è vera per ogni $n\geq 1$

applichiamo il principio di induzione.

Passo base: mostriamo che $\mathcal{P}(1)$ è vera.

$2=2(2-1) \iff 2=2 \; \checkmark$

Passo induttivo: Mostriamo l’implicazione $\mathcal{P}(n)\implies \mathcal{P}(n+1)$ . Osserviamo dunque che

$\sum_{k=1}^{n+1} 2^k = 2^{n+1}+ \sum_{k=1}^n 2^k \overset{*}{=} 2^{n+1}+2^{n+1}-2=2\cdot 2^{n+1}-2=2^{n+2}-2,$

avendo usato l’ipotesi induttiva nel passaggio $*$ .

Il principio di induzione consente di concludere che la proprietà $\mathcal{P}(n)$ è vera per ogni $n\in \mathbb{N}$ .

Esercizio 11 – somma di una progressione geometrica $(\bigstar\largewhitestar\largewhitestar\largewhitestar\largewhitestar)$

. Dimostrare la seguente formula, valida per ogni $n\geq 0$

naturale e ogni $x\in \mathbb{R} \setminus 1$

$\mathcal{P}(n):\quad \sum_{k=0}^n x^k=\dfrac{1-x^{n+1}}{1-x}.$

Svolgimento diretto.

Chiamiamo $S(n)=\sum_{k=0}^n x^k$

per ogni $n \in \mathbb{N}$

. Osserviamo moltiplicando per $x$

la sommatoria si ottiene una nuova sommatoria che differisce dalla precedente solo per il primo e l’ultimo termine. Più precisamente si ha

(4) $\begin{equation*} S(n)-xS(n)= 1 - x^{n+1}, \implies S(n)(1-x)= 1- x^{n+1} \implies S(n)=\frac{1- x^{n+1}}{1-x}. \end{equation*}$

Svolgimento per induzione.

Per dimostrare che $\mathcal{P}(n)$

è vera per ogni $n \in \mathbb{N}$

applichiamo il principio di induzione.

Passo base: mostriamo che $\mathcal{P}(0)$ è vera:

$1=\dfrac{1-x}{1-x} \quad \checkmark$

Passo induttivo: supponiamo vera $\mathcal{P}(n)$ per un arbitrario $n \geq 0$ e mostriamo che da tale assunzione si deduce $\mathcal{P}(n+1)$ . Osserviamo che

$\sum_{k=0}^{n+1}x^k=x^{n+1}+\sum_{k=0}^{n}x^k\overset{*}{=}x^{n+1}+\dfrac{1-x^{n+1}}{1-x}=\dfrac{1-x^{n+2}}{1-x},$

dove in $*$ abbiamo usato l’ipotesi induttiva.

Quindi abbiamo provato la formula per induzione.

Esercizio 12 $(\bigstar\largewhitestar\largewhitestar\largewhitestar\largewhitestar)$

. Dimostrare la seguente formula, valida per ogni $n \ge 1$

naturale:

$\mathcal{P}(n):\quad \sum_{k=1}^n \dfrac{k(k+6)}{(k+2)(k+4)} =\dfrac{n(n+1)(3n+11)}{3(n+3)(n+4)}.$

Svolgimento.

Per dimostrare che $\mathcal{P}(n)$

è vera per ogni $n\ge 1$

applichiamo il principio di induzione.

Passo base: mostriamo che $\mathcal{P}(1)$ è vera.

$\dfrac{1\cdot 7}{3 \cdot 5} = \dfrac{1 \cdot 2 \cdot 14}{3 \cdot 4 \cdot 5} \iff \dfrac{7}{15}=\dfrac{7}{15} \quad \checkmark$

Passo induttivo: mostriamo $\mathcal{P}(n)\implies \mathcal{P}(n+1)$ . Osserviamo che

$\begin{aligned} \sum_{k=1}^{n+1} \dfrac{k(k+6)}{(k+2)(k+4)} & = \left(\sum_{k=1}^n \dfrac{k(k+6)}{(k+2)(k+4)}\right) + \dfrac{(n+1)(n+7)}{(n+3)(n+5)} \overset{*}{=}\\ & \overset{*}{=}\dfrac{n(n+1)(3n+11)}{3(n+3)(n+4)} + \dfrac{(n+1)(n+7)}{(n+3)(n+5)} =\\ & = \dfrac{n(n+1)(3n+11)(n+5) +3(n+1)(n+4)(n+7)}{3(n+3)(n+4)(n+5)} = \\ & = \dfrac{(n+1)\big( n(3n+11)(n+5) +3(n+7)(n+4)\big) }{3(n+3)(n+4)(n+5)} =\\ & = \dfrac{(n+1)\left(3n^3+29n^2+88n+84\right) }{3(n+3)(n+4)(n+5)} \overset{\spadesuit}{=}\\ & \overset{\spadesuit}{=} \dfrac{(n+1)\left(n+2\right)(3n+14)(n+3) }{3(n+3)(n+4)(n+5)} =\\ & = \dfrac{(n+1)\left(n+2\right)(3n+14) }{3(n+4)(n+5)} \end{aligned}$

dove in $*$ abbiamo usato l’ipotesi induttiva, mentre in $\spadesuit$ abbiamo utilizzato il teorema di Ruffini.

Quindi per induzione abbiamo provato che la proprietà $\mathcal{P}(n)$ è valida per ogni $n$ naturale.

Esercizio 13 $(\bigstar\largewhitestar\largewhitestar\largewhitestar\largewhitestar)$

. Dimostrare la seguente formula, valida per ogni $n \in\mathbb{N}$

$\mathcal{P}(n):\quad \sum_{k=0}^{n} (k\cdot k!)=(n+1)!-1 .$

Svolgimento.

Per dimostrare che $\mathcal{P}(n)$

è vera per ogni $n\in \mathbb{N}$

applichiamo il principio di induzione.

Passo base: $\mathcal{P}(0)$ è vera, infatti

$0\cdot 0!=1!-1. \quad \checkmark$

Passo induttivo: per ipotesi induttiva supponiamo vera $\mathcal{P}(n)$ per un certo $n \ge 0$ e mostriamo che da ciò discende $\mathcal{P}(n+1)$ . Osserviamo dunque che avendo usato l’ipotesi induttiva nel passaggio $*$ .

Esercizio 14 $(\bigstar\largewhitestar\largewhitestar\largewhitestar\largewhitestar)$

. Dimostrare la seguente formula, valida per ogni $n \ge 1$

naturale:

$\mathcal{P}(n):\quad \sum_{k=1}^n \dfrac{4k^2+2k-1}{(2k+1)!} =1-\dfrac{1}{(2n+1)!}.$

Svolgimento diretto.

Osserviamo che il termine generico $a_k$

della successione nella sommatoria si può riscrivere come segue:

$a_k=\dfrac{4k^2+2k-1}{(2k+1)!}=\dfrac{2k(2k+1)-1}{(2k+1)!}=\dfrac{1}{(2k-1)!}-\dfrac{1}{(2k+1)!}.$

In particolare quindi la sommatoria in questione è in effetti una somma telescopica, cioè una sommatoria della forma

$\sum_{k=1}^n b_{k}-b_{k+1},$

in cui tutti i termini $b_k$ intermedi (con $1\leq k\leq n-1$ ) si cancellano, lasciando solo

(5) $\begin{equation*} \sum_{k=1}^n b_{k}-b_{k+1}=b_1-b_{n+1}. \end{equation*}$

Nel caso in analisi si ha

$b_k=-\dfrac{1}{(2k-1)!},$

perciò applicando la (5) otteniamo

$\sum_{k=1}^n\dfrac{4k^2+2k-1}{(2k+1)!}=1-\dfrac{1}{(2n+1)!},$

cioè la tesi.

Svolgimento per induzione.

Per dimostrare che $\mathcal{P}(n)$

è vera per ogni $n\ge 1$

applichiamo il principio di induzione.

Passo base: mostriamo che $\mathcal{P}(1)$ è vera.

$\dfrac{5}{3!} = 1-\dfrac{1}{3!} \quad \iff \quad \frac{5}{6}=\frac{5}{6} \quad \checkmark$

Passo induttivo: per ipotesi induttiva supponiamo vera $\mathcal{P}(n)$ per un certo $n \ge 1$ e mostriamo che vale $\mathcal{P}(n+1)$ . Osserviamo che

$\begin{aligned} \sum_{k=1}^{n+1} \dfrac{4k^2+2k-1}{(2k+1)!} & = \left(\sum_{k=1}^n \dfrac{4k^2+2k-1}{(2k+1)!}\right) + \dfrac{4(n+1)^2+2(n+1)-1}{(2n+3)!} \overset{*}{=}\\ & \overset{*}{=} 1-\dfrac{1}{(2n+1)!} + \dfrac{4(n+1)^2+2(n+1)-1}{(2n+3)!} =\\ & = 1 + \dfrac{-(2n+2)(2n+3) + 4n^2+8n+4+2n+2-1}{(2n+3)!} = \\ & = 1 - \dfrac{1}{(2n+3)!}, \end{aligned}$

dove in $*$ abbiamo usato l’ipotesi induttiva.

Esercizio 15 $(\bigstar\bigstar\largewhitestar\largewhitestar\largewhitestar)$

. Dimostrare la seguente proprietà, valida per ogni naturale $n\geq1$

$\mathcal{P}(n):\quad \sum_{k=1}^n \dfrac{1}{k^2+10k+24}=\dfrac{11n^2+61n}{60(n+5)(n+6)}.$

Svolgimento.

Proponiamo due soluzioni per questo esercizio.

Svolgimento per induzione.

Per dimostrare che $\mathcal{P}(n)$

è vera applichiamo il principio di induzione.

Passo base: $\mathcal{P}(1)$ è vera poiché

$\dfrac{1}{1+10+24}= \dfrac{72}{60\cdot 6 \cdot 7} \iff \dfrac{1}{35}=\dfrac{1}{35}.\quad \checkmark$

Passo induttivo: mostriamo che $\mathcal{P}(n)\implies \mathcal{P}(n+1)$ ; si ha infatti

$\begin{aligned} \nonumber\sum_{k=1}^{n+1} \dfrac{1}{k^2+10k+24}&=\dfrac{1}{\left(n+1\right)^2+10\left(n+1\right)+24 }+\sum_{k=1}^{n}\dfrac{1}{k^2+10k+24}\overset{\clubsuit}{=}\\ &\nonumber\overset{\clubsuit}{=}\dfrac{1}{n^2+12n+35}+\dfrac{11n^2+61n}{60(n+5)(n+6)}=\\ &\nonumber=\dfrac{1}{\left(n+7\right)\left(n+5\right)}+\dfrac{11n^2+61n}{60\left(n+5\right)\left(n+6\right)}=\\ &\nonumber=\dfrac{60(n+6)+\left(11n^2+61n\right)(n+7)}{60(n+5)(n+6)(n+7)}=\\ &\nonumber=\dfrac{11n^3+138n^2+487n+360}{60(n+5)(n+6)(n+7)}=\\ &\nonumber=\dfrac{\left(11n+72\right)\left(n+1\right)\left(n+5\right)}{60(n+5)(n+6)(n+7)}=\\ &\nonumber=\dfrac{\left(11n+72\right)\left(n+1\right)}{60(n+6)(n+7)}=\\ &\nonumber=\dfrac{\left(n+1\right)\big(11\left(n+1\right)+61\big)}{60\left(n+6\right)\left(n+7\right)}, \end{aligned}$

dove in $\clubsuit$ abbiamo usato l’ipotesi induttiva.

Il principio di induzione prova la validità di $\mathcal{P}(n)$ per ogni $n \in \mathbb{N}$ .

Svolgimento diretto.

Osserviamo che

$\sum_{k=1}^n \dfrac{1}{k^2+10k+24}=\sum_{k=1}^n\dfrac{1}{(k+6)(k+4)}=\sum_{k=1}^n \dfrac{1}{2(k+4)}-\sum_{k=1}^n \dfrac{1}{2(k+6)}.$

In particolare, con un opportuno “shift” degli indici possiamo riscrivere l’ultimo membro come

$\frac{1}{2}\left (\sum_{k=5}^{n+4} \dfrac{1}{k}-\sum_{k=7}^{n+6} \dfrac{1}{k}\right ).$

Allora i termini in comune si cancellano, lasciando solo i termini con $k=5,6$ della prima sommatoria e i termini con $k=n+5,n+6$ della seconda sommatoria. In conclusione abbiamo

$\sum_{k=1}^n \dfrac{1}{k^2+10k+24}=\dfrac{1}{10}+\dfrac{1}{12}-\dfrac{1}{2(n+5)}-\dfrac{1}{2(n+6)}=\dfrac{11n^2+61n}{60(n+5)(n+6)},$

che prova la tesi.

Esercizio 16 $(\bigstar\largewhitestar\largewhitestar\largewhitestar\largewhitestar)$

. Dimostrare la seguente formula, valida per ogni $n \ge 1$

naturale:

$\mathcal{P}(n):\quad \sum_{k=1}^n \left(1-\dfrac{35}{(k+5)(k+6)}\right) = \dfrac{n(6n+1)}{6(n+6)}.$

Svolgimento.

Presentiamo due soluzioni per questo esercizio.

Svolgimento diretto.

Osserviamo che la sommatoria si può spezzare come segue:

(6) $\begin{equation*} \sum_{k=1}^n \left (1-\dfrac{35}{(k+5)(k+6)}\right )=\left (\sum_{k=1}^n 1\right )-35\sum_{k=1}^n\dfrac{1}{(k+5)(k+6)}=n-35\sum_{k=6}^{n+5}\dfrac{1}{k(k+1)}. \end{equation*}$

Arrivati a questo punto, concentriamoci sulla sommatoria rimasta. In particolare notiamo che

(7) $\begin{equation*} \sum_{k=6}^{n+5}\dfrac{1}{k(k+1)}=\sum_{k=6}^{n+5}\left (\dfrac{1}{k}-\dfrac{1}{k+1}\right ) = \dfrac{1}{6}-\dfrac{1}{n+6}=\dfrac{n}{6(n+6)}, \end{equation*}$

dove la seconda uguaglianza deriva dal fatto che la somma è telescopica, ossia l’addendo negativo del termine $k$ -esimo si cancella con l’addendo positivo del termine $(k+1)$ -esimo (si veda anche l’esercizio 14 precedente). Inserendo (7) in (6) risulta quindi

$\sum_{k=1}^n 1-\dfrac{35}{(k+5)(k+6)}=n-35\cdot\dfrac{n}{6(n+6)}=\dfrac{6n^2+36n-35n}{6(n+6)}=\dfrac{n(6n+1)}{6(n+6)}.$

Secondo svolgimento.

Per dimostrare che $\mathcal{P}(n)$

è vera per ogni $n\geq 1$

applichiamo il principio di induzione.

Passo base: $\mathcal{P}(1)$ è vera, infatti

$1-\dfrac{35}{6 \cdot 7} = \dfrac{1 \cdot 7}{6 \cdot 7} \iff 1-\frac{5}{6}=\frac{1}{6}.\qquad \checkmark$

Passo induttivo: per ipotesi induttiva supponiamo vera $\mathcal{P}(n)$ per un certo $n \ge 1$ e mostriamo che ciò implica $\mathcal{P}(n+1)$ . Si ha

$\begin{aligned} \sum_{k=1}^{n+1} \left(1-\dfrac{35}{(k+5)(k+6)}\right) & = \sum_{k=1}^n \left(1-\dfrac{35}{(k+5)(k+6)}\right) + 1-\dfrac{35}{(n+1+5)(n+1+6)} \overset{*}{=}\\ & \overset{*}{=} \dfrac{n(6n+1)}{6(n+6)}+ 1-\dfrac{35}{(n+6)(n+7)} =\\ & = \dfrac{n(6n+1)(n+7)+6(n+6)(n+7)-35\cdot 6}{6(n+6)(n+7)} = \\ & = \dfrac{(n+7)\left( 6n^2+7n+36 \right)-210}{6(n+6)(n+7)} =\\ & = \dfrac{6n^3+49n^2+85n+42}{6(n+6)(n+7)} = \\ & \overset{\diamond}{=} \dfrac{(n+1)(n+6)(6n+7)}{6(n+6)(n+7)} = \\ & = \dfrac{(n+1)(6n+7)}{6(n+7)}, \end{aligned}$

dove in $*$ abbiamo usato l’ipotesi induttiva, mentre in $\diamond$ il numeratore è stato scomposto mediante il teorema di Ruffini.

Per induzione $\mathcal{P}(n)$ è verificata per ogni $n\geq 1$ naturale.

Esercizio 17 $(\bigstar\bigstar\largewhitestar\largewhitestar\largewhitestar)$

. Dimostrare la seguente formula, valida per ogni $n$

naturale:

$\mathcal{P}(n):\quad \sum_{k=1}^n \sin(kx) = \dfrac{\sin\left(\frac{n+1}{2}x\right)}{\sin\left(\frac{x}{2}\right)} \sin \left(\frac{nx}{2}\right), \qquad x \neq 2k\pi.$

Svolgimento.

Riportiamo tre soluzioni diverse per l’esercizio proposto.

Svolgimento diretto.

Ricordiamo la formula di prostaferesi³

(8) $\begin{equation*} \cos a - \cos b = -2\sin\left (\frac{a+b}{2} \right ) \sin\left (\frac{a-b}{2} \right ). \end{equation*}$

Applicandola agli angoli $a=kx+\frac{x}{2}$ e $b=kx - \frac{x}{2}$ e sommando per $k=1,\dots,n$ si ottiene

(9) $\begin{equation*} \sum_{k=1}^{n} \left ( \cos \left (kx+\frac{x}{2}\right ) - \cos \left (kx-\frac{x}{2}\right ) \right ) = -2 \sum_{k=1}^{n}\sin(kx) \sin \left (\frac{x}{2}\right ). \end{equation*}$

La prima sommatoria è telescopica, quindi rimane soltanto il termine positivo per $k=n$ e il termine negativo per $k=1$

(10) $\begin{equation*} \begin{split} \sum_{k=1}^{n} \left ( \cos \left (kx+\frac{x}{2}\right ) - \cos \left (kx-\frac{x}{2}\right ) \right ) & = \cos \left (nx+\frac{x}{2}\right ) - \cos \left (\frac{x}{2}\right ) \\ & = -2 \sin \left ( \frac{n+1}{2}x \right )\sin \left (\frac{nx}{2}\right ), \end{split} \end{equation*}$

dove la seconda uguaglianza segue di nuovo applicando (8). Uguagliando gli ultimi membri di (9) e (10) e dividendo per $-2\sin \left (\frac{x}{2}\right )$ si ottiene la tesi.

Tale identità si può ottenere mediante la formula di addizione del coseno relativa agli angoli $a=\frac{a+b}{2} + \frac{a-b}{2}$ e agli angoli $b=\frac{a+b}{2} - \frac{a-b}{2}$ . ↩

Svolgimento per induzione.

Per dimostrare che $\mathcal{P}(n)$

è vera per ogni $n\ge 1$

applichiamo il principio di induzione.

Passo base: mostriamo che $\mathcal{P}(1)$ è vera.

$\sin x = \dfrac{\sin x}{\sin \frac{x}{2}} \sin \frac{x}{2} \iff \sin x = \sin x. \quad \checkmark$

Passo induttivo: per ipotesi induttiva supponiamo vera $\mathcal{P}(n)$ per un $n$ arbitrario tale che $n \geq 1$ e mostriamo che da ciò segue $\mathcal{P}(n+1)$ . Si ha

(11) $\begin{equation*} \begin{split} \sum_{k=1}^{n+1} \sin(kx) &= \sin\big((n+1)x\big) + \dfrac{\sin\left( \frac{n+1}{2}x\right) }{\sin \left( \frac{x}{2}\right) } \sin\left( \frac{nx}{2} \right) \\ &= \dfrac{\sin((n+1)x) \sin \left( \frac{x}{2}\right) + \sin \left( \frac{n+1}{2}x\right) \; \sin \left( \frac{nx}{2}\right) }{\sin\left( \frac{x}{2}\right) } \\ &= \dfrac{2 \sin\left( \frac{n+1}{2}x \right) \; \cos \left( \frac{n+1}{2}x\right) \; \sin \left( \frac{x}{2}\right) + \sin \left( \frac{n+1}{2}x\right) \;\sin \left( \frac{nx}{2}\right) }{\sin\left(\frac{x}{2}\right) } \\ &= \dfrac{\sin\left( \frac{n+1}{2}x\right)}{\sin \left( \frac{x}{2}\right)} \left[ 2 \cos \left(\dfrac{n+1}{2}x\right) \sin\left(\dfrac{x}{2}\right) + \sin \left( \frac{nx}{2}\right)\right], \end{split} \end{equation*}$

dove la prima uguaglianza segue applicando l’ipotesi induttiva ai primi $n$ termini della sommatoria, la seconda raccogliendo il fattore $\sin\left( \frac{x}{2}\right)$ , la terza uguaglianza deriva dalla formula di duplicazione del seno⁴ per espandere $\sin\big((n+1)x\big)$ , mentre la quarta si ottiene raccogliendo $\sin\left( \frac{n+1}{2}x \right)$ .

Usando la formula di Werner⁵

(12) $\begin{equation*} 2\sin(\alpha)\cos(\beta)=\sin(\alpha+\beta)+\sin(\alpha-\beta) \end{equation*}$

con $\alpha=\frac{x}{2}$ e $\beta=\frac{n+1}{2}x$ si ottiene, nell’ultimo membro di (11),

(13) $\begin{equation*} \begin{aligned} 2 \cos \left(\dfrac{n+1}{2}x\right) \sin\left(\dfrac{x}{2}\right)=\sin\left(\dfrac{x}{2}+\dfrac{n+1}{2}x\right)+\sin\left(\dfrac{x}{2}-\dfrac{n+1}{2}x\right), \end{aligned} \end{equation*}$

ossia la tesi.

Formula di duplicazione del seno: $\sin \left( 2t\right)=2\sin t \cos t$ . ↩

Si può ottenere sommando le formule di addizione del seno per gli angoli $\alpha+\beta$ e $\alpha- \beta$ . ↩

Terzo svolgimento.

Usando l’identità di Eulero $e^{iz} = \cos(z) + i\sin(z)$

, si verifica facilmente che

(14) $\begin{equation*} \sin(z) = \frac{1}{2i}\left(e^{iz}-e^{-iz}\right). \end{equation*}$

Calcolando (14) in $\frac{z}{2}$ , si hanno due formule per $\sin(z/2)$ :

(15) $\begin{equation*} \sin\frac{z}{2} = \frac{e^{iz/2}}{2i} \left(1-e^{-iz}\right) = \frac{e^{-iz/2}}{2i} \left(e^{iz}-1\right), \end{equation*}$

che, invertite, danno

(16) $\begin{equation*} 1-e^{iz} = -2i\, e^{iz/2}\sin\frac{z}{2},\quad\quad 1-e^{-iz} = 2i\, e^{-iz/2}\sin\frac{z}{2}. \end{equation*}$

Procediamo dunque con il provare quanto richiesto:

$\begin{aligned}\label{eq:contodellamadonna} \sum\limits_{k=1}^{n} \sin(kx) & \overset{(\diamond)}{=} \frac{1}{2i}\sum\limits_{k=0}^{n} \left(e^{ikx}-e^{-ikx}\right) =\\ &= \frac{1}{2i}\sum\limits_{k=0}^{n} \left[\left(e^{ix}\right)^k-\left(e^{-ix}\right)^k\right] = \nonumber \\ & \overset{(\star)}{=} \frac{1}{2i}\left[\frac{1-e^{(n+1)ix}}{1-e^{ix}} - \frac{1-e^{-(n+1)ix}}{1-e^{-ix}}\right] = \nonumber \\ & \overset{(\odot)}{=} \frac{1}{2i}\left[ \frac{e^{(n+1)ix/2}\sin\frac{(n+1)x}{2}}{e^{ix/2}\sin\frac{x}{2}} - \frac{e^{-(n+1)ix/2}\sin\frac{(n+1)x}{2}}{e^{-ix/2}\sin\frac{x}{2}} \right] = \nonumber \\ & = \frac{1}{2i}\frac{\sin\frac{(n+1)x}{2}}{\sin\frac{x}{2}} \left[\frac{e^{(n+1)ix/2}}{e^{ix/2}} - \frac{e^{-(n+1)ix/2}}{e^{-ix/2}} \right] = \nonumber \\ & \overset{(\oplus)}{=} \frac{\sin\frac{(n+1)x}{2}}{\sin\frac{x}{2}} \frac{1}{2i} \left(e^{nx/2} - e^{-nx/2} \right) = \nonumber \\ & = \frac{\sin\frac{(n+1)x}{2}}{\sin\frac{x}{2}}\sin\frac{nx}{2}. \end{aligned}$

Alcuni chiarimenti per i passaggi sopra:

( $\diamond$ ) il termine corrispondente a $k = 0$ è nullo, per cui è ininfluente aggiungerlo nella sommatoria, e aiuta al passo successivo;

( $\star$ ) qui è stata utilizzata la somma della serie geometrica di ragione $q = e^{\pm ix}$ , dimostrata nell’esercizio ??:

$\sum_{k=0}^{n} q^k = \frac{1-q^{n+1}}{1-q} = \frac{1-e^{\pm(n+1)ix}}{1-e^{\pm ix}};$

( $\odot$ ) qui sono state utilizzate le formule (16);

( $\oplus$ ) all’interno delle parentesi quadrate, è stato raccolto e semplificato un fattore $e^{\pm ix/2}$ .

Esercizio 18 – disuguaglianza di Bernoulli $(\bigstar\largewhitestar\largewhitestar\largewhitestar\largewhitestar)$

. Dimostrare la seguente disuguaglianza, valida per ogni $n\geq 0$

$\mathcal{P}(n):\quad (1+x)^n\ge1+nx\qquad \text{per}\,\, x \in (-1,+\infty).$

Svolgimento.

Per dimostrare che $\mathcal{P}(n)$

è vera per ogni $n\in \mathbb{N}$

applichiamo il principio di induzione.

Passo base: mostriamo che $\mathcal{P}(0)$ è vera.

$1 \ge 1. \quad \checkmark$

Passo induttivo: Mostriamo che $\mathcal{P}(n)\implies \mathcal{P}(n+1)$ .

$\begin{aligned} (1+x)^{n+1} & = (1+x)^n \cdot (1+x) \\ &\overset{*}{\ge} (1+nx)\cdot(1+x) \\ & = 1+x+nx+nx^2 \\ & = 1 + (n+1)x + nx^2 \\ &\ge 1+(n+1)x, \end{aligned}$

dove in $*$ abbiamo usato l’ipotesi induttiva.

Esercizio 19 $(\bigstar\largewhitestar\largewhitestar\largewhitestar\largewhitestar)$

. Dimostrare la seguente disuguaglianza, valida per ogni $n \ge 1$

naturale:

$\mathcal{P}(n):\quad n^n \ge n!\;.$

Svolgimento.

Presentiamo due soluzioni per questo esercizio.

Svolgimento diretto.

La tesi segue dall’osservazione che $n^n$

e $n!$

sono il prodotto di $n$

fattori e quelli in $n^n$

sono maggiori rispetto a quelli in $n!$

(17) $\begin{equation*} n^n=\underbrace{n\cdot n\cdots n}_{n \text{ volte}} \geq \underbrace{n(n-1)(n-2)\cdots 1}_{n \text{ fattori}} = n! \qquad \forall n \in \mathbb{N}. \end{equation*}$

Svolgimento per induzione.

Per dimostrare che $\mathcal{P}(n)$

è vera per ogni $n\geq 1$

applichiamo il principio di induzione.

Passo base: mostriamo che $\mathcal{P}(1)$ è vera.

$1^1\ge 1! \iff 1\geq 1. \quad \checkmark$

Passo induttivo: per ipotesi induttiva supponiamo vera $\mathcal{P}(n)$ per un $n \ge 1$ e mostriamo che ciò implica $\mathcal{P}(n+1)$ .

$(n+1)^{n+1} = (n+1)^n \cdot (n+1) \overset{\star}{\ge} n^n \cdot (n+1) \overset{*}{\ge} n! \cdot (n+1) = (n+1)!,$

dove in $*$ abbiamo usato l’ipotesi induttiva, mentre in $\star$ utilizziamo il fatto che $n\ge1$ e quindi $(n+1)^n \ge n^n$ .

La formula risulta provata per induzione.

Esercizio 20 $(\bigstar\largewhitestar\largewhitestar\largewhitestar\largewhitestar)$

. Dimostrare la seguente formula, valida per ogni $n \ge 3$

naturale:

$\mathcal{P}(n):\quad n^2>2n+1.$

Svolgimento.

Presentiamo due soluzioni.

Svolgimento diretto.

Notiamo che

$n^2-2n-1=n^2-2n+1-2=(n-1)^2-2$

e l’ultimo membro è positivo per $n \geq 3$ , ottenendo la tesi.

Svolgimento per induzione.

Per dimostrare che $\mathcal{P}(n)$

è vera per ogni $n\in \mathbb{N}$

applichiamo il principio di induzione.

Passo base: mostriamo che $\mathcal{P}(3)$ è vera.

$9 > 7. \quad \checkmark$

Passo induttivo: Mostriamo che $\mathcal{P}(n)\implies \mathcal{P}(n+1)$ .

$\begin{aligned} (n+1)^2 & = n^2 + 2n +1 \overset{*}{>} 2n+ \underbrace{1+2n+1}_{>3}\overset{\diamond}{>}2n+3, \end{aligned}$

dove in $*$ abbiamo usato l’ipotesi induttiva e in $\diamond$ abbiamo utilizzato il fatto che $n\ge3$ .

Osservazione.

Nel passo induttivo sarebbe bastato avere $n\geq 1$

perché la disuguaglianza $\diamond$

fosse valida; tuttavia $\mathcal{P}(0),\ \mathcal{P}(1)$

e $\mathcal{P}(2)$

sono false!

Esercizio 21 $(\bigstar\bigstar\bigstar\largewhitestar\largewhitestar)$

. Trovare il minimo $n_0\in\mathbb{N}$

tale che la seguente disuguaglianza valga per ogni naturale $n\geq n_0$

$\mathcal{P}(n):\quad n! > 2^{n}.$

Svolgimento.

$n!$

e $2^n$

si ottengono come prodotto di $n$

fattori:

(18) $\begin{equation*} n! = \overbrace{n \cdot (n-1) \cdots 2 \cdot 1}^{n \text{ fattori}}, \qquad 2^n = \overbrace{2 \cdot 2 \cdots 2 }^{n \text{ volte}}. \end{equation*}$

Poiché al crescere di $n$ i fattori di $n!$ diventano via via più grandi, mentre quelli di $2^n$ rimangono costantemente $2$ , intuitivamente ci si aspetta che la disuguaglianza nella traccia sia vera per $n$ sufficientemente grande.

Più precisamente, l’unico fattore di $n!$ minore di quelli che compongono $2^n$ è il fattore $1$ . Osserviamo però che, per $n \geq 4$ , $n!$ contiene un fattore $4$ (doppio di $2$ ) che “bilancia” la presenza del fattore $1$ (metà di $2$ ).

Tale osservazione sarebbe sufficiente a concludere la tesi per $n \geq 4$ , grazie a un ragionamento simile a quello indicato nello svolgimento diretto dell’esercizio 19. La dimostrazione per induzione si può invece formalizzare come segue.

Passo base: La disuguaglianza è vera per $n=4$ , infatti

(19) $\begin{equation*} 4!=4 \cdot 3 \cdot 2 \cdot 1 = 24 > 16 = 2^4. \quad \checkmark \end{equation*}$

Passo induttivo: Supponendo vera la disuguaglianza per $n$ , proviamola per $n+1$ .

(20) $\begin{equation*} (n+1)!=(n+1)n!\overset{*}{>}(n+1)2^n, \end{equation*}$

dove in $*$ è stata usata l’ipotesi induttiva.

Il principio di induzione implica che la tesi dell’esercizio è vera per ogni $n \geq 4$ . Poiché la disuguaglianza è falsa per $n=3$ , in quanto $3!=6 < 8=2^3$ , abbiamo che il valore di $n_0$ richiesto è $n_0=4$ .

Esercizio 22 $(\bigstar\bigstar\bigstar\largewhitestar\largewhitestar)$

. Determinare il minimo $n_0\in\mathbb{N}$

tale che per ogni $n \geq n_0$

valga la seguente proprietà:

$\mathcal{P}(n):\quad n^3-4n^2+n-3>0.$

Svolgimento.

Per trovare il minimo $n_0$

per cui valga la disuguaglianza per ogni naturale successivo applichiamo il principio di induzione “al rovescio”: prima proviamo a svolgere il passo induttivo, per capire cosa ci serve affinché funzioni, e successivamente determiniamo il minimo $n$

per cui è valido il passo base.

Passo induttivo: supponiamo di sapere che valga $\mathcal{P}(n)$ vediamo sotto quali ipotesi su $n$ vale $\mathcal{P}(n+1)$ . Osserviamo che

(21) $\begin{equation*} \begin{split} (n+1)^3-4(n+1)^2+n+1-3 &= n^3+3n^2+3n+1-4n^2-8n-4+n+1-3 \\ & \overset{*}{>} 3n^2+3n+1-8n-4+1 \\ & = 3n^2-6n+3 +n-5 \\ & = 3(n-1)^2 +n- 5, \end{split} \end{equation*}$

che è positivo per $n \geq 2$ . Affinché il passo induttivo sia valido, è sufficiente $n\geq 2$ .

Passo base: Cerchiamo $n_0$ per verifica diretta. Il passo precedente ci dice che, non appena troviamo un $N\geq 1$ tale che $\mathcal{P}(N)$ sia valida, per induzione risulterà vera $\mathcal{P}(n)$ per ogni $n\geq N$ .

Osserviamo che la disuguaglianza è falsa per $n=3$ , infatti

$27-36+3-3=-9<0.$

Invece essa è vera per $n=4$ :

$64-64+4-3=1>0,$

quindi $\mathcal{P}(4)$ è valida.

Abbiamo così dimostrato che la proprietà $\mathcal{P}(n)$ è valida per ogni naturale $n\geq 4$ , mentre, poiché $\mathcal{P}(3)$ è falsa, si ha $n_0=4$ .

Esercizio 23 $(\bigstar\bigstar\largewhitestar\largewhitestar\largewhitestar)$

. Dimostrare la seguente formula, valida per ogni $n \ge 5$

naturale:

$\mathcal{P}(n):\quad 2^n>n^2.$

Svolgimento.

Per dimostrare che $\mathcal{P}(n)$

è vera per ogni $n\geq 5$

naturale applichiamo il principio di induzione.

Passo base: mostriamo che $\mathcal{P}(5)$ è vera.

$32 > 25. \quad \checkmark$

Passo induttivo: per ipotesi induttiva supponiamo vera $\mathcal{P}(n)$ per un qualche $n \ge 5$ e mostriamo che da ciò segue $\mathcal{P}(n+1)$ . Osserviamo che

$\begin{aligned} 2^{n+1} & = 2^n \cdot 2 \overset{*}{>} n^2 \cdot 2 = n^2 + n^2 > n^2 + 2n +1=\left(n+1\right)^2, \end{aligned}$

dove in $*$ abbiamo usato l’ipotesi induttiva e nell’ultima disuguaglianza abbiamo sfruttato l’esercizio 20.

Dunque per induzione la disuguaglianza è verificata per ogni $n\geq 5$ naturale.

Esercizio 24 $(\bigstar\bigstar\bigstar\largewhitestar\largewhitestar)$

. Dimostrare la seguente formula, valida per ogni $n \ge 10$

naturale:

$\mathcal{P}(n):\quad 2^n>n^3.$

Svolgimento.

Per dimostrare che $\mathcal{P}(n)$

è vera per ogni $n\ge 10$

applichiamo il principio di induzione.

Passo base: mostriamo che $\mathcal{P}(10)$ è vera:

$2^{10}\ge 10^3 \iff 1024\ge 1000\quad \checkmark$

Passo induttivo: mostriamo che $\mathcal{P}(n)\implies \mathcal{P}(n+1)$ . Si ha

$2^{n+1}=2\cdot2^n\overset{\clubsuit}{\ge}2\cdot n^3,$

dove in $\clubsuit$ abbiamo usato l’ipotesi induttiva. A questo punto per concludere ci basta verificare che $2n^3\ge (n+1)^3$ . Ma questo equivale a dimostrare che

$n^3\ge 3n^2+3n+1,$

cioè, dividendo per $n^3$ entrambi i lati della disuguaglianza,

$1\geq \frac{3}{n}+\frac{3}{n^2}+\frac{1}{n^3}.$

Osserviamo ora che effettivamente, per $n\geq 10$ , il lato destro si stima con

$\frac{3}{n}+\frac{3}{n^2}+\frac{1}{n^3}\leq \frac{3}{10}+\frac{3}{100}+\frac{1}{1000}<1.$

Alternativamente, si poteva osservare che

(22) $\begin{equation*} n^3-3n^2-3n-1 \geq n^3+3n+3n+1 - 6(n^2+2n+1) = (n+1)^2(n+1-6), \end{equation*}$

che è non-negativo per $n \geq 5$ .

$\mathcal{P}(n)$ è dunque dimostrata per ogni $n \geq 10$ .

Esercizio 25 $(\bigstar\largewhitestar\largewhitestar\largewhitestar\largewhitestar)$

. Dimostrare la seguente disuguaglianza, valida per ogni $n \ge 2$

naturale:

$\mathcal{P}(n):\quad 2^n+3^n < 4^n.$

Svolgimento.

Per dimostrare che $\mathcal{P}(n)$

è vera per ogni $n\geq 2$

applichiamo il principio di induzione.

Passo base: mostriamo che $\mathcal{P}(2)$ è vera.

$2^2 + 3^2 < 4^2 \iff 4 + 9 < 16. \quad \checkmark$

Passo induttivo: per ipotesi induttiva supponiamo vera $\mathcal{P}(n)$ per un $n \ge 2$ e mostriamo che da ciò discende $\mathcal{P}(n+1)$ .

$2^{n+1}+3^{n+1}=2\cdot2^n+3\cdot 3^n\overset{\star}{<} 4\cdot\left(2^n+3^n\right)\overset{*}{<}4\cdot4^n=4^{n+1},$

dove in $\star$ abbiamo usato il fatto che $2<4$ e $3<4$ , mentre in $*$ è stata usata l’ipotesi induttiva.

Per induzione, $\mathcal{P}(n)$ è valida per ogni naturale $n\ge 2$ .

Esercizio 26 $(\bigstar\bigstar\largewhitestar\largewhitestar\largewhitestar)$

. Dimostrare la seguente disuguaglianza, valida per ogni $n \ge 1$

naturale:

$\mathcal{P}(n):\quad \sum_{k=1}^n \dfrac{1}{\sqrt{k}} > 2\left(\sqrt{n+1}-1\right).$

Svolgimento.

Per dimostrare che $\mathcal{P}(n)$

è vera per ogni $n\geq 1$

applichiamo il principio di induzione.

Passo base: mostriamo che $\mathcal{P}(1)$ è vera.

$1>2(\sqrt{1+1}-1) \iff 1>2\sqrt{2}-2 \iff \frac{3}{2}>\sqrt{2}.\quad \checkmark$

Passo induttivo: per ipotesi induttiva supponiamo vera $\mathcal{P}(n)$ per un $n \ge 1$ e dimostriamo $\mathcal{P}(n+1)$ . Osserviamo che

$\begin{aligned} \sum_{k=1}^{n+1} \dfrac{1}{\sqrt{k}} & =\left( \sum_{k=1}^n \dfrac{1}{\sqrt{k}}\right) + \dfrac{1}{\sqrt{n+1}} >\\ & \overset{*}{>}\ 2\left(\sqrt{n+1}-1\right) + \dfrac{1}{\sqrt{n+1}} =\\ & = \dfrac{2n+2-2\sqrt{n+1}+1}{\sqrt{n+1}} =\\ & = 2 \left( \dfrac{n+3/2}{\sqrt{n+1}}- \dfrac{\sqrt{n+1}}{\sqrt{n+1}}\right) =\\ & = 2 \left( \dfrac{n+3/2}{\sqrt{n+1}} - 1\right)\geq \\ & \overset{\clubsuit}{\ge} 2 (\sqrt{n+2} - 1), \end{aligned}$

dove in $*$ abbiamo usato l’ipotesi induttiva, mentre in $\clubsuit$ abbiamo utilizzato la maggiorazione

$\dfrac{n+3/2}{\sqrt{n+1}} \ge \sqrt{n+2}.$

Quest’ultima si può verificare direttamente elevando al quadrato entrambi i membri, ottenendo che la disequazione risulta vera per ogni $n \ge 1$ ; un modo più elegante è applicare la disuguaglianza tra la media aritmetica e media geometrica $x,y\ge 0$ vale

$\dfrac{x+y}{2} \ge \sqrt{xy} \qquad \forall x,y \geq 0,$

(la media aritmetica non è mai minore della media geometrica), al caso $x = n+1$ e $y=n+2$ .

$\mathcal{P}(n)$ è dunque provata per induzione.

Esercizio 27 $(\bigstar\bigstar\largewhitestar\largewhitestar\largewhitestar)$

. Dimostrare che per ogni $n$

naturale vale la disuguaglianza:

(23) $\begin{equation*} \mathcal{P}(n):\quad \sum_{k=0}^{n}\dfrac{1}{\left(4k+5\right)^2}<\dfrac{n+1}{3\left(4n+7\right)}. \end{equation*}$

Svolgimento.

Per dimostrare che $\mathcal{P}(n)$

è vera per ogni $n\in \mathbb{N}$

applichiamo il principio di induzione.

Passo base: mostriamo che $\mathcal{P}(0)$ è vera.

$\frac{1}{25}<\frac{1}{21}. \quad \checkmark$

Passo induttivo: Mostriamo che $\mathcal{P}(n)\implies \mathcal{P}(n+1)$ . Assumendo, $P(n)$ vera, si ha

(24) $\begin{equation*} \begin{aligned} \sum_{k=0}^{n+1}\dfrac{1}{\left(4k+5\right)^2}&=\dfrac{1}{\left(4n+9\right)^2}+\sum_{k=0}^{n}\dfrac{1}{\left(4k+5\right)^2}\overset{\clubsuit}{<}\\ &\overset{\clubsuit}{<} \dfrac{1}{\left(4n+9\right)^2}+\dfrac{n+1}{3\left(4n+7\right)} \end{aligned} \end{equation*}$

dove in $\clubsuit$ abbiamo usato l’ipotesi induttiva. Per (24) è sufficiente dimostrare che

$\begin{aligned} \dfrac{1}{\left(4n+9\right)^2}+\dfrac{n+1}{3\left(4n+7\right)}\leq\dfrac{n+2}{3\left(4n+11\right)}, \end{aligned}$

che è equivalente a

$\begin{aligned} \dfrac{3}{\left(4n+9\right)^2}\leq \dfrac{n+2}{4n+11}-\dfrac{n+1}{4n+7} & \iff \dfrac{3}{\left(4n+9\right)^2}\leq \dfrac{3}{\left(4n+7\right)\left(4n+11\right)} \\ & \iff \left(4n+9\right)^2\geq\left(4n+7\right)\left(4n+11\right) \\ & \iff {16n^2 +72 n + 81} \geq 16n^2 +72n + 77, \end{aligned}$

e quest’ultima disuguaglianza è vera per ogni $n \in \mathbb{N}$ .

La proprietà $\mathcal{P}(n)$ è valida per ogni $n\in\mathbb{N}$ .

Esercizio 28 $(\bigstar\largewhitestar\largewhitestar\largewhitestar\largewhitestar)$

. Dimostrare la seguente formula, valida per ogni $n \ge 1$

naturale:

$\mathcal{P}(n):\quad \prod_{k=1}^n \left( 1+\dfrac{3k+4}{k^2+k} \right) = \dfrac{(n+1)(n+2)^2}{4}.$

Svolgimento.

Mostriamo due soluzioni per questo esercizio.

Svolgimento diretto.

Osserviamo che, per ogni $k=1, \dots,n$

il termine generico nella produttoria è pari a

$a_k=1+\dfrac{3k+4}{k^2+k}=\dfrac{k^2+4k+4}{k^2+k}=\dfrac{(k+2)^2}{k(k+1)}.$

Dunque

(25) $\begin{equation*} \prod_{k=1}^n \left( 1+\dfrac{3k+4}{k^2+k}\right) = \prod_{k=1}^n\dfrac{(k+2)^2}{k(k+1)} = \frac{3^2}{1 \cdot 2} \cdot \frac{4^2}{2 \cdot 3} \cdot \frac{5^2}{3 \cdot 4} \cdots \frac{(n+2)^2}{n(n+1)} \end{equation*}$

e in quest’ultimo prodotto tutti i termini si semplificano, tranne i primi due fattori $2$ al denominatore e un fattore $n+1$ e $(n+2)^2$ al numeratore. Ciò mostra direttamente la tesi.

Svolgimento per induzione.

Per dimostrare che $\mathcal{P}(n)$

è vera per ogni $n\geq 1$

applichiamo il principio di induzione.

Passo base: mostriamo che $\mathcal{P}(1)$ è vera.

$1+\dfrac{7}{2} = \dfrac{2\cdot 9}{4} \iff \dfrac{9}{2} = \dfrac{9}{2}. \quad \checkmark$

Passo induttivo: per ipotesi induttiva supponiamo vera $\mathcal{P}(n)$ per un $n \ge 1$ e mostriamo che da ciò segue $\mathcal{P}(n+1)$ .

$\begin{aligned} \prod_{k=1}^{n+1} \left( 1+\dfrac{3k+4}{k^2+k} \right) & =\left( \prod_{k=1}^n \left( 1+\dfrac{3k+4}{k^2+k} \right)\right) \cdot \left(1+\dfrac{3(n+1)+4}{(n+1)^2+(n+1)}\right) \overset{*}{=}\\ & \overset{*}{=} \dfrac{(n+1)(n+2)^2}{4} \cdot \dfrac{(n+1)^2+4(n+1)+4}{(n+1)(n+2)} =\\ & \overset{\star}{=} \dfrac{(n+1)(n+2)^2}{4} \cdot \dfrac{(n+1+2)^2}{(n+1)(n+2)} =\\ & = \dfrac{(n+2)(n+3)^2}{4}, \end{aligned}$

dove in $*$ abbiamo usato l’ipotesi induttiva, mentre in $\star$ abbiamo usato la formula per la scomposizione di un quadrato di binomio rispetto alla variabile $y=n+1$ .

La tesi risulta provata per induzione.

Esercizio 29 $(\bigstar\largewhitestar\largewhitestar\largewhitestar\largewhitestar)$

. Dimostrare la seguente formula, valida per ogni $n \ge 1$

naturale:

$\mathcal{P}(n):\quad \prod_{k=1}^n \left(\dfrac{4}{k}-\dfrac{1}{k+3}\right) =\dfrac{3^n(n+4)}{4n!}.$

Svolgimento.

Proponiamo due soluzioni per questo esercizio.

Svolgimento diretto.

Osserviamo che per ogni $k=1,\dots, n$

il termine generale della produttoria si può esprimere come

$a_k=\dfrac{4}{k}-\dfrac{1}{k+3}=\dfrac{4(k+3)-k}{k(k+3)}=\dfrac{3(k+4)}{k(k+3)}.$

Grazie a questa scrittura, la produttoria risulta essere telescopica, cioè

(26) $\begin{equation*} \prod_{k=1}^n \dfrac{3(k+4)}{k(k+3)} = 3 \frac{\cancel{5}}{1 \cdot 4} \cdot 3\frac{\cancel{6}}{2 \cdot \cancel{5}} \cdots 3 \frac{n+4}{n(\cancel{n+3})} = 3^n \frac{n+4}{4(n!)}, \end{equation*}$

ossia la tesi.

Svolgimento per induzione.

Per dimostrare che $\mathcal{P}(n)$

è vera per ogni $n\geq 1$

applichiamo il principio di induzione.

Passo base: mostriamo che $\mathcal{P}(1)$ è vera.

$\dfrac{4}{1}-\dfrac{1}{4} = \dfrac{3 \cdot 5}{4} \iff \dfrac{15}{4}=\dfrac{15}{4}. \quad \checkmark$

Passo induttivo: per ipotesi induttiva supponiamo vera $\mathcal{P}(n)$ per un certo $n \ge 1$ e dimostriamo $\mathcal{P}(n+1)$ .

$\begin{aligned} \prod_{k=1}^{n+1} \left(\dfrac{4}{k}-\dfrac{1}{k+3}\right) & = \left(\prod_{k=1}^n \left(\dfrac{4}{k}-\dfrac{1}{k+3}\right)\right) \cdot \left(\dfrac{4}{n+1}-\dfrac{1}{n+1+3}\right) \overset{*}{=}\\ & \overset{*}{=} \dfrac{3^n(n+4)}{4n!} \cdot \left(\dfrac{4}{n+1}-\dfrac{1}{n+4}\right)= \\ & = \dfrac{3^n(n+4)}{4n!} \cdot \dfrac{4n+16-n-1}{(n+1)(n+4)} = \\ & = \dfrac{3^n}{4n!} \cdot \dfrac{3(n+5)}{n+1} = \\ % & = \dfrac{3^{n+1}(n+5)}{4n!(n+1)} = \\ & = \dfrac{3^{n+1}(n+1+4)}{4(n+1)!}, \end{aligned}$

dove in $*$ abbiamo usato l’ipotesi induttiva.

Per induzione, $\mathcal{P}(n)$ è vera per ogni $n\geq 1$ .

Osservazione.

Ovviamente anche nella dimostrazione per induzione una possibilità era quella di sfruttare la semplificazione presente nello svolgimento diretto, così da semplificare il passo induttivo.

Esercizio 30 $(\bigstar\largewhitestar\largewhitestar\largewhitestar\largewhitestar)$

. Dimostrare la seguente formula, valida per ogni $n \ge 1$

naturale:

$\mathcal{P}(n):\quad \prod_{k=1}^n \left( \dfrac{2k^2+k}{2k-1} \right) = n! (2n+1).$

Svolgimento.

Mostriamo due possibili soluzioni.

Svolgimento diretto.

Si ha

(27) $\begin{equation*} \prod_{k=1}^n \left( \dfrac{2k^2+k}{2k-1} \right) = \prod_{k=1}^n \frac{k(2k+1)}{2k-1} = n! (2n+1), \end{equation*}$

dove l’ultima uguaglianza deriva dalla presenza del fattore $k$ in ogni termine della produttoria (che dà luogo al risultato finale $n!$ ), mentre il prodotto dei fattori $\frac{2k+1}{2k-1}$ è telescopico, poiché il numeratore della frazione $k$ -esima si semplifica col denominatore della frazione $(k+1)$ -esima.

Svolgimento per induzione.

Per dimostrare che $\mathcal{P}(n)$

è vera per ogni $n\geq 1$

applichiamo il principio di induzione.

Passo base: mostriamo che $\mathcal{P}(1)$ è vera.

$\dfrac{2+1}{2-1} = 1! \; (2+1) \iff 3=3. \quad \checkmark$

Passo induttivo: per ipotesi induttiva supponiamo vera $\mathcal{P}(n)$ per un $n \ge 1$ e proviamo $\mathcal{P}(n+1)$ . Osserviamo che

$\begin{aligned} \prod_{k=1}^{n+1} \left( \dfrac{2k^2+k}{2k-1} \right) & = \left(\prod_{k=1}^n \left( \dfrac{2k^2+k}{2k-1} \right)\right) \cdot \dfrac{2(n+1)^2+(n+1)}{2(n+1)-1} \overset{*}{=}\\ & \overset{*}{=} n! (2n+1) \cdot \dfrac{(n+1)(2n+3)}{2n+1}=\\ & = (n+1)! \; \big(2(n+1)+1\big), \end{aligned}$

dove in $*$ abbiamo usato l’ipotesi induttiva.

Ciò prova la tesi per induzione.

Esercizio 31 $(\bigstar\largewhitestar\largewhitestar\largewhitestar\largewhitestar)$

. Dimostrare la seguente formula, valida per ogni $n \ge 1$

naturale:

$\mathcal{P}(n):\quad \prod_{k=1}^n \left(k+4-\dfrac{6}{k+3}\right) = \dfrac{(n+1)!}{120} (n+4)(n+5)(n+6).$

Svolgimento.

Presentiamo due soluzioni per questo esercizio.

Svolgimento diretto.

Osserviamo che, per ogni $k=1,\dots,n$

, il generico termine $a_k$

della produttoria si può scrivere come segue:

$a_k=k+4-\dfrac{6}{k+3}=\dfrac{k^2+7k+6}{k+3}=\dfrac{(k+1)(k+6)}{k+3}.$

Dunque possiamo riscrivere la produttoria del testo come

$\begin{aligned} \prod_{k=1}^{n}(k+1)\cdot\prod_{k=1}^{n}(k+6)\cdot\prod_{k=1}^{n}\frac{1}{k+3} & = (n+1)! \cdot \frac{(n+6)!}{6!} \cdot \frac{3!}{(n+3)!} \\ & = (n+1)! \cdot \frac{\cancel{(n+3)!}(n+4)(n+5)(n+6)}{\cancel{3!}\cdot 4 \cdot 5 \cdot 6}\cdot \frac{\cancel{3!}}{\cancel{(n+3)!}} \\ & = \frac{(n+1)!}{120}(n+4)(n+5)(n+6). \end{aligned}$

Questo conclude la dimostrazione.

Svolgimento per induzione.

Per dimostrare che $\mathcal{P}(n)$

è vera per ogni $n\geq 1$

applichiamo il principio di induzione.

Passo base: mostriamo che $\mathcal{P}(1)$ è vera.

$1+4 - \dfrac{6}{1+3} = \dfrac{2!}{120} \cdot 5 \cdot 6 \cdot 7 \iff \dfrac{7}{2}=\dfrac{7}{2}. \quad \checkmark$

Passo induttivo: Mostriamo che $\mathcal{P}(n)\implies \mathcal{P}(n+1)$ .

$\begin{aligned} \prod_{k=1}^{n+1} \left(k+4-\dfrac{6}{k+3}\right) & = \left(\prod_{k=1}^n \left(k+4-\dfrac{6}{k+3}\right)\right) \cdot \left(n+1+4-\dfrac{6}{n+1+3}\right) \overset{*}{=}\\ & \overset{*}{=} \dfrac{(n+1)!}{120} (n+4)(n+5)(n+6) \cdot \left(n+5-\dfrac{6}{n+4}\right) =\\ & = \dfrac{(n+1)!}{120} (n+4)(n+5)(n+6) \cdot \left(\dfrac{n^2+9n+14}{n+4}\right) = \\ & = \dfrac{(n+1)!}{120}(n+5)(n+6) \cdot (n+2)(n+7) = \\ & = \dfrac{(n+2)!}{120}(n+5)(n+6)(n+7), \end{aligned}$

dove in $*$ abbiamo usato l’ipotesi induttiva.

Ciò prova la formula per induzione.

Esercizio 32 $(\bigstar\largewhitestar\largewhitestar\largewhitestar\largewhitestar)$

. Dimostrare la seguente formula, valida per ogni $n \ge 1$

naturale:

$\mathcal{P}(n):\quad \prod_{k=1}^n \left( k-1+\dfrac{6}{2k+5} \right) = \dfrac{15(n+1)!}{(2n+3)(2n+5)}.$

Svolgimento.

Presentiamo due soluzioni per questo esercizio.

Svolgimento diretto.

Possiamo riscrivere il termine generico della produttoria come segue:

$a_k=k-1+\dfrac{6}{2k+5}=\dfrac{2k^2+3k+1}{2k+5}=\dfrac{(2k+1)(k+1)}{2k+5}.$

Allora possiamo riformulare la produttoria come

$\begin{equation*} \prod_{k=1}^{n}(k+1)\cdot\prod_{k=1}^{n} \frac{2k+1}{2k+5} \overset{*}{=} (n+1)!\cdot \frac{(2\cdot 1 + 1)(2\cdot 2 + 1)}{(2n+3)(2n+5)} = \frac{15 (n+1)!}{(2n+3)(2n+5)}, \end{equation*}$

dove nel passaggio $*$ abbiamo semplificato i termini intermedi della produttoria.

Svolgimento per induzione.

Per dimostrare che $\mathcal{P}(n)$

è vera per ogni $n\geq 1$

applichiamo il principio di induzione.

Passo base: mostriamo che $\mathcal{P}(1)$ è vera.

$\dfrac{6}{2+5} = \dfrac{15\cdot 2!}{(2+3)(2+5)}\iff \dfrac{6}{7} = \dfrac{6}{7}. \quad \checkmark$

Passo induttivo: per ipotesi induttiva supponiamo vera $\mathcal{P}(n)$ per un $n \ge 1$ e mostriamo che ciò implica $\mathcal{P}(n+1)$ .

$\begin{aligned} \prod_{k=1}^{n+1} \left( k-1+\dfrac{6}{2k+5} \right) & = \left(\prod_{k=1}^n \left( k-1+\dfrac{6}{2k+5} \right) \right) \cdot \left(n+\dfrac{6}{2n+7}\right) \overset{*}{=}\\ & \overset{*}{=} \dfrac{15(n+1)!}{(2n+3)(2n+5)} \cdot \left(n+\dfrac{6}{2n+7}\right)=\\ & = \dfrac{15(n+1)!}{(2n+3)(2n+5)} \cdot \dfrac{2n^2+7n+6}{2n+7}=\\ & = \dfrac{15(n+1)!}{(2n+3)(2n+5)} \cdot \dfrac{(2n+3)(n+2)}{2n+7}=\\ & = \dfrac{15(n+2)!}{(2n+5)(2n+7)}, \end{aligned}$

dove in $*$ abbiamo usato l’ipotesi induttiva.

Esercizio 33 $(\bigstar\bigstar\largewhitestar\largewhitestar\largewhitestar)$

. Dimostrare la seguente formula, valida per ogni $n\geq 1$

naturale:

$\mathcal{P}(n):\quad \prod_{k=1}^{n} \left(k+\dfrac{1}{2}-\dfrac{1}{2k+2}\right)= \dfrac{(2n+3)!!}{3(n+1)2^n}.$

Si ricorda che il semifattoriale (o doppio fattoriale) $n!!$ è definito come il prodotto di tutti i naturali minori o uguali a $n$ aventi la stessa parità di $n$ ; ovvero, ricorsivamente:

(28) $\begin{equation*} n!!= \begin{cases} 1\qquad&\text{se}\ n=0,1\\ n\cdot(n-2)!!\quad&\text{se}\ n\ge 2. \end{cases} \end{equation*}$

Svolgimento.

Proponiamo due soluzioni: una diretta e una per induzione.

Svolgimento diretto.

Partiamo riscrivendo il generico termine $a_k$

della produttoria come segue:

$a_k=k+\dfrac{1}{2}-\dfrac{1}{2k+2}=\dfrac{2k^2+2k+k+1-1}{2(k+1)}=\dfrac{k(2k+3)}{2(k+1)}.$

Inserendo tali scritture nella produttoria otteniamo

$\begin{equation*} \prod_{k=1}^{n}\dfrac{k(2k+3)}{2(k+1)}=\frac{1}{2^n}\underbrace{\left(\prod_{k=1}^{n}\dfrac{k}{k+1}\right)}_{A}\underbrace{\left(\prod_{k=1}^{n}(2k+3)\right)}_{B}. \end{equation*}$

Evidenziamo le seguenti osservazioni.

$\quad$

La produttoria $A$ è una produttoria telescopica, in cui si semplificano tutti i termini intermedi, pertanto $A=\frac{1}{n+1}$ .

La produttoria $B$ è il prodotto di tutti i termini dispari da $5$ a $2n+3$ , quindi è pari al semifattoriale di $2n+3$ a cui manca il fattore $3$ ; in altre parole si ha

$B=\dfrac{(2n+3)!!}{3}.$

Dunque

$\begin{equation*} \prod_{k=1}^{n}a_k=\dfrac{(2n+3)!!}{3(n+1)2^n}. \end{equation*}$

Svolgimento per induzione.

Applichiamo il principio di induzione.

Passo base: $\mathcal{P}(1)$ è vera, infatti

$\dfrac{3}{2}-\dfrac{1}{4} = \dfrac{5 \cdot 3 \cdot 1}{12} \iff \dfrac{5}{4} = \dfrac{5}{4}. \quad\checkmark$

Passo induttivo: mostriamo ora che $\mathcal{P}(n)\implies \mathcal{P}(n+1)$ .

$\begin{aligned} \prod_{k=1}^{n+1} \left(k+\dfrac{1}{2}-\dfrac{1}{2k+2}\right) & = \left(\prod_{k=1}^{n} \left(k+\dfrac{1}{2}-\dfrac{1}{2k+2}\right)\right) \cdot \left(n+\dfrac{3}{2}-\dfrac{1}{2(n+2)}\right) = \\ & \overset{*}{=} \dfrac{(2n+3)!!}{3(n+1)2^n} \cdot \left(\dfrac{2(n+2)n+3(n+2)-1}{2(n+2)}\right) =\\ & = \dfrac{(2n+3)!!}{3(n+1)2^{n+1}} \cdot \left(\dfrac{2n^2+7n+5}{n+2}\right) =\\ & = \dfrac{(2n+3)!!}{3(n+1)2^{n+1}} \cdot \left(\dfrac{(2n+5)(n+1)}{n+2}\right) =\\ & = \dfrac{(2n+5)(2n+3)!!}{3(n+2)2^{n+1}} =\\ & = \dfrac{(2n+5)!!}{3(n+2)2^{n+1}}, \end{aligned}$

dove in $*$ abbiamo usato l’ipotesi induttiva.

Per induzione, la tesi risulta provata.

Esercizio 34 $(\bigstar\bigstar\largewhitestar\largewhitestar\largewhitestar)$

. Dimostrare la seguente formula, valida per ogni $n \ge 1$

naturale:

$\mathcal{P}(n):\quad \prod_{k=1}^n \left(2k-5+\dfrac{26}{k+6}\right) = \dfrac{30(2n-1)!!}{(n+5)(n+6)},$

dove il semifattoriale $n!!$ è definito in (28).

Svolgimento.

Presentiamo due soluzioni per questo esercizio.

Svolgimento diretto.

Possiamo riscrivere il termine generico della produttoria come

$a_k=2k-5+\dfrac{26}{k+6}=\dfrac{2k^2+7k-4}{k+6}=\dfrac{(2k-1)(k+4)}{k+6}.$

Allora possiamo riformulare la produttoria nel modo seguente:

$\begin{equation*} \prod_{k=1}^{n}(k+4)\cdot\prod_{k=1}^{n}\frac{1}{k+6}\cdot\prod_{k=1}^{n}(2k-1) = \frac{(n+4)!}{4!} \cdot \frac{6!}{(n+6)!} \cdot (2n-1)!! =\cdot\dfrac{5\cdot 6 \cdot (2n-1)!!}{(n+5)(n+6)}. \end{equation*}$

Ciò conclude la dimostrazione.

Svolgimento per induzione.

Per dimostrare che $\mathcal{P}(n)$

è vera per ogni $n\geq 1$

applichiamo il principio di induzione.

Passo base: mostriamo che $\mathcal{P}(1)$ è vera.

$2-5+\dfrac{26}{1+6} = \dfrac{30 (2-1)!!}{(1+5)(1+6)} \iff -3+\dfrac{26}{7}=\dfrac{30}{42} \iff \dfrac{5}{7} = \dfrac{5}{7}. \quad \checkmark$

Passo induttivo: per ipotesi induttiva supponiamo vera $\mathcal{P}(n)$ per un certo $n \ge 1$ e dimostriamo $\mathcal{P}(n+1)$ . Osserviamo che⁶

$\begin{aligned} \prod_{k=1}^{n+1} \left(2k-5+\dfrac{26}{k+6}\right) & = \left(\prod_{k=1}^n \left(2k-5+\dfrac{26}{k+6}\right)\right) \cdot \left(2(n+1) - 5+\dfrac{26}{n+1+6}\right) \overset{*}{=}\\ & \overset{*}{=} \dfrac{30(2n-1)!!}{(n+5)(n+6)} \cdot \left(2n-3+\dfrac{26}{n+7}\right) =\\ & = \dfrac{30(2n-1)!!}{(n+5)(n+6)} \cdot \dfrac{(2n-3)(n+7) + 26}{n+7} = \\ & = \dfrac{30(2n-1)!!}{(n+5)(n+6)} \cdot \dfrac{2n^2+11n+5}{n+7} = \\ & = \dfrac{30(2n-1)!!}{(n+5)(n+6)} \cdot \dfrac{(2n+1)(n+5)}{n+7} = \\ & = \dfrac{30(2n+1)!!}{(n+6)(n+7)}, \end{aligned}$

dove in $*$ abbiamo usato l’ipotesi induttiva.

La tesi risulta provata per induzione.

Ricordiamo che

$n!! = \begin{cases} 1 &\qquad n=0,1\\ n \cdot (n-2)!! & \qquad n \ge 2 \end{cases}$

↩

Esercizio 35 $(\bigstar\largewhitesstar\largewhitestar\largewhitestar\largewhitestar)$

. Dimostrare la seguente proprietà, valida per ogni $n \ge 0$

naturale:

$\mathcal{P}(n):\quad n^2+n \;\; \text{è pari}.$

Svolgimento.

Presentiamo due dimostrazioni per questo esercizio.

Svolgimento diretto.

Osserviamo che, per ogni $n\in\mathbb{N}$

, $n^2$

e $n$

hanno la stessa parità (ossia sono entrambi pari oppure entrambi dispari), dunque la loro somma

$n^2+n$

sarà necessariamente pari.

Osservazione.

In alternativa, si poteva notare che

$n^2+n=n(n+1)$

e osservare che almeno uno tra $n$ e $n+1$ deve essere pari.

Svolgimento per induzione.

Per dimostrare che $\mathcal{P}(n)$

è vera per ogni $n\in \mathbb{N}$

applichiamo il principio di induzione.

Passo base: mostriamo che $\mathcal{P}(0)$ è vera.

$0+0=0 \text{ è pari}. \quad \checkmark$

Passo induttivo: mostriamo che $\mathcal{P}(n)\implies \mathcal{P}(n+1)$ .

$\left(n+1\right)^2+\left(n+1\right)=n^2+2n+1+n+1=\underbrace{n^2+n}_{\text{pari per ipotesi induttiva}}+\underbrace{2\left(n+1\right)}_{\text{pari}}.$

Per induzione risulta stabilita la validità della proprietà $\mathcal{P}(n)$ per ogni $n$ naturale.

Osservazione.

Il lettore può notare che la soluzione diretta appare molto più naturale e semplice di quella per induzione. Ciò suggerisce, nella risoluzione di un esercizio, di individuare la tecnica che meglio si presta alla situazione, evitando schemi e procedure preconfezionate, che potrebbero portare a risoluzioni sub-ottimali.

Esercizio 36 $(\bigstar\largewhitestar\largewhitestar\largewhitestar\largewhitestar)$

. Dimostrare il seguente enunciato, valido per ogni $n \ge 0$

naturale

$\mathcal{P}(n):\quad 3^{2n}-1 \;\; \text{è divisibile per } \, 2.$

Svolgimento.

Presentiamo due dimostrazioni per questo esercizio.

Svolgimento diretto.

Osserviamo che ogni potenza di $3$

è dispari, dunque $3^{2n}-1$

è sempre pari.

Svolgimento per induzione.

Per dimostrare che $\mathcal{P}(n)$

è vera applichiamo il principio di induzione.

Passo base: $\mathcal{P}(0)$ è vera, infatti

$0 \text{ è divisibile per } 2.\quad \checkmark$

Passo induttivo: mostriamo che $\mathcal{P}(n)\implies \mathcal{P}(n+1)$ .

$\begin{aligned} 3^{2n+2}-1&=3^{2n+2}-1+3^{2n}-3^{2n}=\\&=3^{2n}\left(3^2-1\right)+3^{2n}-1=\\ &=\underbrace{3^{2n}\cdot 8}_{\text{pari}} + \underbrace{3^{2n}-1}_{\text{pari per ipotesi induttiva}}. \end{aligned}$

$\mathcal{P}(n)$ è provata per induzione per ogni $n \in \mathbb{N}$ .

Esercizio 37 $(\bigstar\largewhitestar\largewhitestar\largewhitestar\largewhitestar)$

. Dimostrare la seguente proprietà, valida per ogni $n \ge 0$

naturale:

$\mathcal{P}(n):\quad n^3-n+6 \;\; \text{è divisibile per } \, 3.$

Svolgimento diretto.

Poiché $6$

è multiplo di $3$

, è sufficiente dimostrare che $n^3-n$

è multiplo di $3$

per ogni $n \in \mathbb{N}$

. A tal fine, osserviamo che

(29) $\begin{equation*} n^3-n=n(n^2-1)=n(n-1)(n+1), \end{equation*}$

che è multiplo di $3$ in quanto è il prodotto di tre numeri naturali consecutivi, pertanto almeno uno di essi è multiplo di $3$ .

Svolgimento per induzione.

Per dimostrare che $\mathcal{P}(n)$

è vera per ogni $n\geq 0$

applichiamo il principio di induzione.

Passo base: $\mathcal{P}(0)$ è vera poiché

$0-0+6=6 \text{ è divisibile per } 3.\quad \checkmark$

Passo induttivo: per ipotesi induttiva supponiamo vera $\mathcal{P}(n)$ per un $n \ge 1$ e dimostriamo che da essa discende $\mathcal{P}(n+1)$ .

$\begin{aligned} (n+1)^3-(n+1)+6 & = n^3 + 3n^2+3n+1 -n-1+6 =\\ & = \underbrace{n^3-n+6}_{\diamondsuit} + \underbrace{3(n^2+n)}_{\bigstar}. \end{aligned}$

Notiamo che il termine $\diamondsuit$ è divisibile per $3$ per ipotesi induttiva, mentre il termine $\bigstar$ è banalmente multiplo di $3$ .

Il principio di induzione prova che $\mathcal{P}(n)$ è valida per ogni $n$ naturale.

Esercizio 38 $(\bigstar\bigstar\largewhitestar\largewhitestar\largewhitestar)$

. Dimostrare la seguente proprietà, valida per ogni $n \ge 0$

naturale:

$\mathcal{P}(n):\quad 4^{2n+1}+3^{n+2} \;\; \text{è divisibile per } \, 13.$

Svolgimento.

Per dimostrare che $\mathcal{P}(n)$

è vera per ogni $n\in \mathbb{N}$

applichiamo il principio di induzione.

Passo base: mostriamo che $\mathcal{P}(0)$ è vera.

$4^1 + 3^2 = 4 + 9 = 13 \; \text{divisibile per } \, 13. \quad \checkmark$

Passo induttivo: mostriamo che $\mathcal{P}(n)\implies \mathcal{P}(n+1)$ .

$\begin{aligned} 4^{2(n+1)+1}+3^{n+1+2} & = 4^{2n+1} \cdot 4^2 + 3^{n+2} \cdot 3 = \\ & \overset{\heartsuit}{=} 4^{2n+1} \cdot 4^2 + 3^{n+2} \cdot 4^2 - 3^{n+2} \cdot 4^2 + 3^{n+2} \cdot 3 = \\ & = 4^2\left( 4^{2n+1}+3^{n+2}\right) +3^{n+2}(-4^2+3) = \\ & = 16 (\underbrace{4^{2n+1}+3^{n+2} }_{\diamondsuit}) - \underbrace{13 \cdot 3^{n+2}}_{\bigstar}, \end{aligned}$

dove in $\heartsuit$ abbiamo aggiunto e sottratto $4^2 \cdot3^{n+2}$ . Notiamo che il termine $\diamondsuit$ è divisibile per $13$ per ipotesi induttiva, mentre il termine $\bigstar$ è banalmente multiplo di $13$ ; pertanto la somma dei due termini è divisibile per $13$ .

Abbiamo provato la validità di $\mathcal{P}(n)$ per ogni $n \in \mathbb{N}$ per induzione.

Esercizio 39 – binomio di Newton $(\bigstar\bigstar\largewhitestar\largewhitestar\largewhitestar)$

. Dimostrare la formula del binomio di Newton:

$\mathcal{P}(n):\qquad (a+b)^n=\sum_{k=0}^{n}\binom{n}{k}a^kb^{n-k}\qquad \forall a,b\in\mathbb{R}\ \ \forall n\in\mathbb{N}.$

Svolgimento.

Dimostriamo la tesi per induzione su $n$

Passo base: l’uguaglianza vale per $n=0$ in quanto

$(a+b)^0=1=\sum_{k=0}^{0}\binom{0}{k}a^kb^{0-k}. \quad\checkmark$

Passo induttivo: Supponiamo per ipotesi induttiva di aver dimostrato la formula di Newton per $(a+b)^n$ e verifichiamo che vale anche per $(a+b)^{n+1}$ . A tale scopo, si ha

$(a+b)^{n+1}=(a+b)(a+b)^n\overset{*}{=}(a+b)\sum_{k=0}^{n}\binom{n}{k}a^kb^{n-k},$

dove abbiamo usato l’ipotesi induttiva per il passaggio $*$ . A questo punto possiamo distribuire il prodotto per $(a+b)$ ed espandere i coefficienti binomiali per riportare l’espressione in un’unica sommatoria come segue dove in $*$ abbiamo usato l’ipotesi induttiva, nella terza uguaglianza abbiamo distribuito il prodotto, nella quarta abbiamo riscritto la prima sommatoria con uno “shift” di indice, nella quinta uguaglianza abbiamo isolato il termine di indice $k=n+1$ nella prima sommatoria e quello di indice $k=0$ nella seconda sommatoria, usando anche $\binom{n}{n}=\binom{n}{0}=1$ , nella sesta uguaglianza abbiamo raccolto i termini simili tra le due sommatorie, mentre nella settima uguaglianza abbiamo usato la nota relazione $\binom{n}{k-1} + \binom{n}{k} = \binom{n+1}{k}$ , dimostrabile mediante la definizione stessa di coefficiente binomiale. Ciò conclude il passo induttivo.

Abbiamo quindi dimostrato per induzione la formula richiesta.

Esercizio 40 – piccolo teorema di Fermat $(\bigstar\bigstar\bigstar\largewhitestar\largewhitestar)$

. Dimostrare che, se $p \in \mathbb{N}$

è un numero primo, per ogni naturale $n$

esiste $q\in \mathbb{N}$

tale che

$n^p=q\cdot p+n.$

Nel linguaggio delle congruenze, ciò si formula anche come $n^p\equiv n\; (\text{mod }p).$

Svolgimento.

Fissiamo un numero primo $p$

e dimostriamo la tesi per induzione su $n$

Passo base: dimostriamo che la tesi è vera per $n=0$ .

$0^p=0\cdot p+0. \quad\checkmark$

Passo induttivo: assumiamo per ipotesi induttiva che la tesi sia valida per $n$ , ossia che

(30) $\begin{equation*} n^p=q \cdot p + n \end{equation*}$

, e dimostriamone la validità per $n+1$ . Sviluppiamo $(n+1)^p$ tramite la formula del binomio di Newton, dimostrata nell’esercizio 39):

(31) $\begin{equation*} (n+1)^p=\sum_{k=0}^{p}\binom{p}{k}n^k 1^{p-k} = \sum_{k=0}^{p}\binom{p}{k}n^k \end{equation*}$

Osserviamo che, ad eccezione dei termini corrispondenti a $k=0$ e $k=p$ , il coefficiente binomiale $\binom{p}{k}$ presenta sempre almeno un fattore $p$ ed è pertanto divisibile per $p$ , infatti nella frazione

$\binom{p}{k}=\dfrac{p(p-1)(p-2)\cdots (p-k+1)}{k(k-1)\cdots 2\cdot 1},$

possiamo notare che il fattore $p$ al numeratore non si semplifica con nessun fattore al denominatore, essendo $p$ primo e tutti i fattori al denominatore strettamente minori di $p$ . Dunque esiste $c \in \mathbb{N}$ tale che

(32) $\begin{equation*} \sum_{k=1}^{p-1}\binom{p}{k}n^k= c \cdot p. \end{equation*}$

Inserendo (30) e (32) in (31), si ottiene

$(n+1)^p = \sum_{k=0}^{p}\binom{p}{k}n^k = 1+ \left(\sum_{k=1}^{p-1}\binom{p}{k}n^k \right ) + n^p = 1 + \big(c \cdot p\big) + \big(q \cdot p + n\big) = (c+q) \cdot p + (n+1),$

che è l’espressione che volevamo ottenere.

Esercizio 41 $(\bigstar\bigstar\bigstar\largewhitestar\largewhitestar)$

. Dimostrare le seguenti formule trigonometriche per il seno e il coseno di $nx$

per $x\in \mathbb{R}$

e $n\in \mathbb{N}$

$\begin{aligned} \sin(nx)&=\sum_{r=0}^{\left\lfloor\frac{n-1}{2}\right\rfloor}(-1)^r \binom{n}{2r+1} \cos^{n-2r-1}(x) \sin^{2r+1}(x);\\ \cos(nx)&=\sum_{r=0}^{\left\lfloor\frac{n}{2}\right\rfloor} (-1)^r \binom{n}{2r} \cos^{n-2r}(x) \sin^{2r}(x). \end{aligned}$

Svolgimento.

Dimostriamo la tesi per induzione su $n$

Passo base: poniamo $n=0$ e verifichiamo la validità della tesi in questo caso, infatti

$\sum_{r=0}^{\left\lfloor\frac{-1}{2}\right\rfloor}(-1)^r \binom{0}{2r+1} \cos^{-2r-1}(x) \sin^{2r+1}(x) = 0 = \sin(0),$

dove la somma è nulla in quanto è svolta su un insieme vuoto di indici. Si ha inoltre

$\sum_{r=0}^{\left\lfloor\frac{0}{2}\right\rfloor} (-1)^r \binom{0}{2r} \cos^{-2r}(x) \sin^{2r}(x)=1 = \cos(0),$

che completa quindi il passo base dell’induzione.

Passo induttivo: supponiamo di aver dimostrato le due formule per $n$ e dimostriamone la validità per $n+1$ . Svolgeremo i calcoli solo per la formula del seno, essendo questi assolutamente analoghi nel caso del coseno. Partiamo sviluppando la formula del seno della somma:

$\begin{aligned} \sin((n+1)x)=\sin(nx+x)=\sin(nx)\cos(x)+\cos(nx)\sin(x). \end{aligned}$

Ora possiamo usare l’ipotesi induttiva per sviluppare il seno e il coseno di $nx$ :

(33) $\begin{equation*} \begin{aligned} \sin(nx)\cos(x)+\cos(nx)\sin(x) & = \cos(x)\cdot\sum_{r=0}^{\left\lfloor\frac{n-1}{2}\right\rfloor}(-1)^r \binom{n}{2r+1} \cos^{n-2r-1}(x) \sin^{2r+1}(x) \\ & \quad +\sin(x)\cdot\sum_{r=0}^{\left\lfloor\frac{n}{2}\right\rfloor} (-1)^r \binom{n}{2r} \cos^{n-2r}(x) \sin^{2r}(x)= \\ &=\sum_{r=0}^{\left\lfloor\frac{n-1}{2}\right\rfloor}(-1)^r \binom{n}{2r+1} \cos^{n-2r}(x) \sin^{2r+1}(x)\\ &\quad +\sum_{r=0}^{\left\lfloor\frac{n}{2}\right\rfloor} (-1)^r \binom{n}{2r} \cos^{n-2r}(x) \sin^{2r+1}(x). \end{aligned} \end{equation*}$

Distinguiamo ora due casi in base alla parità di $n$ .

$\quad$

Se $n$ è dispari, si ha $\left\lfloor\frac{n-1}{2}\right\rfloor=\left\lfloor\frac{n}{2}\right\rfloor = \frac{n-1}{2}$ e quindi le ultime due sommatorie di (33) hanno lo stesso numero di termini: usando la nota relazione $\binom{n}{2r}+ \binom{n}{2r+1}= \binom{n+1}{2r+1}$ (dimostrabile mediante la definizione di coefficiente binomiale), si ottiene
(34) $\begin{equation*} \sin\big((n+1)x\big) = \sum_{r=0}^{\left\lfloor\frac{n-1}{2}\right\rfloor}(-1)^r \binom{n+1}{2r+1} \cos^{n-2r}(x) \sin^{2r+1}(x), \end{equation*}$

ossia la tesi.

Se invece $n$ è pari, si ha $\frac{n}{2}=\left\lfloor\frac{n}{2}\right\rfloor = \left\lfloor\frac{n-1}{2}\right\rfloor + 1$ , cioè la seconda sommatoria all’ultimo membro di (33) possiede un termine in più della prima. Tenendo conto di ciò e della relazione $\binom{n}{2r}+ \binom{n}{2r+1}= \binom{n+1}{2r+1}$ , si giunge a
(35) $\begin{equation*} \begin{split} \sin\big((n+1)x\big) & = (-1)^{\frac{n}{2}} \binom{n}{n}\cos^0(x)\sin^{n+1}(x) + \sum_{r=0}^{\left\lfloor\frac{n-1}{2}\right\rfloor}(-1)^r \binom{n+1}{2r+1} \cos^{n-2r}(x) \sin^{2r+1}(x) \\ & = (-1)^{\left\lfloor\frac{(n+1)-1}{2}\right\rfloor} \binom{n+1}{n+1}\cos^{n+1 - 2\frac{n}{2}-1}(x)\sin^{2\frac{n}{2} +1}(x) \\ &\quad + \sum_{r=0}^{\left\lfloor\frac{n-1}{2}\right\rfloor}(-1)^r \binom{n+1}{2r+1} \cos^{n-2r}(x) \sin^{2r+1}(x) \\ & = \sum_{r=0}^{\left\lfloor\frac{(n+1)-1}{2}\right\rfloor}(-1)^r \binom{n+1}{2r+1} \cos^{n-2r}(x) \sin^{2r+1}(x). \end{split} \end{equation*}$

Ciò conclude il passo induttivo.

Esercizio 42 $(\bigstar\bigstar\largewhitestar\largewhitestar\largewhitestar)$

. Dimostrare che per ogni $n$

naturale vale la seguente proprietà:

$\mathcal{P}(n):\quad \dfrac{d^nf}{dx^n}(x)=\left(x^2+2nx+n\left(n-1\right)\right)e^x \qquad \forall x\in\mathbb{R},$

dove $f(x)=x^2e^x$ per ogni $x\in\mathbb{R}$ .

Svolgimento.

Per dimostrare che $\mathcal{P}(n)$

è vera per ogni $n\in \mathbb{N}$

applichiamo il principio di induzione.

Passo base: mostriamo che $\mathcal{P}(0)$ è vera.

$\dfrac{d^0f}{dx^0}(x)=f(x)=x^2e^x. \quad \checkmark$

Passo induttivo: mostriamo che $\mathcal{P}(n)\implies \mathcal{P}(n+1)$ .

$\begin{aligned} \dfrac{d^{n+1}f}{dx^{n+1}}(x)&=\dfrac{d}{dx}\left(\dfrac{d^{n}f}{dx^{n}}(x)\right)\overset{*}{=}\\ &\overset{*}{=}\dfrac{d}{dx} \left(x^2+2nx+n\left(n-1\right)\right)e^x=\\ &=\left(2x+2n\right)e^x+\left(x^2+2nx+n\left(n-1\right)\right)e^x=\\ &=e^x\left(2x+2n+x^2+2nx+n^2-n\right)=\\ &=e^x\left(x^2+2\left(n+1\right)x+n\left(n+1\right)\right), \end{aligned}$

avendo usato l’ipotesi induttiva nel passaggio $*$ .

Il principio di induzione prova quindi la proprietà $\mathcal{P}(n)$ per ogni $n\in \mathbb{N}$ .

Esercizio 43 $(\bigstar\bigstar\bigstar\largewhitestar\largewhitestar)$

. Dimostrare che per ogni $n\ge 1$

naturale vale la seguente proprietà:

$\mathcal{P}(n):\quad \dfrac{d^{n}f}{dx^{n}}(x)=\dfrac{2n!\left(-1\right)^{n+1}}{\left(x+2\right)^{n+1}}\qquad\forall x\in\mathbb{R} \setminus\{-2\},$

dove $\displaystyle f(x)=\frac{x}{x+2}$ per ogni $x\in\mathbb{R} \setminus\{-2\}$ .

Svolgimento.

Osserviamo preliminarmente che si ha

(36) $\begin{equation*} f(x) = \frac{x}{x+2} = \frac{x+2 - 2}{x+2} = 1 -\frac{2}{x+2} = 1 -2(x+2)^{-1} \qquad \forall x \in \mathbb{R}\setminus\{-2\}. \end{equation*}$

Per dimostrare la tesi applichiamo il principio di induzione.

Passo base: $\mathcal{P}(1)$ è vera in quanto da (36) segue

$\begin{aligned} \dfrac{df(x)}{dx} = 2(x+1)^{-2}= \frac{2}{(x+1)^2} \qquad \forall x \in \mathbb{R}\setminus\{-2\}. \quad \checkmark \end{aligned}$

Passo induttivo: per ipotesi induttiva supponiamo vera $\mathcal{P}(n)$ per un $n \ge 0$ e dimostriamo $\mathcal{P}(n+1)$ .

$\begin{aligned} \dfrac{d^{n+1}f}{dx^{n+1}}(x)&=\dfrac{d}{dx}\left(\dfrac{d^{n}f}{dx^{n}}(x)\right)=\\ &\overset{*}{=}\dfrac{d}{dx}\left(2(n!)\left(-1\right)^{n+1}\left(x+2\right)^{-n-1}\right)=\\ & =2n!\left(-1\right)^{n+1}\left(-\left(n+1\right)\right)\left(x+2\right)^{-n-2}=\\ &=\dfrac{2\left(n+1\right)!\left(-1\right)^{n+2}}{\left(x+2\right)^{n+2}}, \end{aligned}$

avendo usato l’ipotesi induttiva nel passaggio $*$ .

Per il principio di induzione, la proprietà $\mathcal{P}(n)$ vale per ogni $n\geq 1$ naturale.

Esercizio 44 $(\bigstar\bigstar\bigstar\bigstar\bigstar)$

. Dimostrare che per ogni $n \in \mathbb{N} \setminus\{0\}$

vale la seguente proposizione:

$\mathcal{P}(n):\int_{0}^{\frac{\pi}{3} } \frac{dx}{\left(\cos x\right)^{2n}}=\sqrt{3} \cdot\frac{(2n-2)!!}{(2n-1)!!} \cdot \sum_{k=0}^{n-1} \frac{(2k-1)!!}{(2k)!!}\cdot 2^{2k}.$

Svolgimento.

Per dimostrare la tesi applichiamo il principio d’induzione.

Passo base: Mostriamo che $\mathcal{P}(1)$ è vera.

$\int_{0}^{\frac{\pi}{3}}\dfrac{1}{\cos^2 x}dx=\tan x \big\vert_{0}^{\frac{\pi}{3}}=\tan\left(\frac{\pi}{3}\right)=\sqrt{3}.\quad \checkmark$

Passo induttivo: Per ipotesi induttiva supponiamo vera $\mathcal{P}(n)$ per un fissato $n\ge 1$ e mostriamo che essa implica $\mathcal{P}(n+1)$ . Chiamiamo

$I_n=\int_{0}^{\frac{\pi}{3} } \left( \frac{dx}{\left(\cos x\right)^{2n}}\right).$

Osserviamo che possiamo “separare” il prodotto e poi integrare per parti, ottenendo quanto segue:

$\begin{aligned} I_{n+1}&=\int_0^{\frac{\pi}{3}}\dfrac{1}{\cos^{2n+2}x}dx=\int_0^{\frac{\pi}{3}}\dfrac{1}{\cos^{2n}x}\cdot\dfrac{1}{\cos^2x}dx\\ &=\tan x \cdot \frac{1}{\left(\cos x\right)^{2n}} \bigg\vert_0^{\frac{\pi}{3}}-\int_0^{\frac{\pi}{3}}\tan x \cdot \dfrac{(-2n)(-\sin x)}{\cos^{2n+1}x}dx=\\ &=2^{2n}\sqrt{3}-2n\int_0^{\frac{\pi}{3}}\dfrac{\sin^2x}{\cos x}\cdot \dfrac{1}{\cos^{2n+1}x}dx=\\ &=2^{2n} \sqrt{3}-2n\int_0^{\frac{\pi}{3}} \dfrac{1-\cos^2x}{\cos^{2n+2}x}dx=\\ &=2^{2n} \sqrt{3}-2n\int_0^{\frac{\pi}{3}}\dfrac{1}{\cos^{2n+2}x}dx+2n\int_0^{\frac{\pi}{3}}\dfrac{1}{\cos^{2n}x}dx\\ &=2^{2n}\sqrt{3}-2n I_{n+1}+2nI_n. \end{aligned}$

Abbiamo quindi ottenuto la seguente identità:

$(2n+1)I_{n+1}=2^{2n}\sqrt{3}+2nI_n,$

e per ipotesi induttiva sappiamo che $I_n=\sqrt{3} \cdot\frac{(2n-2)!!}{(2n-1)!!} \cdot \sum_{k=0}^{n-1}\left( \frac{(2k-1)!!}{(2k)!!}\cdot 2^{2k}\right)$ . Pertanto possiamo sostituire e dividere per $2n+1$ , giungendo a

$\begin{aligned} I_{n+1}&=\dfrac{1}{2n+1}\left[2^{2n}\sqrt{3}+2n\left(\sqrt{3}\,\dfrac{(2n-2)!!}{(2n-1)!!}\sum_{k=0}^{n-1}\dfrac{(2k-1)!!}{(2k)!!}\cdot 2^{2k} \right)\right]=\\ &=\dfrac{\sqrt{3}}{2n+1}\left(2^{2n}+\dfrac{(2n)!!}{(2n-1)!!}\sum_{k=0}^{n-1}\dfrac{(2k-1)!!}{(2k)!!}\cdot2^{2k} \right)=\\ &=\sqrt{3}\, \dfrac{(2n)!!}{(2n+1)!!} \left(2^{2n}\cdot\dfrac{(2n-1)!!}{(2n)!!}+\sum_{k=0}^{n-1}\dfrac{(2k-1)!!}{(2k)!!}\cdot2^{2k} \right)=\\ &=\sqrt{3}\, \dfrac{(2n)!!}{(2n+1)!!}\sum_{k=0}^{n}\dfrac{(2k-1)!!}{(2k)!!}\cdot2^{2k}. \end{aligned}$

Questo conclude il passo induttivo e dunque la dimostrazione per induzione.

Esercizio 45 $(\bigstar\bigstar\bigstar\bigstar\bigstar)$

. Per ogni naturale $n\ge0$

determinare il quoziente e il resto della divisione tra i seguenti polinomi:

$p_n(x)=\sum_{k=0}^{n}\left(2k+1\right)x^k,\qquad q(x)=x-1.$

Suggerimento: si calcoli il risultato per valori piccoli di n, si congetturi una relazione generale, e la si dimostri per induzione.

Svolgimento.

Per trovare quoziente e resto per la seguente scrittura conviene calcolare il risultato per alcuni valori di $n$

al fine di formulare una congettura generale.

Poniamo $n=1$ :

$\sum_{k=0}^{1}\left(2k+1\right)x^k=1+3x = 3(x-1)+3+1.$

Per $n=2$ :

$\sum_{k=0}^{2}\left(2k+1\right)x^k = 1 + 3x + 5x^2 = (5x+8)(x-1) +9=5x(x-1)+(3+5)(x-1)+5+3+1.$

Per $n=3$ :

$\sum_{k=0}^{3}\left(2k+1\right)x^k=7x^2(x-1)+\left(5+7\right)x(x-1) +\left(3+5+7\right)(x-1)+1+3+5+7.$

Per $n=4$ :

$\begin{aligned} \sum_{k=0}^{4}\left(2k+1\right)x^k &= 9x^3(x-1)+\left(7+9\right)x^2(x-1)+\left(5+7+9\right)x(x-1) \\ & \quad +\left(3+5+7+9\right)(x-1) +1+3+5+7+9. \end{aligned}$

Basandoci sui primi casi che abbiamo trovato,, congetturiamo che la relazione generale sia:

$\boxcolorato{analisi}{{P}(n):\quad\sum_{k=0}^{n}\left(2k+1\right)x^k=\displaystyle\left[\sum_{k=1}^{n}\left(x^{k-1}\cdot\displaystyle\sum_{j=k}^{n}\left(2j+1\right)\right) \right](x-1) +\displaystyle\sum_{k=0}^{n}\left(2k+1\right). }$

Per dimostrare che $\mathcal{P}(n)$ è vera per ogni $n\in \mathbb{N}$ applichiamo il principio di induzione.

Passo base: mostriamo che $\mathcal{P}(0)$ è vera.

$1=0(x-1) +1.\quad \checkmark$

Passo induttivo: mostriamo che $\mathcal{P}(n)\implies \mathcal{P}(n+1)$ assumendo vera $\mathcal{P}(n)$ e deducendone $\mathcal{P}(n+1)$ . Chiamiamo $Q_n(x), R_n$ il quoziente e il resto della divisione al passo $n$ . Osserviamo che

$p_{n+1}(x)=p_n(x)+(2n+3)x^{n+1}=p_n(x)+(2n+3)\left[(x^{n+1}-x^n)+(x^n-x^{n-1})+\dots+(x-1)+1\right].$

Quindi compattando la sommatoria abbiamo

$p_{n+1}(x)=p_n(x)+\left[(2n+3)\cdot\sum_{k=0}^{n}x^k\right](x-1)+(2n+3).$

Adesso possiamo sfruttare l’ipotesi induttiva e sommare tra loro i termini simili, giungendo a

$\begin{aligned} p_{n+1}(x)&=Q_n(x)\cdot(x-1)+\left[(2n+3)\cdot\sum_{k=0}^{n}x^k\right](x-1)+(2n+3)+R_n(x)=\\ &=\left[\sum_{k=1}^{n}\left(x^{k-1}\cdot\displaystyle\sum_{j=k}^{n}\left(2j+1\right)\right) +(2n+3)\cdot\sum_{k=1}^{n+1}x^{k-1}\right](x-1)+(2n+3)+\sum_{k=0}^{n}\left(2k+1\right)=\\ &=\left[\sum_{k=1}^{n+1}\left(x^{k-1}\cdot\displaystyle\sum_{j=k}^{n+1}\left(2j+1\right)\right)\right](x-1) +\sum_{k=0}^{n+1}\left(2k+1\right). \end{aligned}$

Abbiamo ottenuto l’espressione che volevamo e abbiamo dunque concluso il passo induttivo, dimostrando per induzione la formula congetturata.

Esercizio 46 $(\bigstar\largewhitestar\largewhitestar\largewhitestar\largewhitestar)$

. Si consideri la seguente successione per ricorrenza:

$\begin{cases} a_0=0,\qquad a_1=1;\\ a_{n+1}=5a_n+6a_{n-1}\quad n\ge 1. \end{cases}$

Dimostrare che per ogni naturale $n\ge 1$ il termine $a_n$ è coprimo con $6$ .

Si ricorda che due numeri interi si dicono coprimi quando non hanno fattori comuni nella scomposizione in fattori primi, cioè se il loro massimo comun divisore (MCD) è $1$ .

Svolgimento.

Dimostriamo che l’enunciato è valido per induzione.

Passo base: dimostriamo che la tesi è vera per $n=1$ in quanto $a_1=1$ , che è ovviamente coprimo con $6$ .

Passo induttivo: Supponiamo la tesi vera per $a_n$ e dimostriamola per $a_{n+1}$ . Dalla traccia sappiamo che

$a_{n+1}=5a_n+6a_{n-1}$

e per ipotesi induttiva $a_n$ non ha fattori primi in comune con $6$ , dunque tale è anche $5a_n$ in quanto $5$ è coprimo con $6$ . Poiché $6a_{n-1}$ è multiplo di $6$ , ne segue che $a_{n+1}$ non è divisibile né per $2$ né per $3$ , cioè non ha fattori primi in comune con $6$ .

Esercizio 47 $(\bigstar\bigstar\largewhitestar\largewhitestar\largewhitestar)$

. Si consideri la seguente successione definita per ricorrenza:

(37) $\begin{equation*} \begin{cases} a_0=2,\qquad a_1=3, \qquad a_2=5;\\ a_{n+1}=a_n-a_{n-1}+2a_{n-2}\quad n\ge 2. \end{cases} \end{equation*}$

Dimostrare che la successione è strettamente crescente.

Svolgimento.

Dimostreremo che per ogni $n \in \mathbb{N}$

si ha $a_{n+1}>a_n$

; a tal fine, usiamo il principio di induzione forte stabilito nel teorema 1.4.

Passi base: Dimostriamo la tesi per i primi termini della successione.

Per $n=0,1$ , segue dalla definizione della successione, in (37).

Poniamo $n=2$ ; si ha

$a_{n+1}=a_3=a_2-a_1+2a_0=5-3+4=6>5=a_2.\quad\checkmark$

Passo induttivo: Supponiamo che la tesi sia vera per ogni termine fino all’ $n$ -esimo e dimostriamola per $a_{n+1}$ . Si ha

$a_{n+2}>a_{n+1} \iff a_{n+1}-a_n+2a_{n-1}>a_{n+1} \iff 2a_{n-1}-a_n>0.$

Per provare l’ultima disuguaglianza, sviluppiamo $a_n$ ottenendo

$2a_{n-1}-(a_{n-1}-a_{n-2}+2a_{n-3})=a_{n-1}+a_{n-2}-2a_{n-3}\overset{*}{>}0,$

dove l’ultimo passaggio $*$ sfrutta l’ipotesi induttiva forte e precisamente che $a_{n-3}<a_{n-2}$ e $a_{n-3}<a_{n-1}$ . Ciò dimostra che $a_{n+1}<a_{n+2}$ , cioè la tesi.

Esercizio 48 $(\bigstar\largewhitestar\largewhitestar\largewhitestar\largewhitestar)$

. Si consideri la seguente successione per ricorrenza:

$\begin{cases} a_0=2,\qquad a_1=1;\\ a_{n+1}=a_n+a_{n-1}\quad n\ge 1. \end{cases}$

Dimostrare che per ogni naturale $n$ vale la seguente proprietà:

$\sum_{k=0}^{n}a_k^2=a_n a_{n+1}+2.$

Osservazione.

La successione $a_n$

è detta di Fibonacci.

Svolgimento.

Dimostriamo la tesi per induzione.

Passo base: Dimostriamo la tesi per $n=0$ .

$a_0^2=2^2=4=2+2=a_0\cdot a_1+2.\quad \checkmark$

Passo induttivo: Supponiamo che la tesi sia vera per $n$ e dimostriamone la validità anche per $n+1$ .

$\sum_{k=0}^{n+1}a_k^2=a_{n+1}^2+\sum_{k=0}^{n}a_k^2\overset{*}{=}a_{n+1}^2+a_na_{n+1}+2= a_{n+1}(a_{n+1}+a_n)+2=a_{n+1}a_{n+2}+2,$

dove in $*$ è stata utilizzata l’ipotesi induttiva. Siamo quindi arrivati a ciò che volevamo dimostrare, concludendo così il passo induttivo.

Esercizio 49 $(\bigstar\bigstar\bigstar\largewhitestar\largewhitestar)$

. Si consideri la seguente successione per ricorrenza:

(38) $\begin{equation*} \begin{cases} a_0=1,\qquad a_1=1;\\ a_{n+2}=a_{n}+n+2\quad n\ge 0. \end{cases} \end{equation*}$

Trovare il minimo $n_0$ tale che per ogni $n\geq n_0$ valga $a_n\ge 2n$ .

Svolgimento.

Da (38) segue che $a_n \geq 2n$

se e solo se $a_{n-2} \geq n$

. Dunque la richiesta dell’esercizio è equivalente a trovare il minimo $n_0$

tale che

(39) $\begin{equation*} a_{n-2} \geq n \qquad \forall n \geq n_0. \end{equation*}$

Osserviamo che, per la definizione (38) della successione, i termini di indice dispari dipendono dai soli termini di indice dispari precedenti, e similmente per i termini di indice pari.

Osserviamo inoltre che, se $a_{n-2} \geq n$ , allora

(40) $\begin{equation*} a_{n}= a_{n-2}+ n \geq n + n = 2n \end{equation*}$

e tale quantità è maggiore o uguale a $n+2$ se e solo se $n \geq 2$ . In altre parole,

(41) $\begin{equation*} a_{n-2} \geq n \implies a_n \geq n+2 \qquad \text{se }n \geq 2. \end{equation*}$

Tale considerazione mostra che, affinché la proprietà richiesta rimanga induttivamente vera per tutti i termini con una certa parità dell’indice, è sufficiente che valga per $a_{n-2}\geq n$ con $n \geq 2$ .

Conviene quindi distinguere le due sottosuccessioni dei termini aventi indice pari e dispari, ricercando i primi termini che soddisfano le proprietà richieste.

$\quad$

$n$ pari. Calcolando i primi termini di indice pari della successione si ha:

(42) $\begin{equation*} \begin{aligned} n=2, \qquad &a_{n-2}=a_0=1 < 2; \\ n=4, \qquad &a_{n-2}=a_2=3 < 4; \\ n=6, \qquad &a_{n-2}=a_4=7 \geq 6. \end{aligned} \end{equation*}$

Per il ragionamento precedente, tutti i termini di indice pari a partire da $n=6$ soddisfano la disuguaglianza richiesta.

$n$ dispari. Con lo stesso argomento di sopra, è sufficiente calcolare i primi termini di indice dispari della successione:

(43) $\begin{equation*} \begin{aligned} n=3, \qquad &a_{n-2}=a_1=1 < 3; \\ n=5, \qquad &a_{n-2}=a_3=4 < 5; \\ n=7, \qquad &a_{n-2}=a_5=9 \geq 7. \end{aligned} \end{equation*}$

Tutti i termini di indice dispari a partire da $n=7$ soddisfano la disuguaglianza richiesta.

Dalle considerazioni precedenti segue che il valore richiesto è $n_0=6$ .

Esercizio 50 $(\bigstar\bigstar\largewhitestar\largewhitestar\largewhitestar)$

. Si consideri la successione di Fibonacci:

$\begin{cases} F_0=0,\qquad F_1=1;\\ F_{n+1}=F_n+F_{n-1}\quad n\ge 1. \end{cases}$

Dimostrare che per ogni naturale $n$ vale la seguente proprietà:

$\mathcal{P}(n):\qquad F_{2n+1}=F_n^2+F_{n+1}^2.$

Svolgimento.

Mostriamo due risoluzioni di quest’esercizio.

Primo svolgimento.

Dimostriamo la validità della proprietà $\mathcal{P}(n)$

per induzione forte, teorema 1.4.

Passo base: Verifichiamo che $\mathcal{P}(0)$ sia vera.

$F_0^2+F_1^2=0+1=1=F_1.\quad \checkmark$

Passo induttivo: Supponiamo che $\mathcal{P}(m)$ sia vera per ogni $m\leq n-1$ e dimostriamo che ciò implica la validità di $\mathcal{P}(n)$ . Per definizione

(44) $\begin{equation*} F_{2n+1}=F_{2n}+F_{2n-1}. \end{equation*}$

In particolare $2n-1=2(n-1)+1$ , quindi per $F_{2n-1}$ possiamo sfruttare l’ipotesi induttiva, ma dobbiamo scrivere diversamente $F_{2n}$ . A tal fine, notiamo che

$F_{2n}=F_{2n-1}+F_{2n-2}=F_{2n-1}+F_{2n-1}-F_{2n-3},$

dove, nell’ultimo passaggio, abbiamo usato il fatto che $F_{2n-1}=F_{2n-2}+F_{2n-3}$ per ottenere $F_{2n-2}$ come somma di numeri di Fibonacci con indici dispari. Inserendo tale relazione in (44) e usando l’ipotesi di induzione forte si ottiene

(45) $\begin{equation*} F_{2n+1} = 3F_{2n-1}-F_{2n-3} = 3F_{n-1}^2 + 3F_{n}^2 - F_{n-2}^2 - F_{n-1}^2 \end{equation*}$

$\begin{aligned} F_{2n+1}&=3F_{2n-1}-F_{2n-3}=\\ &=2F_{2n-1}+F_{n}^2+F_{n-1}^2-(F_{n-2}^2+F_{n-1}^2)=\\ &=2F_{2n-1}+F_n^2-F_{n-2}^2=\\ &=2F_n^2+2F_{n-1}^2+(F_{n}-F_{n-2})(F_n+F_{n-2})=\\ &=2F_n^2+2F_{n-1}^2+F_{n-1}(F_{n+1}+F_n-2F_{n-1})=\\ &=2F_n^2+F_{n-1}F_{n+1}+F_{n-1}F_n=\\ &=F_n^2+F_n^2+F_{n-1}^2+2F_{n-1}F_n=\\ &=F_n^2+(F_n+F_{n-1})^2=\\ &=F_n^2+F_{n+1}^2. \end{aligned}$

Siamo quindi arrivati all’espressione che desideravamo.

Per induzione, $\mathcal{P}(n)$ è valida per ogni $n\in\mathbb{N}$ .

Secondo svolgimento.

Dimostriamo per induzione forte su $k\geq 1$

la seguente proprietà che generalizza la tesi dell’esercizio:

$\mathcal{Q}(k):\qquad F_{n+k}=F_kF_{n+1}+F_{k-1}F_n.$

Osserviamo che effettivamente scegliendo $k=n+1$ si ottiene la tesi dell’esercizio.

Passo base: Dimostriamo che $\mathcal{Q}(1)$ è valida. Osserviamo infatti che

$F_{n+1}=F_1F_{n+1}+F_0F_n.$

Passo induttivo: Assumiamo che $\mathcal{Q}(h)$ sia vera per ogni $h\leq k$ e verifichiamo che lo è anche $\mathcal{Q}(k+1)$ .

$F_{n+k+1}=F_{n+k}+F_{n+k-1}\overset{*}{=}F_kF_{n+1}+F_{k-1}F_n+F_{k-1}F_{n+1}+F_{k-2}F_n,$

dove in $*$ abbiamo usato l’induzione sia su $F_{n+k}$ che su $F_{n+k-1}$ . A questo punto raccogliamo e otteniamo

$F_{n+k+1}=F_{n+1}(F_{k}+F_{k-1})+F_{n}(F_{k-1}+F_{k-2})=F_{k+1}F_{n+1}+F_kF_{n}.$

Abbiamo perciò dimostrato per induzione forte la validità della proprietà $\mathcal{Q}(k)$ per ogni naturale $k\geq 1$ , e in particolare anche per $k=n+1$ .

Esercizio 51 $(\bigstar\bigstar\largewhitestar\largewhitestar\largewhitestar)$

. Dimostrare che ogni numero naturale si può scrivere come somma di numeri di Fibonacci distinti.

Svolgimento.

Dimostriamo la conclusione per induzione forte, teorema 1.4.

Passo base: la tesi è banale per $n=0$ e $n=1$ , che sono pari ai primi numeri di Fibonacci.

Passo induttivo: supponiamo che la tesi sia vera per tutti i numeri naturali fino a $n-1$ e proviamola per $n$ , con $n \geq 2$ . Sia $F_k$ il massimo numero di Fibonacci minore o uguale a $n$ ossia tale che

(46) $\begin{equation*} F_k \leq n < F_{k+1} = F_k + F_{k-1} \end{equation*}$

Poiché $n \geq 1$ , si ha $F_k\geq 1$ e dunque $n-F_k< n$ . Per ipotesi induttiva, $n-F_k$ si può scrivere come somma di numeri di Fibonacci distinti e tutti strettamente minori di $F_k$ , in quanto per (46) vale $n-F_k < F_{k-1} \leq F_{k}$ . Dunque, poiché $n=(n-F_k)+F_k$ , esso si può scrivere come somma di numeri di Fibonacci distinti.

Esercizio 52 $(\bigstar\bigstar\largewhitestar\largewhitestar\largewhitestar)$

. Trovare l’errore nalla seguente dimostrazione per induzione che tutte le automobili sono dello stesso colore.

Dimostriamo che, dato un insieme di $n$ automobili, esse sono tutte dello stesso colore.

Per $n=1$ l’enunciato è banalmente vero.

Supponiamo la tesi vera per insiemi di $n$ elementi e consideriamo un insieme $A$ di $n+1$ automobili. Escludendone una, che chiameremo $x$ , rimane un insieme di $n$ automobili che per ipotesi induttiva sono tutte dello stesso colore.
Escludendo invece da $A$ un’altra automobile $y$ , diversa da $x$ , e reinserendo $x$ nell’insieme, otteniamo un nuovo sottoinsieme di $n$ automobili, tutte dello stesso colore per ipotesi induttiva. Ciò prova che anche anche $x$ è dello stesso colore delle altre automobili.

Svolgimento.

L’errore nella dimostrazione si trova nel passo induttivo: quando consideriamo i due sottoinsiemi di $A$

aventi $n$

elementi, stiamo assumendo che essi abbiano elementi in comune; la in comune è essenziale per concludere che i colori di $x$

e $y$

siano i medesimi, ma non è detto che tale parte comune esista.

Più precisamente, il ragionamento del passo induttivo fallisce nel passare da $n=1$ a $n=2$ . Infatti, se $A=\{x,y\}$ ha $2$ elementi, escludendo $x$ otteniamo $A \setminus \{x\}=\{y\}$ , mentre escludendo $y$ si ottiene $A \setminus \{y\}=\{x\}$ . Entrambi questi sottoinsiemi hanno $n=1$ elementi e chiaramente soddisfano l’ipotesi induttiva, ma non si riesce a concludere che $x$ e $y$ abbiano lo stesso colore, in quanto non vi sono altri elementi di $A$ che consentono di “trasferire” l’uguaglianza del colore di $x$ col colore di $y$ . In altre parole, la dimostrazione si baserebbe sulla transitività dell’uguaglianza del colore, ma tale proprietà viene erroneamente applicata non essendoci necessariamente elementi “medi”.

Esercizio 53 $(\bigstar\bigstar\bigstar\largewhitestar\largewhitestar)$

. Si dimostri che una scacchiera quadrata di lato $2^n$

a cui viene rimosso un quadratino nell’angolo può essere tassellata con pezzi a L con lati di $2$

quadratini, rappresentati in figura.

Svolgimento.

Possiamo dimostrare la tesi per induzione su $n\geq 1$

Passo base: Come si può vedere in figura 1, la tesi è vera per $n=1$ ; infatti se ad una scacchiera di lato $2$ viene tolto un angolo, resta esattamente il pezzo a L con cui vogliamo tassellarla.

$\quad$

Figura 1: passo base dell’induzione.

$\quad$

Passo induttivo: Supponiamo per ipotesi induttiva che la tesi sia vera per griglie $2^n\times 2^n$ e dimostriamo che possiamo tassellare anche griglie di lato $2^{n+1}$ . Osserviamo che una griglia $2^{n+1}\times 2^{n+1}$ si può suddividere in $4$ griglie di lato $2^n$ , dividendo a metà i bordi e tracciando gli assi. Se la griglia $2^{n+1}\times 2^{n+1}$ viene privata dell’angolo in alto a destra, allora la sottogriglia $2^n\times 2^n$ in alto a destra è privata di un angolo e quindi è tassellabile con pezzi a L per ipotesi induttiva, si veda la figura 2, dove è rappresentato il caso $n=2$ . Possiamo privare ciascuna delle restanti $3$ griglie dell’angolo che si trova al centro della griglia principale, come rappresentato in figura 2, in modo tale da poter tassellare le $3$ parti rimanenti, di nuovo per ipotesi induttiva. Così facendo restano al centro $3$ quadratini messi a L, ovvero gli angoli “rimossi” dalle sottogriglie, che chiaramente possono essere coperti da un ulteriore pezzo a L. cui vogliamo tassellarla.

$\quad$

Figura 2: passo induttivo nel caso $n=2$ .

$\quad$

Esercizio 54 $(\bigstar\bigstar\bigstar\bigstar\largewhitestar)$

. Dimostrare che per ogni $n\ge 4$

ogni triangolo isoscele con un angolo di $120$

gradi può essere scomposto in $n$

triangoli ad esso simili.

Suggerimento: si utilizzi l’induzione forte.

Svolgimento.

Dimostriamo per induzione forte quanto richiesto.

Passi base: La tesi è vera per $n=4,5,6$ , come si può vedere in figura.

$\quad$

Figura 3: passo base dell’induzione.

$\quad$

Passo induttivo: Supponiamo per ipotesi induttiva forte che la tesi sia vera per $4\leq k\leq n$ , con $n\geq 6$ e dimostriamo che la proprietà è valida anche per $k=n+1$ . Poiché $n+1=(n-2)+3$ e $n\geq 6$ , allora $n-2$ è compreso tra $4$ e $n$ . Allora possiamo agire come segue:

$\quad$

suddividiamo il triangolo in $n-2$ triangoli ad esso simili (è lecito, per ipotesi induttiva);

scegliamo uno di questi $n-2$ triangoli della decomposizione;

sostituiamo quest’ultimo con 4 triangoli ad esso simili, e quindi simili al triangolo originale per proprietà transitiva della similitudine.

Così facendo abbiamo suddiviso il triangolo di partenza in $(n-2)+4-1=n+1$ triangoli ad esso simili, come volevamo.

Esercizio 55 $(\bigstar\bigstar\bigstar\largewhitestar\largewhitestar)$

. Dimostrare che, in un poligono di $n$

lati (con $n\geq 3$

), la somma degli angoli interni è $(n-2)\pi$

e il numero totale di diagonali è $\frac{n(n-3)}{2}$

Svolgimento.

Presentiamo due soluzioni per questo esercizio.

Svolgimento diretto.

Consideriamo un poligono $Q$

di $n$

lati e indichiamo con $P_1,\dots,P_n$

i suoi vertici. Partizioniamo $Q$

nei seguenti $n-2$

triangoli:

(47) $\begin{equation*} P_nP_1P_2, \qquad P_nP_2P_3, \qquad \dots \qquad P_nP_{n-2}P_{n-1}. \end{equation*}$

Per come è stata fatta la suddivisione, la somma degli angoli interni di $Q$ è quindi pari alla somma degli angoli interni di questi $n-2$ triangoli, ciascuno dei quali ha somma degli angoli interni pari a $\pi$ : il risultato è cioè

$(n-2)\pi.$

Il numero di diagonali di $Q$ è pari al numero di coppie non ordinate di vertici non adiacenti. Il primo vertice della coppia può essere scelto in $n$ modi, mentre i vertici a esso non adiacenti sono in numero $n-3$ . Dividendo per $2$ , in modo da non contare due volte ciascuna coppia di vertici, si ottiene che il numero di diagonali di $Q$ è pari a

(48) $\begin{equation*} \frac{n(n-3)}{2}, \end{equation*}$

come desiderato.

Svolgimento per induzione.

Indicando con $\sigma_n$

la somma degli angoli interni di un poligono di $n$

lati e con $d_n$

il numero delle sue diagonali, vogliamo dimostrare la validità della proprietà

$\mathcal{P}(n):\quad \sigma_n=(n-2)\pi,\qquad d_n=\frac{n(n-3)}{2}$

per ogni $n \geq 3$ .

Passo base: un poligono di $n=3$ lati è un triangolo, che sappiamo avere somma degli angoli interni pari a $\pi$ e non avere diagonali. Dunque

$\sigma_3=\pi \qquad d_3=0.\quad\checkmark$

Passo induttivo: supponiamo che la tesi sia vera per i poligoni di $n$ lati e dimostriamola per i poligoni di $n+1$ lati.

Fissiamo un poligono $Q$ di $n+1$ lati e indichiamo con $P_i$ , $i=1,\ldots,n+1$ i suoi vertici; consideriamo poi il poligono $Q'$ di $n$ lati determinato dai vertici $P_1,\dots,P_n$ . $Q$ si ottiene dall’unione di $Q'$ e del triangolo $T$ di vertici $P_n,P_{n+1},P_1$ e dunque la misura totale degli angoli interni di $Q$ si ottiene come somma degli angoli in $Q'$ e in $T$ , che, per ipotesi induttiva, è pari a $(n-2)\pi + \pi=(n-1)\pi$ .

Inoltre, il numero di diagonali di $Q$ è dato dalla somma delle diagonali di $Q'$ e delle diagonali aventi per estremo $P_{n+1}$ e la diagonale data dal segmento $P_nP_1$ . Per ipotesi induttiva $Q'$ possiede $\frac{n(n-3)}{2}$ diagonali. Invece, le diagonali aventi per estremo $P_{n+1}$ sono in corrispondenza biunivoca con i vertici $P_2,\dots,P_{n-1}$ (ossia tutti i vertici non adiacenti a $P_{n+1}$ ), dunque sono in numero $n-2$ . Dunque il numero totale di diagonali di $Q$ è

(49) $\begin{equation*} \frac{n(n-3)}{2} + (n-2) + 1 = \frac{n^2-n-2}{2}=\frac{(n+1)(n-2)}{2}. \end{equation*}$

Per l’arbitrarietà del poligono $Q$ , possiamo quindi concludere che

(50) $\begin{equation*} \sigma_{n+1}=(n-1)\pi, \qquad d_{n+1}=\frac{(n+1)(n-2)}{2}. \end{equation*}$

Ciò conclude la dimostrazione.

Riferimenti bibliografici

[1] Piacentini Cattaneo, G.M., Algebra. Un approccio algoritmico, Zanichelli (1996).

[2] Qui Si Risolve, Teoria degli insiemi numerici

[3] Qui Si Risolve, Il principio di induzione

[4] Verardi, L., Gli insiemi numerici, Dispense del corso di algebra, Unibo (2007).

Tutta la teoria di analisi matematica

Leggi...

Tutte le cartelle di Analisi Matematica

Leggi...

Tutti gli esercizi di geometria

In questa sezione vengono raccolti molti altri esercizi che coprono tutti gli argomenti di geometria proposti all’interno del sito con lo scopo di offrire al lettore la possibilità di approfondire e rinforzare le proprie competenze inerenti a tali argomenti.

Strutture algebriche.

Algebra lineare.

Geometria analitica.

Geometria differenziale.

Risorse didattiche aggiuntive per approfondire la matematica

Leggi...

Math Stack Exchange – Parte della rete Stack Exchange, questo sito è un forum di domande e risposte specificamente dedicato alla matematica. È una delle piattaforme più popolari per discutere e risolvere problemi matematici di vario livello, dall’elementare all’avanzato.
Art of Problem Solving (AoPS) – Questo sito è molto noto tra gli studenti di matematica di livello avanzato e i partecipanti a competizioni matematiche. Offre forum, corsi online, e risorse educative su una vasta gamma di argomenti.
MathOverflow – Questo sito è destinato a matematici professionisti e ricercatori. È una piattaforma per domande di ricerca avanzata in matematica. È strettamente legato a Math Stack Exchange ma è orientato a un pubblico con una formazione più avanzata.
PlanetMath – Una comunità collaborativa di matematici che crea e cura articoli enciclopedici e altre risorse di matematica. È simile a Wikipedia, ma focalizzata esclusivamente sulla matematica.
Wolfram MathWorld – Una delle risorse online più complete per la matematica. Contiene migliaia di articoli su argomenti di matematica, creati e curati da esperti. Sebbene non sia un forum, è una risorsa eccellente per la teoria matematica.
The Math Forum – Un sito storico che offre un’ampia gamma di risorse, inclusi forum di discussione, articoli e risorse educative. Sebbene alcune parti del sito siano state integrate con altri servizi, come NCTM, rimane una risorsa preziosa per la comunità educativa.
Stack Overflow (sezione matematica) – Sebbene Stack Overflow sia principalmente noto per la programmazione, ci sono anche discussioni rilevanti di matematica applicata, specialmente nel contesto della scienza dei dati, statistica, e algoritmi.
Reddit (r/Math) – Un subreddit popolare dove si possono trovare discussioni su una vasta gamma di argomenti matematici. È meno formale rispetto ai siti di domande e risposte come Math Stack Exchange, ma ha una comunità attiva e molte discussioni interessanti.
Brilliant.org – Offre corsi interattivi e problemi di matematica e scienza. È particolarmente utile per chi vuole allenare le proprie capacità di problem solving in matematica.
Khan Academy – Una risorsa educativa globale con lezioni video, esercizi interattivi e articoli su una vasta gamma di argomenti di matematica, dalla scuola elementare all’università.

Document