Prezzi Registrazione Login
Qui si risolve LOGO
a

Menu

M

Chiudi

Principio di Induzione: Esercizi Svolti

Principio di Induzione in Analisi Matematica

Home » Principio di Induzione: Esercizi Svolti

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\]

  1. sommatorie;

    2.  

  2. disuguaglianze;

    3.  

  3. produttorie;

    4.  

  4. divisibilità;

    5.  

  5. formule chiuse;

    6.  

  6. successioni definite per ricorrenza;

    7.  

  7. “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.1

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

  1. 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} .\]

Questa parte è riservata agli abbonati

per continuare a leggere, attiva un abbonamento.

• Mensile: 7,99€ / mese • Trimestrale: 19,99€ / 3 mesi • Annuale: 79,99€ / anno

Attiva abbonamento

Già abbonato? Accedi