Una raccolta progressiva di 20 esercizi svolti sul principio di induzione matematica, pensata per comprendere in modo rigoroso il funzionamento delle dimostrazioni per induzione. Ogni esercizio mostra con chiarezza:
- come verificare correttamente la base induttiva;
- come formulare l’ipotesi induttiva;
- come utilizzare l’ipotesi senza errori logici;
- come dimostrare il passaggio dal caso \(n\) al caso \(n+1\).
L’obiettivo non è soltanto verificare formule, ma comprendere la struttura logica della dimostrazione per induzione e imparare a sviluppare ragionamenti rigorosi passo dopo passo.
Esercizio 1 — livello ★☆☆☆☆
Dimostrare per induzione che:
\[ 1+2+3+\dots+n=\frac{n(n+1)}{2} \]
Dimostrazione
Base induttiva
Verifichiamo anzitutto la proprietà per \(n=1\).
Il membro sinistro vale:
\[ 1 \]
Il membro destro vale:
\[ \frac{1(1+1)}{2}=\frac{2}{2}=1 \]
I due membri coincidono. La proprietà è quindi vera per \(n=1\).
Ipotesi induttiva
Supponiamo ora che la formula sia vera per un certo numero naturale \(n\). Questa supposizione prende il nome di ipotesi induttiva.
Supponiamo quindi:
\[ 1+2+3+\dots+n=\frac{n(n+1)}{2} \]
È fondamentale capire che non stiamo assumendo la formula vera per tutti i numeri naturali, ma soltanto per un valore arbitrario \(n\).
Passo induttivo
Dobbiamo dimostrare che, se la formula vale per \(n\), allora vale anche per \(n+1\).
In altre parole, dobbiamo provare:
\[ 1+2+3+\dots+n+(n+1)=\frac{(n+1)(n+2)}{2} \]
Partiamo dal membro sinistro:
\[ 1+2+3+\dots+n+(n+1) \]
A questo punto utilizziamo l’ipotesi induttiva. Essa ci permette di sostituire la somma dei primi \(n\) numeri con l’espressione già nota:
\[ \frac{n(n+1)}{2} \]
Otteniamo quindi:
\[ 1+2+\dots+n+(n+1) = \frac{n(n+1)}{2}+(n+1) \]
Ora il nostro obiettivo è trasformare questa espressione nella formula attesa:
\[ \frac{(n+1)(n+2)}{2} \]
Per farlo, raccogliamo il fattore comune \(n+1\):
\[ \frac{n(n+1)}{2}+(n+1) = (n+1)\left(\frac{n}{2}+1\right) \]
Scriviamo ora \(1\) come \(\frac{2}{2}\), così da poter sommare le frazioni:
\[ \frac{n}{2}+1 = \frac{n}{2}+\frac{2}{2} = \frac{n+2}{2} \]
Sostituendo otteniamo:
\[ (n+1)\left(\frac{n+2}{2}\right) = \frac{(n+1)(n+2)}{2} \]
Abbiamo dunque dimostrato che:
\[ 1+2+\dots+n+(n+1) = \frac{(n+1)(n+2)}{2} \]
Conclusione
La proprietà è vera per \(n=1\) e abbiamo dimostrato che la verità della formula per \(n\) implica la sua verità per \(n+1\).
Per il principio di induzione matematica, concludiamo che:
\[ 1+2+3+\dots+n=\frac{n(n+1)}{2} \]
per ogni numero naturale \(n\geq1\).
Esercizio 2 — livello ★☆☆☆☆
Dimostrare per induzione che:
\[ 1+3+5+\dots+(2n-1)=n^2 \]
Dimostrazione
Interpretazione della formula
Il membro sinistro rappresenta la somma dei primi \(n\) numeri dispari:
\[ 1,3,5,7,\dots \]
La formula afferma che tale somma è sempre uguale al quadrato di \(n\).
Base induttiva
Verifichiamo la formula per \(n=1\).
Il membro sinistro vale:
\[ 1 \]
Il membro destro vale:
\[ 1^2=1 \]
I due membri coincidono. La proprietà è quindi vera per \(n=1\).
Ipotesi induttiva
Supponiamo ora che la formula sia vera per un certo numero naturale \(n\).
Assumiamo quindi:
\[ 1+3+5+\dots+(2n-1)=n^2 \]
Passo induttivo
Dobbiamo dimostrare che allora vale anche:
\[ 1+3+5+\dots+(2n-1)+(2n+1)=(n+1)^2 \]
È importante osservare perché compare il termine \(2n+1\).
Infatti:
\[ 2(n+1)-1=2n+2-1=2n+1 \]
Dunque \(2n+1\) è esattamente il numero dispari successivo.
Partiamo ora dal membro sinistro:
\[ 1+3+5+\dots+(2n-1)+(2n+1) \]
Utilizziamo l’ipotesi induttiva per sostituire la parte iniziale della somma:
\[ n^2+(2n+1) \]
Otteniamo quindi:
\[ n^2+2n+1 \]
Riconosciamo ora un quadrato perfetto:
\[ n^2+2n+1=(n+1)^2 \]
Abbiamo così dimostrato che:
\[ 1+3+5+\dots+(2n-1)+(2n+1)=(n+1)^2 \]
Conclusione
La proprietà è vera per \(n=1\) e il passo induttivo è stato verificato.
Per il principio di induzione matematica:
\[ 1+3+5+\dots+(2n-1)=n^2 \]
per ogni \(n\geq1\).
Esercizio 3 — livello ★★☆☆☆
Dimostrare per induzione che:
\[ 1+2+4+8+\dots+2^n=2^{n+1}-1 \]
Dimostrazione
Interpretazione della formula
Il membro sinistro rappresenta la somma delle prime potenze di \(2\):
\[ 2^0+2^1+2^2+\dots+2^n \]
La formula afferma che questa somma può essere scritta in forma chiusa come:
\[ 2^{n+1}-1 \]
Base induttiva
Verifichiamo la proprietà per \(n=0\).
Il membro sinistro vale:
\[ 2^0=1 \]
Il membro destro vale:
\[ 2^{0+1}-1=2^1-1=2-1=1 \]
I due membri coincidono. La proprietà è quindi vera per \(n=0\).
Ipotesi induttiva
Supponiamo ora che la formula sia vera per un certo numero naturale \(n\).
Assumiamo quindi:
\[ 1+2+4+\dots+2^n=2^{n+1}-1 \]
Passo induttivo
Dobbiamo dimostrare che allora vale anche:
\[ 1+2+4+\dots+2^n+2^{n+1}=2^{n+2}-1 \]
Partiamo dal membro sinistro:
\[ 1+2+4+\dots+2^n+2^{n+1} \]
Utilizziamo l’ipotesi induttiva per sostituire la somma iniziale:
\[ (2^{n+1}-1)+2^{n+1} \]
Sommiamo ora i termini simili:
\[ 2^{n+1}+2^{n+1}-1 \]
Poiché:
\[ 2^{n+1}+2^{n+1}=2\cdot2^{n+1} \]
otteniamo:
\[ 2\cdot2^{n+1}-1 \]
Applicando le proprietà delle potenze:
\[ 2\cdot2^{n+1}=2^{n+2} \]
segue:
\[ 2^{n+2}-1 \]
Abbiamo dunque dimostrato che:
\[ 1+2+4+\dots+2^n+2^{n+1}=2^{n+2}-1 \]
Conclusione
La proprietà è vera per \(n=0\) e il passo induttivo è stato verificato.
Per il principio di induzione matematica:
\[ 1+2+4+8+\dots+2^n=2^{n+1}-1 \]
per ogni \(n\geq0\).
Esercizio 4 — livello ★★☆☆☆
Dimostrare per induzione che:
\[ 1^2+2^2+3^2+\dots+n^2=\frac{n(n+1)(2n+1)}{6} \]
Dimostrazione
Significato della formula
La formula fornisce un’espressione chiusa per la somma dei quadrati dei primi \(n\) numeri naturali.
Invece di sommare ogni termine separatamente:
\[ 1^2+2^2+3^2+\dots+n^2 \]
possiamo calcolare direttamente:
\[ \frac{n(n+1)(2n+1)}{6} \]
Base induttiva
Verifichiamo la proprietà per \(n=1\).
Il membro sinistro vale:
\[ 1^2=1 \]
Il membro destro vale:
\[ \frac{1(1+1)(2\cdot1+1)}{6} \]
Semplificando:
\[ \frac{1\cdot2\cdot3}{6}=\frac{6}{6}=1 \]
La proprietà è quindi vera per \(n=1\).
Ipotesi induttiva
Supponiamo ora che la formula sia vera per un certo numero naturale \(n\).
Assumiamo quindi:
\[ 1^2+2^2+3^2+\dots+n^2 = \frac{n(n+1)(2n+1)}{6} \]
Passo induttivo
Dobbiamo dimostrare che allora vale anche:
\[ 1^2+2^2+\dots+n^2+(n+1)^2 = \frac{(n+1)(n+2)(2n+3)}{6} \]
Partiamo dal membro sinistro:
\[ 1^2+2^2+\dots+n^2+(n+1)^2 \]
Utilizziamo ora l’ipotesi induttiva:
\[ \frac{n(n+1)(2n+1)}{6}+(n+1)^2 \]
Per poter sommare i termini, scriviamo tutto con denominatore \(6\):
\[ \frac{n(n+1)(2n+1)}{6}+\frac{6(n+1)^2}{6} \]
Otteniamo:
\[ \frac{n(n+1)(2n+1)+6(n+1)^2}{6} \]
Notiamo che entrambi i termini del numeratore contengono il fattore \(n+1\). Lo raccogliamo:
\[ \frac{(n+1)\left[n(2n+1)+6(n+1)\right]}{6} \]
Sviluppiamo ora l’espressione tra parentesi:
\[ n(2n+1)+6(n+1) \]
Moltiplichiamo:
\[ 2n^2+n+6n+6 \]
Sommiamo i termini simili:
\[ 2n^2+7n+6 \]
Dobbiamo ora fattorizzare questo trinomio.
Cerchiamo due numeri il cui prodotto sia:
\[ 2\cdot6=12 \]
e la cui somma sia:
\[ 7 \]
I numeri sono \(3\) e \(4\). Otteniamo quindi:
\[ 2n^2+7n+6=(n+2)(2n+3) \]
Sostituendo:
\[ \frac{(n+1)(n+2)(2n+3)}{6} \]
che è esattamente la formula da dimostrare.
Conclusione
La proprietà è vera per \(n=1\) e il passo induttivo è stato dimostrato.
Per il principio di induzione matematica:
\[ 1^2+2^2+3^2+\dots+n^2=\frac{n(n+1)(2n+1)}{6} \]
per ogni \(n\geq1\).
Esercizio 5 — livello ★★☆☆☆
Dimostrare per induzione che:
\[ 1^3+2^3+3^3+\dots+n^3=\left(\frac{n(n+1)}{2}\right)^2 \]
Dimostrazione
Significato della formula
La formula afferma che la somma dei cubi dei primi \(n\) numeri naturali è uguale al quadrato della somma dei primi \(n\) numeri naturali.
Infatti:
\[ 1+2+3+\dots+n=\frac{n(n+1)}{2} \]
e quindi il membro destro:
\[ \left(\frac{n(n+1)}{2}\right)^2 \]
è proprio il quadrato di questa quantità .
Base induttiva
Verifichiamo la proprietà per \(n=1\).
Il membro sinistro vale:
\[ 1^3=1 \]
Il membro destro vale:
\[ \left(\frac{1(1+1)}{2}\right)^2 = \left(\frac{2}{2}\right)^2 = 1^2 = 1 \]
I due membri coincidono. La proprietà è vera per \(n=1\).
Ipotesi induttiva
Supponiamo che la formula sia vera per un certo numero naturale \(n\).
Assumiamo quindi:
\[ 1^3+2^3+3^3+\dots+n^3 = \left(\frac{n(n+1)}{2}\right)^2 \]
Questa è l’unica informazione che possiamo usare nel passo induttivo: non possiamo assumere direttamente la formula per \(n+1\), perché è proprio ciò che dobbiamo dimostrare.
Passo induttivo
Dobbiamo dimostrare che:
\[ 1^3+2^3+3^3+\dots+n^3+(n+1)^3 = \left(\frac{(n+1)(n+2)}{2}\right)^2 \]
Partiamo dal membro sinistro:
\[ 1^3+2^3+3^3+\dots+n^3+(n+1)^3 \]
Applichiamo l’ipotesi induttiva alla somma dei primi \(n\) cubi:
\[ \left(\frac{n(n+1)}{2}\right)^2+(n+1)^3 \]
Ora sviluppiamo il primo termine in modo da vedere meglio i fattori comuni:
\[ \left(\frac{n(n+1)}{2}\right)^2 = \frac{n^2(n+1)^2}{4} \]
Quindi otteniamo:
\[ \frac{n^2(n+1)^2}{4}+(n+1)^3 \]
Entrambi i termini contengono il fattore \((n+1)^2\). Lo raccogliamo:
\[ (n+1)^2\left(\frac{n^2}{4}+n+1\right) \]
A questo punto dobbiamo trasformare la parentesi in un quadrato. Portiamo tutto al denominatore \(4\):
\[ \frac{n^2}{4}+n+1 = \frac{n^2}{4}+\frac{4n}{4}+\frac{4}{4} \]
quindi:
\[ \frac{n^2}{4}+n+1 = \frac{n^2+4n+4}{4} \]
Il numeratore è un quadrato perfetto:
\[ n^2+4n+4=(n+2)^2 \]
Dunque:
\[ \frac{n^2}{4}+n+1 = \frac{(n+2)^2}{4} \]
Sostituendo nella nostra espressione:
\[ (n+1)^2\cdot\frac{(n+2)^2}{4} \]
Scriviamo il prodotto come quadrato:
\[ \frac{(n+1)^2(n+2)^2}{4} = \left(\frac{(n+1)(n+2)}{2}\right)^2 \]
Abbiamo ottenuto esattamente la formula richiesta per \(n+1\).
Conclusione
La proprietà è vera per \(n=1\) e abbiamo dimostrato che, se vale per \(n\), allora vale anche per \(n+1\).
Per il principio di induzione matematica:
\[ 1^3+2^3+3^3+\dots+n^3=\left(\frac{n(n+1)}{2}\right)^2 \]
per ogni \(n\geq1\).
Esercizio 6 — livello ★★☆☆☆
Dimostrare per induzione che \(5^n-1\) è divisibile per \(4\), per ogni \(n\geq1\).
Dimostrazione
Significato della proprietÃ
Dire che \(5^n-1\) è divisibile per \(4\) significa dire che esiste un numero intero \(k\) tale che:
\[ 5^n-1=4k \]
In una dimostrazione per induzione sulla divisibilità , l’ipotesi induttiva viene quasi sempre tradotta proprio in questa forma.
Base induttiva
Verifichiamo la proprietà per \(n=1\).
Calcoliamo:
\[ 5^1-1=5-1=4 \]
Poiché \(4\) è divisibile per \(4\), la proprietà è vera per \(n=1\).
Ipotesi induttiva
Supponiamo che la proprietà sia vera per un certo \(n\geq1\).
Questo significa che \(5^n-1\) è divisibile per \(4\). Quindi esiste un intero \(k\) tale che:
\[ 5^n-1=4k \]
Questa forma è molto importante: ci permette di usare concretamente l’ipotesi induttiva nei calcoli.
Passo induttivo
Dobbiamo dimostrare che anche \(5^{n+1}-1\) è divisibile per \(4\).
Partiamo dall’espressione:
\[ 5^{n+1}-1 \]
Scriviamo \(5^{n+1}\) come \(5\cdot5^n\):
\[ 5^{n+1}-1=5\cdot5^n-1 \]
Ora vogliamo far comparire \(5^n-1\), perché è proprio l’espressione che compare nell’ipotesi induttiva.
Per questo riscriviamo:
\[ 5\cdot5^n-1=5(5^n-1)+4 \]
Verifichiamo mentalmente il passaggio:
\[ 5(5^n-1)+4=5\cdot5^n-5+4=5\cdot5^n-1 \]
Ora possiamo usare l’ipotesi induttiva:
\[ 5^n-1=4k \]
quindi:
\[ 5(5^n-1)+4=5\cdot4k+4 \]
Raccogliamo \(4\):
\[ 5\cdot4k+4=4(5k+1) \]
Poiché \(5k+1\) è un numero intero, l’espressione \(4(5k+1)\) è divisibile per \(4\).
Quindi \(5^{n+1}-1\) è divisibile per \(4\).
Conclusione
La proprietà è vera per \(n=1\) e abbiamo dimostrato che, se \(5^n-1\) è divisibile per \(4\), allora anche \(5^{n+1}-1\) è divisibile per \(4\).
Per il principio di induzione matematica, \(5^n-1\) è divisibile per \(4\) per ogni \(n\geq1\).
Esercizio 7 — livello ★★☆☆☆
Dimostrare per induzione che \(7^n-1\) è divisibile per \(6\), per ogni \(n\geq1\).
Dimostrazione
Significato della proprietÃ
Dire che \(7^n-1\) è divisibile per \(6\) significa dire che \(7^n-1\) è un multiplo di \(6\).
In simboli, dobbiamo dimostrare che esiste un intero \(k\) tale che:
\[ 7^n-1=6k \]
Base induttiva
Verifichiamo la proprietà per \(n=1\).
Calcoliamo:
\[ 7^1-1=7-1=6 \]
Poiché \(6\) è divisibile per \(6\), la proprietà è vera per \(n=1\).
Ipotesi induttiva
Supponiamo che la proprietà sia vera per un certo \(n\geq1\).
Questo significa che \(7^n-1\) è divisibile per \(6\). Dunque esiste un intero \(k\) tale che:
\[ 7^n-1=6k \]
L’obiettivo del passo induttivo sarà far comparire proprio l’espressione \(7^n-1\), perché è quella che possiamo sostituire usando l’ipotesi induttiva.
Passo induttivo
Dobbiamo dimostrare che \(7^{n+1}-1\) è divisibile per \(6\).
Partiamo da:
\[ 7^{n+1}-1 \]
Scriviamo \(7^{n+1}\) come \(7\cdot7^n\):
\[ 7^{n+1}-1=7\cdot7^n-1 \]
Ora riscriviamo questa espressione in modo da far comparire \(7^n-1\):
\[ 7\cdot7^n-1=7(7^n-1)+6 \]
Infatti:
\[ 7(7^n-1)+6=7\cdot7^n-7+6=7\cdot7^n-1 \]
Usando l’ipotesi induttiva \(7^n-1=6k\), otteniamo:
\[ 7(7^n-1)+6=7\cdot6k+6 \]
Raccogliamo il fattore \(6\):
\[ 7\cdot6k+6=6(7k+1) \]
Poiché \(7k+1\) è un intero, \(6(7k+1)\) è divisibile per \(6\).
Quindi \(7^{n+1}-1\) è divisibile per \(6\).
Conclusione
La proprietà è vera per \(n=1\) e abbiamo dimostrato che la divisibilità per \(6\) si trasmette dal caso \(n\) al caso \(n+1\).
Per il principio di induzione matematica, \(7^n-1\) è divisibile per \(6\) per ogni \(n\geq1\).
Esercizio 8 — livello ★★★☆☆
Dimostrare per induzione che:
\[ 11^n-4^n \]
è divisibile per \(7\), per ogni \(n\geq1\).
Dimostrazione
Significato della proprietÃ
Dobbiamo dimostrare che la differenza \(11^n-4^n\) è sempre un multiplo di \(7\).
In altre parole, vogliamo provare che esiste un intero \(k\) tale che:
\[ 11^n-4^n=7k \]
Questo esercizio è leggermente più delicato dei precedenti, perché contiene due potenze diverse. Nel passo induttivo dovremo quindi trasformare l’espressione con attenzione, in modo da far comparire \(11^n-4^n\).
Base induttiva
Verifichiamo la proprietà per \(n=1\).
Calcoliamo:
\[ 11^1-4^1=11-4=7 \]
Poiché \(7\) è divisibile per \(7\), la proprietà è vera per \(n=1\).
Ipotesi induttiva
Supponiamo che la proprietà sia vera per un certo \(n\geq1\).
Quindi supponiamo che \(11^n-4^n\) sia divisibile per \(7\). Equivalentemente, esiste un intero \(k\) tale che:
\[ 11^n-4^n=7k \]
Nel passo successivo dovremo usare proprio questa informazione.
Passo induttivo
Dobbiamo dimostrare che:
\[ 11^{n+1}-4^{n+1} \]
è divisibile per \(7\).
Scriviamo le potenze al passo successivo:
\[ 11^{n+1}-4^{n+1}=11\cdot11^n-4\cdot4^n \]
Vogliamo far comparire \(11^n-4^n\). Per riuscirci, sommiamo e sottraiamo lo stesso termine \(11\cdot4^n\):
\[ 11\cdot11^n-4\cdot4^n = 11\cdot11^n-11\cdot4^n+11\cdot4^n-4\cdot4^n \]
Questo passaggio non cambia il valore dell’espressione, perché abbiamo aggiunto e sottratto la stessa quantità .
Ora raccogliamo nei primi due termini il fattore \(11\), e negli ultimi due termini il fattore \(4^n\):
\[ 11(11^n-4^n)+(11-4)4^n \]
Poiché \(11-4=7\), otteniamo:
\[ 11(11^n-4^n)+7\cdot4^n \]
Ora possiamo usare l’ipotesi induttiva:
\[ 11^n-4^n=7k \]
Sostituendo:
\[ 11(11^n-4^n)+7\cdot4^n = 11\cdot7k+7\cdot4^n \]
Raccogliamo \(7\):
\[ 11\cdot7k+7\cdot4^n = 7(11k+4^n) \]
Poiché \(11k+4^n\) è un intero, l’espressione è divisibile per \(7\).
Quindi:
\[ 7\mid(11^{n+1}-4^{n+1}) \]
Conclusione
La proprietà è vera per \(n=1\) e il passo induttivo è stato dimostrato.
Per il principio di induzione matematica, \(11^n-4^n\) è divisibile per \(7\) per ogni \(n\geq1\).
Esercizio 9 — livello ★★★☆☆
Dimostrare per induzione che:
\[ 2^n \geq n+1 \]
per ogni \(n\geq0\).
Dimostrazione
Significato della proprietÃ
La disuguaglianza afferma che la potenza \(2^n\) cresce almeno quanto l’espressione lineare \(n+1\).
In una dimostrazione per induzione sulle disuguaglianze, il punto delicato è usare l’ipotesi induttiva senza perdere il verso della disuguaglianza.
Base induttiva
Verifichiamo la proprietà per \(n=0\).
Il membro sinistro vale:
\[ 2^0=1 \]
Il membro destro vale:
\[ 0+1=1 \]
Quindi:
\[ 2^0\geq0+1 \]
La proprietà è vera per \(n=0\).
Ipotesi induttiva
Supponiamo che la proprietà sia vera per un certo \(n\geq0\).
Assumiamo quindi:
\[ 2^n\geq n+1 \]
Questa ipotesi ci dice che possiamo sostituire \(2^n\) con una quantità non più piccola di \(n+1\).
Passo induttivo
Dobbiamo dimostrare che:
\[ 2^{n+1}\geq n+2 \]
Partiamo dal membro sinistro:
\[ 2^{n+1} \]
Scriviamolo come:
\[ 2^{n+1}=2\cdot2^n \]
Poiché per ipotesi induttiva \(2^n\geq n+1\), moltiplicando entrambi i membri per \(2\), che è positivo, il verso della disuguaglianza resta invariato:
\[ 2\cdot2^n\geq2(n+1) \]
Quindi:
\[ 2^{n+1}\geq2n+2 \]
Ora dobbiamo confrontare \(2n+2\) con \(n+2\), perché l’obiettivo è ottenere \(n+2\).
Poiché \(n\geq0\), si ha:
\[ 2n+2\geq n+2 \]
Infatti la differenza tra i due membri è:
\[ (2n+2)-(n+2)=n\geq0 \]
Combinando le due disuguaglianze:
\[ 2^{n+1}\geq2n+2\geq n+2 \]
quindi:
\[ 2^{n+1}\geq n+2 \]
Conclusione
La proprietà è vera per \(n=0\) e abbiamo dimostrato che, se vale per \(n\), allora vale per \(n+1\).
Per il principio di induzione matematica:
\[ 2^n\geq n+1 \]
per ogni \(n\geq0\).
Esercizio 10 — livello ★★★☆☆
Dimostrare per induzione che:
\[ 3^n>n \]
per ogni \(n\geq1\).
Dimostrazione
Significato della proprietÃ
La disuguaglianza afferma che la potenza \(3^n\) è sempre maggiore dell’esponente \(n\), per ogni \(n\geq1\).
Anche se la proprietà è intuitivamente evidente, perché le potenze di \(3\) crescono molto rapidamente, l’obiettivo è dimostrarla in modo rigoroso usando l’induzione.
Base induttiva
Verifichiamo la proprietà per \(n=1\).
Il membro sinistro vale:
\[ 3^1=3 \]
Il membro destro vale:
\[ 1 \]
Poiché:
\[ 3>1 \]
la proprietà è vera per \(n=1\).
Ipotesi induttiva
Supponiamo che la proprietà sia vera per un certo \(n\geq1\).
Assumiamo quindi:
\[ 3^n>n \]
Questa è l’informazione che dovremo usare per dimostrare la disuguaglianza al passo successivo.
Passo induttivo
Dobbiamo dimostrare che:
\[ 3^{n+1}>n+1 \]
Partiamo da:
\[ 3^{n+1} \]
Scriviamo:
\[ 3^{n+1}=3\cdot3^n \]
Usando l’ipotesi induttiva \(3^n>n\), e moltiplicando per \(3>0\), otteniamo:
\[ 3\cdot3^n>3n \]
Quindi:
\[ 3^{n+1}>3n \]
Ora dobbiamo confrontare \(3n\) con \(n+1\).
Per \(n\geq1\), si ha:
\[ 3n>n+1 \]
Infatti:
\[ 3n-(n+1)=2n-1 \]
e, se \(n\geq1\), allora:
\[ 2n-1\geq1>0 \]
Dunque:
\[ 3n>n+1 \]
Combinando:
\[ 3^{n+1}>3n>n+1 \]
quindi:
\[ 3^{n+1}>n+1 \]
Conclusione
La proprietà è vera per \(n=1\) e il passo induttivo è stato dimostrato.
Per il principio di induzione matematica:
\[ 3^n>n \]
per ogni \(n\geq1\).
Esercizio 11 — livello ★★★★☆
Dimostrare per induzione che:
\[ 2^n < n! \]
per ogni \(n\geq4\).
Dimostrazione
Significato della proprietÃ
La disuguaglianza confronta una potenza con un fattoriale.
Il fattoriale \(n!\) è il prodotto:
\[ n!=1\cdot2\cdot3\cdot\dots\cdot n \]
La proprietà afferma che, a partire da \(n=4\), il fattoriale è sempre maggiore di \(2^n\).
Base induttiva
Verifichiamo la proprietà per \(n=4\).
Il membro sinistro vale:
\[ 2^4=16 \]
Il membro destro vale:
\[ 4!=1\cdot2\cdot3\cdot4=24 \]
Poiché:
\[ 16<24 \]
la proprietà è vera per \(n=4\).
Ipotesi induttiva
Supponiamo che la proprietà sia vera per un certo \(n\geq4\).
Assumiamo quindi:
\[ 2^n < n! \]
Questa ipotesi ci permette di confrontare \(2^n\) con \(n!\). Nel passo successivo dovremo confrontare \(2^{n+1}\) con \((n+1)!\).
Passo induttivo
Dobbiamo dimostrare che:
\[ 2^{n+1}<(n+1)! \]
Partiamo dal membro sinistro:
\[ 2^{n+1} \]
Scriviamolo come:
\[ 2^{n+1}=2\cdot2^n \]
Per ipotesi induttiva sappiamo che:
\[ 2^n < n! \]
Moltiplicando entrambi i membri per \(2>0\), otteniamo:
\[ 2\cdot2^n<2n! \]
Quindi:
\[ 2^{n+1}<2n! \]
Ora dobbiamo collegare \(2n!\) con \((n+1)!\). Ricordiamo che:
\[ (n+1)!=(n+1)n! \]
Poiché \(n\geq4\), allora:
\[ n+1\geq5 \]
quindi:
\[ 2 < n+1 \]
Moltiplicando per \(n!>0\), otteniamo:
\[ 2n!<(n+1)n! \]
cioè:
\[ 2n!<(n+1)! \]
Combinando le due disuguaglianze:
\[ 2^{n+1}<2n!<(n+1)! \]
dunque:
\[ 2^{n+1}<(n+1)! \]
Conclusione
La proprietà è vera per \(n=4\) e abbiamo dimostrato che, se vale per \(n\), allora vale anche per \(n+1\).
Per il principio di induzione matematica:
\[ 2^n < n! \]
per ogni \(n\geq4\).
Esercizio 12 — livello ★★★★☆
Dimostrare per induzione che:
\[ 4^n\geq3n+1 \]
per ogni \(n\geq0\).
Dimostrazione
Significato della proprietÃ
La proprietà confronta una crescita esponenziale, rappresentata da \(4^n\), con una crescita lineare, rappresentata da \(3n+1\).
L’induzione ci permette di dimostrare che questa disuguaglianza è valida per ogni numero naturale \(n\geq0\), senza dover controllare i singoli casi uno per uno.
Base induttiva
Verifichiamo la proprietà per \(n=0\).
Il membro sinistro vale:
\[ 4^0=1 \]
Il membro destro vale:
\[ 3\cdot0+1=1 \]
I due membri sono uguali, quindi:
\[ 4^0\geq3\cdot0+1 \]
La proprietà è vera per \(n=0\).
Ipotesi induttiva
Supponiamo che la proprietà sia vera per un certo \(n\geq0\).
Assumiamo quindi:
\[ 4^n\geq3n+1 \]
Dobbiamo usare questa informazione per dimostrare la disuguaglianza al passo successivo.
Passo induttivo
Dobbiamo dimostrare che:
\[ 4^{n+1}\geq3(n+1)+1 \]
Poiché:
\[ 4^{n+1}=4\cdot4^n \]
possiamo usare l’ipotesi induttiva. Dal momento che \(4>0\), moltiplicando per \(4\) il verso della disuguaglianza non cambia:
\[ 4\cdot4^n\geq4(3n+1) \]
Quindi:
\[ 4^{n+1}\geq12n+4 \]
Ora vogliamo ottenere:
\[ 3(n+1)+1 \]
Sviluppiamo questa espressione:
\[ 3(n+1)+1=3n+3+1=3n+4 \]
Dobbiamo quindi confrontare \(12n+4\) con \(3n+4\).
Poiché \(n\geq0\), si ha:
\[ 12n+4\geq3n+4 \]
Infatti:
\[ (12n+4)-(3n+4)=9n\geq0 \]
Quindi:
\[ 12n+4\geq3n+4=3(n+1)+1 \]
Combinando:
\[ 4^{n+1}\geq12n+4\geq3(n+1)+1 \]
perciò:
\[ 4^{n+1}\geq3(n+1)+1 \]
Conclusione
La proprietà è vera per \(n=0\) e abbiamo dimostrato che la sua validità per \(n\) implica la sua validità per \(n+1\).
Per il principio di induzione matematica:
\[ 4^n\geq3n+1 \]
per ogni \(n\geq0\).
Esercizio 13 — livello ★★★★☆
Dimostrare per induzione che:
\[ 1+3+3^2+\dots+3^n=\frac{3^{n+1}-1}{2} \]
per ogni \(n\geq0\).
Dimostrazione
Significato della formula
Il membro sinistro è la somma delle prime potenze di \(3\), a partire da \(3^0=1\):
\[ 1+3+3^2+\dots+3^n \]
La formula afferma che questa somma può essere calcolata direttamente tramite:
\[ \frac{3^{n+1}-1}{2} \]
Base induttiva
Verifichiamo la proprietà per \(n=0\).
Il membro sinistro vale:
\[ 1 \]
Il membro destro vale:
\[ \frac{3^{0+1}-1}{2} = \frac{3-1}{2} = \frac{2}{2} = 1 \]
I due membri coincidono. La proprietà è vera per \(n=0\).
Ipotesi induttiva
Supponiamo che la formula sia vera per un certo \(n\geq0\).
Assumiamo quindi:
\[ 1+3+3^2+\dots+3^n=\frac{3^{n+1}-1}{2} \]
Passo induttivo
Dobbiamo dimostrare che:
\[ 1+3+3^2+\dots+3^n+3^{n+1} = \frac{3^{n+2}-1}{2} \]
Partiamo dal membro sinistro:
\[ 1+3+3^2+\dots+3^n+3^{n+1} \]
Usiamo l’ipotesi induttiva sulla parte iniziale della somma:
\[ \frac{3^{n+1}-1}{2}+3^{n+1} \]
Portiamo tutto allo stesso denominatore:
\[ \frac{3^{n+1}-1}{2}+\frac{2\cdot3^{n+1}}{2} \]
Sommiamo i numeratori:
\[ \frac{3^{n+1}-1+2\cdot3^{n+1}}{2} \]
Ora raccogliamo i termini con \(3^{n+1}\):
\[ 3^{n+1}+2\cdot3^{n+1}=3\cdot3^{n+1} \]
Quindi:
\[ \frac{3\cdot3^{n+1}-1}{2} \]
Per la proprietà delle potenze:
\[ 3\cdot3^{n+1}=3^{n+2} \]
Otteniamo dunque:
\[ \frac{3^{n+2}-1}{2} \]
che è esattamente la formula al passo \(n+1\).
Conclusione
La proprietà è vera per \(n=0\) e abbiamo dimostrato che, se vale per \(n\), allora vale anche per \(n+1\).
Per il principio di induzione matematica:
\[ 1+3+3^2+\dots+3^n=\frac{3^{n+1}-1}{2} \]
per ogni \(n\geq0\).
Esercizio 14 — livello ★★★★☆
Dimostrare per induzione che:
\[ 8^n-1 \]
è divisibile per \(7\), per ogni \(n\geq1\).
Dimostrazione
Significato della proprietÃ
Dobbiamo dimostrare che \(8^n-1\) è sempre un multiplo di \(7\).
Equivalentemente, dobbiamo mostrare che esiste un intero \(k\) tale che:
\[ 8^n-1=7k \]
Base induttiva
Verifichiamo la proprietà per \(n=1\).
Calcoliamo:
\[ 8^1-1=8-1=7 \]
Poiché \(7\) è divisibile per \(7\), la proprietà è vera per \(n=1\).
Ipotesi induttiva
Supponiamo che la proprietà sia vera per un certo \(n\geq1\).
Allora esiste un intero \(k\) tale che:
\[ 8^n-1=7k \]
Nel passo induttivo dovremo far comparire l’espressione \(8^n-1\), così da poter usare l’ipotesi induttiva.
Passo induttivo
Dobbiamo dimostrare che \(8^{n+1}-1\) è divisibile per \(7\).
Partiamo da:
\[ 8^{n+1}-1 \]
Scriviamo \(8^{n+1}\) come:
\[ 8^{n+1}=8\cdot8^n \]
Quindi:
\[ 8^{n+1}-1=8\cdot8^n-1 \]
Ora riscriviamo l’espressione facendo comparire \(8^n-1\):
\[ 8\cdot8^n-1=8(8^n-1)+7 \]
Infatti:
\[ 8(8^n-1)+7=8\cdot8^n-8+7=8\cdot8^n-1 \]
Usando l’ipotesi induttiva \(8^n-1=7k\), otteniamo:
\[ 8(8^n-1)+7=8\cdot7k+7 \]
Raccogliamo \(7\):
\[ 8\cdot7k+7=7(8k+1) \]
Poiché \(8k+1\) è un numero intero, l’espressione \(7(8k+1)\) è divisibile per \(7\).
Quindi \(8^{n+1}-1\) è divisibile per \(7\).
Conclusione
La proprietà è vera per \(n=1\) e abbiamo dimostrato che la divisibilità si trasmette dal caso \(n\) al caso \(n+1\).
Per il principio di induzione matematica, \(8^n-1\) è divisibile per \(7\) per ogni \(n\geq1\).
Esercizio 15 — livello ★★★★☆
Dimostrare per induzione che:
\[ 9^n-1 \]
è divisibile per \(8\), per ogni \(n\geq1\).
Dimostrazione
Significato della proprietÃ
Dobbiamo dimostrare che \(9^n-1\) è sempre un multiplo di \(8\).
In simboli, vogliamo dimostrare che esiste un intero \(k\) tale che:
\[ 9^n-1=8k \]
Base induttiva
Verifichiamo la proprietà per \(n=1\).
Calcoliamo:
\[ 9^1-1=9-1=8 \]
Poiché \(8\) è divisibile per \(8\), la proprietà è vera per \(n=1\).
Ipotesi induttiva
Supponiamo che la proprietà sia vera per un certo \(n\geq1\).
Allora esiste un intero \(k\) tale che:
\[ 9^n-1=8k \]
Passo induttivo
Dobbiamo dimostrare che \(9^{n+1}-1\) è divisibile per \(8\).
Partiamo da:
\[ 9^{n+1}-1 \]
Scriviamo:
\[ 9^{n+1}=9\cdot9^n \]
quindi:
\[ 9^{n+1}-1=9\cdot9^n-1 \]
Ora vogliamo far comparire \(9^n-1\), perché è l’espressione controllata dall’ipotesi induttiva.
Riscriviamo:
\[ 9\cdot9^n-1=9(9^n-1)+8 \]
Infatti:
\[ 9(9^n-1)+8=9\cdot9^n-9+8=9\cdot9^n-1 \]
Usando l’ipotesi induttiva:
\[ 9^n-1=8k \]
otteniamo:
\[ 9(9^n-1)+8=9\cdot8k+8 \]
Raccogliamo \(8\):
\[ 9\cdot8k+8=8(9k+1) \]
Poiché \(9k+1\) è un intero, l’espressione è divisibile per \(8\).
Quindi \(9^{n+1}-1\) è divisibile per \(8\).
Conclusione
La proprietà è vera per \(n=1\) e il passo induttivo è stato dimostrato.
Per il principio di induzione matematica, \(9^n-1\) è divisibile per \(8\) per ogni \(n\geq1\).
Esercizio 16 — livello ★★★★★
Dimostrare per induzione che:
\[ 1\cdot1!+2\cdot2!+3\cdot3!+\dots+n\cdot n!=(n+1)!-1 \]
per ogni \(n\geq1\).
Dimostrazione
Significato della formula
Il membro sinistro è una somma i cui termini hanno la forma:
\[ k\cdot k! \]
La formula afferma che questa somma si semplifica in modo sorprendentemente compatto:
\[ (n+1)!-1 \]
In questo esercizio il punto centrale è riconoscere come il termine successivo \((n+1)(n+1)!\) si combini con \((n+1)!\).
Base induttiva
Verifichiamo la proprietà per \(n=1\).
Il membro sinistro vale:
\[ 1\cdot1!=1 \]
Il membro destro vale:
\[ (1+1)!-1=2!-1=2-1=1 \]
I due membri coincidono. La proprietà è vera per \(n=1\).
Ipotesi induttiva
Supponiamo che la formula sia vera per un certo \(n\geq1\).
Assumiamo quindi:
\[ 1\cdot1!+2\cdot2!+\dots+n\cdot n!=(n+1)!-1 \]
Passo induttivo
Dobbiamo dimostrare che:
\[ 1\cdot1!+2\cdot2!+\dots+n\cdot n!+(n+1)(n+1)!=(n+2)!-1 \]
Partiamo dal membro sinistro:
\[ 1\cdot1!+2\cdot2!+\dots+n\cdot n!+(n+1)(n+1)! \]
Usiamo l’ipotesi induttiva sulla somma fino a \(n\):
\[ (n+1)!-1+(n+1)(n+1)! \]
Ora raccogliamo il fattore comune \((n+1)!\):
\[ (n+1)!+(n+1)(n+1)!-1 \]
Nei primi due termini compare \((n+1)!\), quindi:
\[ (n+1)!\left[1+(n+1)\right]-1 \]
Semplifichiamo la parentesi:
\[ 1+(n+1)=n+2 \]
quindi:
\[ (n+1)!(n+2)-1 \]
Poiché:
\[ (n+2)!=(n+2)(n+1)!, \]
otteniamo:
\[ (n+2)!-1 \]
che è esattamente la formula richiesta per il passo \(n+1\).
Conclusione
La proprietà è vera per \(n=1\) e abbiamo dimostrato che, se vale per \(n\), allora vale anche per \(n+1\).
Per il principio di induzione matematica:
\[ 1\cdot1!+2\cdot2!+3\cdot3!+\dots+n\cdot n!=(n+1)!-1 \]
per ogni \(n\geq1\).
Esercizio 17 — livello ★★★★★
Dimostrare per induzione che:
\[ 1+\frac{1}{2}+\frac{1}{4}+\dots+\frac{1}{2^n} = 2-\frac{1}{2^n} \]
per ogni \(n\geq0\).
Dimostrazione
Significato della formula
Il membro sinistro è una somma di potenze negative di \(2\), cioè una somma geometrica:
\[ 1+\frac{1}{2}+\frac{1}{4}+\dots+\frac{1}{2^n} \]
La formula afferma che questa somma è uguale a:
\[ 2-\frac{1}{2^n} \]
Il termine \(\frac{1}{2^n}\) misura quanto la somma è ancora distante da \(2\).
Base induttiva
Verifichiamo la proprietà per \(n=0\).
Il membro sinistro contiene solo il primo termine:
\[ 1 \]
Il membro destro vale:
\[ 2-\frac{1}{2^0}=2-1=1 \]
I due membri coincidono. La proprietà è vera per \(n=0\).
Ipotesi induttiva
Supponiamo che la formula sia vera per un certo \(n\geq0\).
Assumiamo quindi:
\[ 1+\frac{1}{2}+\frac{1}{4}+\dots+\frac{1}{2^n} = 2-\frac{1}{2^n} \]
Questa ipotesi descrive la somma fino al termine \(\frac{1}{2^n}\). Nel passo successivo dovremo aggiungere il nuovo termine \(\frac{1}{2^{n+1}}\).
Passo induttivo
Dobbiamo dimostrare che:
\[ 1+\frac{1}{2}+\frac{1}{4}+\dots+\frac{1}{2^n}+\frac{1}{2^{n+1}} = 2-\frac{1}{2^{n+1}} \]
Partiamo dal membro sinistro:
\[ 1+\frac{1}{2}+\frac{1}{4}+\dots+\frac{1}{2^n}+\frac{1}{2^{n+1}} \]
Usiamo l’ipotesi induttiva sulla somma fino a \(\frac{1}{2^n}\):
\[ 2-\frac{1}{2^n}+\frac{1}{2^{n+1}} \]
Ora dobbiamo semplificare gli ultimi due termini:
\[ -\frac{1}{2^n}+\frac{1}{2^{n+1}} \]
Osserviamo che:
\[ \frac{1}{2^n}=\frac{2}{2^{n+1}} \]
Infatti \(2^{n+1}=2\cdot2^n\).
Quindi:
\[ -\frac{1}{2^n}+\frac{1}{2^{n+1}} = -\frac{2}{2^{n+1}}+\frac{1}{2^{n+1}} \]
Sommiamo le frazioni:
\[ -\frac{2}{2^{n+1}}+\frac{1}{2^{n+1}} = -\frac{1}{2^{n+1}} \]
Pertanto:
\[ 2-\frac{1}{2^n}+\frac{1}{2^{n+1}} = 2-\frac{1}{2^{n+1}} \]
Abbiamo ottenuto esattamente la formula richiesta per \(n+1\).
Conclusione
La proprietà è vera per \(n=0\) e il passo induttivo è stato dimostrato.
Per il principio di induzione matematica:
\[ 1+\frac{1}{2}+\frac{1}{4}+\dots+\frac{1}{2^n} = 2-\frac{1}{2^n} \]
per ogni \(n\geq0\).
Esercizio 18 — livello ★★★★★
Dimostrare per induzione che:
\[ \sum_{k=1}^{n} k(k+1)=\frac{n(n+1)(n+2)}{3} \]
per ogni \(n\geq1\).
Dimostrazione
Significato della formula
Il simbolo:
\[ \sum_{k=1}^{n} k(k+1) \]
indica la somma dei termini della forma \(k(k+1)\), al variare di \(k\) da \(1\) a \(n\).
Esplicitamente:
\[ \sum_{k=1}^{n} k(k+1) = 1\cdot2+2\cdot3+3\cdot4+\dots+n(n+1) \]
La formula afferma che questa somma può essere scritta in forma chiusa come:
\[ \frac{n(n+1)(n+2)}{3} \]
Base induttiva
Verifichiamo la proprietà per \(n=1\).
Il membro sinistro vale:
\[ \sum_{k=1}^{1} k(k+1)=1(1+1)=2 \]
Il membro destro vale:
\[ \frac{1(1+1)(1+2)}{3} = \frac{1\cdot2\cdot3}{3} = 2 \]
I due membri coincidono. La proprietà è vera per \(n=1\).
Ipotesi induttiva
Supponiamo che la formula sia vera per un certo \(n\geq1\).
Assumiamo quindi:
\[ \sum_{k=1}^{n} k(k+1)=\frac{n(n+1)(n+2)}{3} \]
Questa ipotesi descrive la somma fino al termine \(n(n+1)\). Nel passo successivo dovremo aggiungere il termine corrispondente a \(k=n+1\).
Passo induttivo
Dobbiamo dimostrare che:
\[ \sum_{k=1}^{n+1} k(k+1)=\frac{(n+1)(n+2)(n+3)}{3} \]
Scriviamo la somma fino a \(n+1\) separando l’ultimo termine:
\[ \sum_{k=1}^{n+1} k(k+1) = \sum_{k=1}^{n} k(k+1)+(n+1)(n+2) \]
Ora usiamo l’ipotesi induttiva:
\[ \frac{n(n+1)(n+2)}{3}+(n+1)(n+2) \]
I due termini hanno in comune il fattore \((n+1)(n+2)\). Lo raccogliamo:
\[ (n+1)(n+2)\left(\frac{n}{3}+1\right) \]
Ora trasformiamo la parentesi:
\[ \frac{n}{3}+1=\frac{n}{3}+\frac{3}{3}=\frac{n+3}{3} \]
Sostituendo:
\[ (n+1)(n+2)\cdot\frac{n+3}{3} \]
cioè:
\[ \frac{(n+1)(n+2)(n+3)}{3} \]
Abbiamo ottenuto esattamente la formula richiesta per \(n+1\).
Conclusione
La proprietà è vera per \(n=1\) e il passo induttivo è stato dimostrato.
Per il principio di induzione matematica:
\[ \sum_{k=1}^{n} k(k+1)=\frac{n(n+1)(n+2)}{3} \]
per ogni \(n\geq1\).
Esercizio 19 — livello ★★★★★
Dimostrare per induzione che:
\[ 2^n>n^2 \]
per ogni \(n\geq5\).
Dimostrazione
Significato della proprietÃ
La disuguaglianza confronta una crescita esponenziale, \(2^n\), con una crescita polinomiale, \(n^2\).
La proprietà non è vera per tutti i valori iniziali di \(n\). Per esempio, per \(n=2\) si ha \(2^2=4\) e \(2^2=4\), quindi non vale la disuguaglianza stretta.
Per questo motivo la dimostrazione per induzione parte da \(n=5\).
Base induttiva
Verifichiamo la proprietà per \(n=5\).
Il membro sinistro vale:
\[ 2^5=32 \]
Il membro destro vale:
\[ 5^2=25 \]
Poiché:
\[ 32>25 \]
la proprietà è vera per \(n=5\).
Ipotesi induttiva
Supponiamo che la proprietà sia vera per un certo \(n\geq5\).
Assumiamo quindi:
\[ 2^n>n^2 \]
Dobbiamo usare questa informazione per dimostrare la disuguaglianza al passo successivo.
Passo induttivo
Dobbiamo dimostrare che:
\[ 2^{n+1}>(n+1)^2 \]
Partiamo dal membro sinistro:
\[ 2^{n+1} \]
Scriviamo:
\[ 2^{n+1}=2\cdot2^n \]
Per ipotesi induttiva sappiamo che:
\[ 2^n>n^2 \]
Moltiplicando per \(2>0\), otteniamo:
\[ 2\cdot2^n>2n^2 \]
Quindi:
\[ 2^{n+1}>2n^2 \]
Ora dobbiamo mostrare che \(2n^2\) è maggiore di \((n+1)^2\). Infatti, se:
\[ 2n^2>(n+1)^2 \]
allora, combinando le due disuguaglianze, otterremo:
\[ 2^{n+1}>2n^2>(n+1)^2 \]
Verifichiamo dunque che:
\[ 2n^2>(n+1)^2 \]
Portiamo tutto a sinistra:
\[ 2n^2-(n+1)^2 \]
Sviluppiamo il quadrato:
\[ (n+1)^2=n^2+2n+1 \]
quindi:
\[ 2n^2-(n+1)^2 = 2n^2-(n^2+2n+1) \]
cioè:
\[ n^2-2n-1 \]
Scriviamo questa espressione in una forma utile:
\[ n^2-2n-1=(n-1)^2-2 \]
Poiché \(n\geq5\), abbiamo \(n-1\geq4\), quindi:
\[ (n-1)^2\geq4^2=16 \]
Di conseguenza:
\[ (n-1)^2-2\geq16-2=14>0 \]
Quindi:
\[ 2n^2-(n+1)^2>0 \]
e dunque:
\[ 2n^2>(n+1)^2 \]
Combinando:
\[ 2^{n+1}>2n^2>(n+1)^2 \]
otteniamo:
\[ 2^{n+1}>(n+1)^2 \]
Conclusione
La proprietà è vera per \(n=5\) e abbiamo dimostrato che, se vale per \(n\), allora vale anche per \(n+1\).
Per il principio di induzione matematica:
\[ 2^n>n^2 \]
per ogni \(n\geq5\).
Esercizio 20 — livello ★★★★★
Dimostrare per induzione che ogni numero naturale \(n\geq2\) è primo oppure è prodotto di numeri primi.
Dimostrazione
Significato della proprietÃ
Questa proprietà è una forma essenziale del teorema fondamentale dell’aritmetica: ogni numero naturale maggiore o uguale a \(2\) può essere scomposto in fattori primi.
In questo esercizio useremo la induzione forte. A differenza dell’induzione ordinaria, nell’induzione forte, per dimostrare la proprietà per \(n\), possiamo assumere che essa sia vera per tutti i numeri naturali compresi tra \(2\) e \(n-1\).
Questa forma di induzione è naturale qui, perché se un numero non è primo, si scrive come prodotto di due numeri più piccoli.
Base induttiva
Verifichiamo la proprietà per \(n=2\).
Il numero \(2\) è primo.
Quindi la proprietà è vera per \(n=2\).
Ipotesi di induzione forte
Supponiamo che la proprietà sia vera per tutti i numeri naturali \(m\) tali che:
\[ 2\leq m\leq n \]
Ciò significa che ogni numero naturale compreso tra \(2\) e \(n\) è primo oppure è prodotto di numeri primi.
Passo induttivo
Dobbiamo dimostrare che la proprietà vale per \(n+1\).
Consideriamo quindi il numero \(n+1\).
Ci sono due possibilità .
Primo caso: \(n+1\) è primo
Se \(n+1\) è primo, allora la proprietà è immediatamente vera.
Infatti la proprietà richiede che il numero sia primo oppure prodotto di primi; in questo caso è direttamente primo.
Secondo caso: \(n+1\) non è primo
Se \(n+1\) non è primo, allora per definizione esistono due numeri naturali \(a\) e \(b\), maggiori di \(1\), tali che:
\[ n+1=ab \]
Inoltre, poiché \(a>1\) e \(b>1\), entrambi i fattori sono strettamente minori di \(n+1\).
Quindi:
\[ 2\leq a\leq n \qquad \text{e} \qquad 2\leq b\leq n \]
A questo punto possiamo applicare l’ipotesi di induzione forte sia ad \(a\) sia a \(b\).
Per ipotesi, \(a\) è primo oppure è prodotto di numeri primi.
Allo stesso modo, \(b\) è primo oppure è prodotto di numeri primi.
Poiché:
\[ n+1=ab \]
e sia \(a\) sia \(b\) sono primi oppure prodotti di primi, segue che anche \(n+1\) è prodotto di numeri primi.
Conclusione
Abbiamo dimostrato che, se la proprietà vale per tutti i numeri da \(2\) a \(n\), allora vale anche per \(n+1\).
Poiché la proprietà è vera per \(n=2\), per il principio di induzione forte concludiamo che ogni numero naturale \(n\geq2\) è primo oppure è prodotto di numeri primi.