Il Principio di Induzione Matematica – Problemi e Teoremi

In questo articolo studiamo il principio di induzione matematica, uno strumento potente utilizzato per risolvere problemi e dimostrare teoremi. L’idea fondamentale sulla quale si basa questo metodo è la ricorsione, un procedimento che permette di ridurre la risoluzione di un problema o la dimostrazione di un teorema ad un problema o teorema di dimensioni minori.
Non c’è una origine precisa di questo metodo di ragionamento matematico. In modo informale era usato già dagli antichi greci e dai matematici arabi e indiani, anche se non veniva utilizzato il termine induzione. Nel XVI secolo il metodo di dimostrazione tramite il procedimento di induzione è stato utilizzato da molti matematici. In particolare ricordiamo Francesco Maurolico, che utilizzò il principio in modo esteso nella sua opera ‘Arithmeticorum Libri Duo’ (1575). Tra gli altri matematici di quel periodo ricordiamo Fermat, Pascal e i vari esponenti della famiglia Bernoulli.
Il termine induzione venne introdotto dai matematici John Wallis (1616-1703) e Augustus De Morgan (1806-1871).
La formalizzazione del principio di induzione è stata inserita negli assiomi di Peano-Dedekind, che definiscono il sistema dei numeri naturali e quindi le operazioni dell’aritmetica elementare.

1) I numeri naturali

“Die ganzen Zahlen hat der liebe Gott geschaffen, alles andere ist Menschenwerk.”
(“Dio ha creato i numeri interi, tutto il resto è opera dell’uomo.”)

Leopold Kronecker (1823-1891)

I principali insiemi numerici utilizzati nella matematica sono i seguenti:

\[ \begin{array}{l} \mathbb{N}= \{0,1,2,3,\cdots\} \quad \text{(numeri naturali)} \\ \mathbb{Z} = \{\cdots,-3,-2,-1,0,1,2,3,\cdots\} \quad \text{(numeri interi)} \\ \mathbb{Q} =\left \{ \dfrac nm \mid n,m\in\mathbb{Z}\text{ e }m\neq 0\right\} \quad \text{(numeri razionali)} \\ \mathbb{R} =\text{numeri reali} \\ \mathbb{C} =\text{numeri complessi} \end{array} \]

Notiamo che \(\mathbb{N}\subset\mathbb{Z} \subset\mathbb{Q}\subset\mathbb{R}\subset\mathbb{C}\).
Indicheremo con \(\mathbb{Z}^{+}=\{1,2,3,4,\cdots\}\) l’insieme degli interi positivi.
I numeri naturali sono stati utilizzati fin dai tempi preistorici per le operazioni di conteggio con diverse modalità di rappresentazione. I numeri naturali sono uno dei pilastri fondamentali della Matematica, come afferma la famosa citazione di Kronecker. Una volta definiti i numeri naturali, è possibile definire in modo formale gli altri insiemi numerici: i numeri interi, i numeri razionali, i numerai reali e i numeri complessi.
Dal punto di vista storico il processo non è stato lineare: gli antichi greci conoscevano le frazioni e avevano sviluppato una conoscenza dei razionali e degli irrazionali, concepiti dal punto di vista geometrico come rapporti fra grandezze commensurabili o non. Alcuni numeri irrazionali famosi già nell’antichità sono \(\sqrt{2}\) e \(\pi\). L’introduzione dei numeri negativi, dei numeri irrazionali e dei numeri complessi ha richiesto un lungo processo di elaborazione prima di essere universalmente accettata.

1.1) Gli assiomi di Peano-Dedekind

Nonostante siano stati utilizzati fin dall’antichità, una definizione matematica formale dei numeri naturali è stata proposta solo nel secolo XIX, mediante gli assiomi di Peano-Dedekind, introdotti da Giuseppe Peano (1858-1932) nel \(1889\), che si è basato anche sui contributi di Dedekind (1831-1916).
L’idea base della definizione dei numeri naturali mediante gli assiomi di Peano-Dedekind è l’esistenza di un insieme di numeri \(\mathbb{N}\), con un particolare numero \(0\) che rappresenta il numero iniziale (il numero zero), e una funzione iniettiva \(s(n)\) chiamata funzione successore:

\[ \begin{array}{l} s(n): \mathbb{N} \to \mathbb{N} \end{array} \]

Il valore di \(s(n)\) è chiamato il successore di \(n\). Indichiamo con il simbolo \(1\) il successore dello zero, cioè \(s(0)=1\).
Gli assiomi di Peano-Dedekind sono i seguenti:

• \(0\) è un numero naturale;
• \(0\) non è il successore di nessun numero naturale;
• se \(n\) è un numero naturale, lo è anche \(s(n)\);
• la funzione \(s(n)\) è iniettiva, cioè se \(n \neq m\) allora \(s(n) \neq s(m)\);
• principio di induzione: se un insieme contiene lo zero e contiene il successore di ogni numero, allora contiene l’insieme dei numeri naturali.

Attraverso la nozione di successore \(s(n)\) di un numero naturale \(n\) è possibile definire le operazioni di addizione e moltiplicazione mediante delle equazioni ricorsive.

Addizione di numeri naturali (\(+)\):

\[ \begin{array}{l} n + 0 = n \\ n+s(m)=s(n+m) \\ \end{array} \]

Moltiplicazione di numeri naturali \((\cdot)\):

\[ \begin{array}{l} n \cdot 0 = 0 \\ n \cdot s(m)= n \cdot m +n \\ \end{array} \]

Si possono quindi dimostrare le proprietà commutativa, associativa e distributiva delle due operazioni. Dati \(m,n,q \in \mathbb{N}\) abbiamo

\[ \begin{array}{l} m + (n+q) = (m+n) + q \\ m + n = n +m \\ m \cdot (n \cdot q)= (m \cdot n) \cdot q \\ m \cdot n = n \cdot m \\ m \cdot (n+q)= m \cdot n + m \cdot q \\ \end{array} \]

Per semplicità l’operazione di moltiplicazione di due numeri \(n,m\) viene in genere indicata anche con la notazione senza il simbolo del punto, cioè \(nm\) invece di \(n \cdot m\).
Le operazioni di addizione e moltiplicazione sono definite per tutti i numeri naturali. Se \(n=m \cdot q\) si dice che \(n\) è un multiplo di \(m\) e di \(q\), mentre \(m,q\) si dicono divisori di \(n\). I numeri \(\{0,2,4,6, \cdots\}\) si dicono pari, mentre i numeri \(\{1,3,5,7, \cdots\}\)si dicono dispari.

Potenze dei numeri naturali
Dopo aver definito le operazioni di moltiplicazione, possiamo definire le potenze di un numero naturale \(a \neq 0\) in modo ricorsivo:

\[ \begin{array}{l} a^{0}=1 \\ a^{n+1}=a^{n}a \end{array} \]

Si dimostrano facilmente le note proprietà delle potenze:

\[ \begin{array}{l} a^{m+n}=a^{m}a^{n} \\ a^{mn}=(a^{m})^{n} \\ a^{n}b^{n}=(ab)^{n} \end{array} \]

Relazione di ordinamento
Nell’insieme dei numeri naturali possiamo definire la seguente relazione di ordinamento: per ogni coppia \(m,n \in \mathbb{N}\) diciamo che \(m\) è minore od uguale a \(n\) e scriviamo \(m \le n\) se esiste \( q \in \mathbb{N}\) tale che

\[ n = m+q \]

Teorema 1.1
La relazione \(\le\) ha le seguenti proprietà: \(\forall m,n \in \mathbb{N}\) si ha

• \( m \le n \text{ oppure } n \le m \quad \text{(ordinamento totale)} \)
• \( n \le n \quad \text{(proprietà riflessiva)}\)
• \(m \le n \land n \le m \implies m=n \quad \text{(proprietà anti-simmetrica)}\)
• \( m \le n \land n \le q \implies m \le q \quad \text{(proprietà transitiva)}\)

In base al teorema precedente l’insieme degli interi è totalmente ordinato, cioè:

\[ 0 \le 1 \le 2 \le 3 \le \cdots \]

Si possono dare anche ulteriori definizioni di relazioni di ordinamento:

\[ \begin{array}{l} m \ge n \quad \text{se } n \le m \quad \text{(maggiore od uguale)}\\ m \lt n \quad \text{se } m \le n \text{ e } m \neq n \quad \text{(minore)}\\ m \gt n \quad \text{se } n \lt m \quad \text{(maggiore)}\\ \end{array} \]

Teorema 1.2 – Legge di tricotomia dei naturali
Dati due numeri naturali \(m,n\) vale esattamente una delle tre relazioni:

\[ \begin{array}{l} m = n \\ m \lt n \\ m \gt n \end{array} \]

Operazioni di sottrazione e divisione
Si possono definire anche le operazioni di sottrazione e divisione fra due numeri naturali \(n,m\). Tuttavia con l’insieme dei numeri naturali la sottrazione è possibile solo se \( n \ge m\), mentre la divisione è possibile solo se \( n\) è un multiplo di \(m\).

Teorema 1.3 – Leggi di cancellazione

\[ \begin{array}{l} m + n = q + n \implies m = q \\ mn = qn \quad n \neq 0 \implies m=q \end{array} \]

Per la dimostrazione utilizzare il principio di induzione.

2) Il principio di induzione matematica

Il principio di induzione matematica è uno strumento fondamentale nella dimostrazione dei teoremi e nella soluzione dei problemi. Deriva direttamente dall’assioma di Peano-Dedekind che possiamo riformulare con questa piccola variazione. Sia \(S\) un insieme di numeri naturali con le seguenti due proprietà:

• \(S\) contiene un numero naturale \(n_{0} \ge 0\);
• Se \(S\) contiene un numero naturale \(n\) allora contiene anche il successore \(n+1\).

Se valgono entrambe le proprietà, allora \(S\) contiene tutti i numeri naturali maggiori od uguali a \(n_{0}\). Naturalmente se \(n_{0}=0\) allora \(S\) contiene tutti i numeri naturali.

2.1) Principio di induzione matematica debole

L’assioma di Peano-Dedekind è formulato con il linguaggio della teoria degli insiemi. Tuttavia per l’utilizzo nelle dimostrazioni è preferibile formulare l’assioma di Peano-Dedekind tramite il concetto di proprietà o proposizione. Ricordiamo che in logica una proposizione è un’affermazione che può assumere soltanto i valori vero o falso.

Principio di induzione matematica (forma debole)
Sia \(P(n)\) una proprietà relativa ai numeri naturali \(n \ge n_{0}\), dove \(n_{0} \ge 0\). Consideriamo le seguenti due proposizioni:

• 1) \(P(n)\) è vera per \(n=n_{0}\);
• 2) dato un valore qualsiasi \(n \ge n_{0}\), se \(P(n)\) è vera allora è vera anche \(P(n+1)\).

Se entrambe le proposizioni \(1,2\) sono vere, allora la proprietà \(P(n)\) è vera per tutti i numeri naturali maggiori od uguali a \(n_{0}\).
In genere si assume il valore \(n_{0}\) uguale a \(0\) oppure \(1\). Tuttavia può anche essere un valore maggiore.

Il principio di induzione permette di dimostrare delle proprietà per un numero infinito di casi, mediante un numero finito di passi. Il metodo di dimostrazione che si basa sul principio di induzione consiste in due passi principali:

• a) la base induttiva: dimostriamo che la proposizione \(P(n)\) è vera quando \(n=n_{0}\);
• b) il passo induttivo: dimostriamo che, se la proposizione \(P(n)\) è vera per un arbitrario numero \(n \ge n_{0}\), allora à vera anche per il numero successivo \(n+1\).

Se completiamo entrambi i due passi, allora abbiamo dimostrato che la proposizione \(P(n)\) è vera per ogni \(n \ge n_{0}\).

Esempio 2.1

\[ S_{1}(n)= 1 + 2+ \cdots + n = \frac{n(n+1)}{2} \]

La formula è vera per \(n=1\), in quanto \(S_{1}(1)=\dfrac{1(1+1)}{2}=1\). Supponiamola vera per un generico numero naturale \(n \ge 1\). Dobbiamo dimostrare che è vera anche per \(n+1\), cioè

\[ S_{1}(n+1)=\dfrac{(n+1)(n+2)}{2} \]

Facendo i calcoli abbiamo

\[ S_{1}(n+1)= S_{1}(n)+ (n+1)= \frac{n(n+1)}{2}+ (n+1)= \frac{(n+1)(n+2)}{2} \]

Quindi la formula è vera per ogni numero naturale.

Esercizio 2.1
Mediante il metodo di induzione dimostrare che

\[ S_{2}(n)=\sum_{k=1}^{n}k^{2}=\frac{n(n+1)(2n+1)}{6} \quad \forall n \in \mathbb{Z}^{+} \]

Dimostrazione
La formula è vera per \(n=1\), in quanto

\[ S_{2}(1)=1^{2}=\dfrac{1(1+1)(2+1)}{6} \]

Supponiamola vera un intero positivo \(n \ge 1\), e dimostriamo che è vera per \(n+1\). Cioè dobbiamo dimostrare che

\[ S_{2}(n+1)= \dfrac{(n+1)(n+2)(2n+3)}{6} \]

Sfruttando l’ipotesi induttiva, con semplici passaggi otteniamo

\[ \begin{array}{l} S_{2}(n+1)= 1^{2}+ 2^{2}+ \cdots + n^{2}+(n+1)^{2}=\dfrac{n(n+1)(2n+1)}{6}+ (n+1)^{2}= \\ \dfrac{n+1}{6}\biggl[n(2n+1)+6(n+1)\biggr]=\dfrac{n+1}{6}\left(2n^{2}+7n+6\right)= \\ \dfrac{(n+1)(n+2)(2n+3)}{6} \end{array} \]

Quindi abbiamo dimostrato che la formula è valida per ogni intero positivo \(n\).

Esercizio 2.2
Dimostrare con il metodo di induzione la seguente formula:

\[ S_{3}(n)=1^{3}+2^{3}+ \cdots + n^{3}= \left( \dfrac {n(n+1)}{2}\right)^{2} \]

Esercizio 2.3
Dimostrare con il metodo di induzione che

\[ 1 \cdot 2 + 2 \cdot 3 + \cdots + (n-1)\cdot n = \frac{(n-1)n(n+1)}{3} \]

Esercizio 2.4 – I coefficienti binomiali
Ricordiamo che il coefficiente binomiale \(\displaystyle\binom{n}{k}\) rappresenta il numero delle combinazioni di \(n\) oggetti di classe \(k\). In modo equivalente è il numero dei sottoinsiemi con \(k\) elementi che si possono estrarre da un insieme di \(n\) elementi. Per definizione si assumono i seguenti valori

\[ \binom{0}{0}= \binom{1}{0}=\binom{1}{1}=1 \]

Dalla definizione segue facilmente la seguente formula di Pascal:

\[ \binom{n+1}{k+1}=\binom{n}{k}+ \binom{n}{k+1} \]

Mediante la formula di Pascal e il metodo di induzione dimostrare la seguente formula:

\[ \binom{n}{k}= \frac{n!}{k!(n-k)!} \]

Dimostrazione
Indichiamo con \(P_{n}\) la proposizione che la formula è vera per un dato intero positivo \(n\), e per tutti i valori \(k=0,1,\cdots, n\). Sappiamo che \(P_{0}\) e \(P_{1}\) sono vere. Supposta vera \(P_{n}\), sfruttando la relazione precedente con semplici passaggi abbiamo

\[ \begin{array}{l} \displaystyle \binom{n+1}{k+1}=\binom{n}{k}+ \binom{n}{k+1}= \\ \displaystyle \dfrac{n!}{k!(n-k)!} + \dfrac{n!}{(k+1)!(n-k-1)!}=\dfrac{(n+1)!}{(k+1)!(n-k)!} \end{array} \]

Esercizio 2.5
Dimostrare le seguenti formule con il metodo di induzione:

\[ \begin{array}{l} \displaystyle \sum\limits_{k=0}^{n}\binom{n}{k}= 2^{n} \\ \displaystyle \sum\limits_{k \text{ pari}}{}\binom{n}{k}= 2^{n -1}\\ \displaystyle \sum\limits_{k \text{ dispari}}{}\binom{n}{k}= 2^{n -1}\\ \end{array} \]

Osservazione
Il principio di induzione è stato enunciato limitatamente agli insiemi di numeri naturali, cioè interi non negativi. Tuttavia può essere facilmente esteso ad insiemi di interi qualsiasi in questo modo: sia \(S\) un insieme di interi \(S\) con le seguenti proprietà:

• \(S\) contiene un numero intero \(n_{0}\)
• se \(S\) contiene un intero \(n \ge n_{0}\), allora contiene anche \(n+1\)

Allora \(S\) contiene tutti gli interi maggiori o uguali a \(n_{0}\).

2.2) Principio di induzione matematica forte

Il principio presentato sopra viene chiamato principio di induzione debole, per distinguerlo da una sua formulazione in apparenza più forte, ma in realtà equivalente, chiamato principio di induzione matematica completa o forte.

Principio di induzione completa (induzione forte)
Sia \(P(n)\) una proposizione relativa ai numeri naturali, cioè agli interi \(n \ge 0\). Consideriamo le seguenti due proposizioni:

• 1) \(P(n_{0})\) è vera per qualche \(n_{0} \in \mathbb{N}\);
• 2) se \(P(k)\) è vera per tutti i valori di \(k\) con \(n_{0}\le k \le n\) allora anche \(P(n+1)\) è vera.

Se entrambe le proposizioni \(1,2\) sono vere, allora la proprietà \(P(n)\) è vera per tutti i numeri naturali maggiori od uguali a \(n_{0}\).

Esercizio 2.6
Mediante il metodo di induzione completa dimostrare che ogni intero positivo \(n \gt 11\) può essere scritto nella forma

\[ n =4a + 5b \ , \quad a,b \in \mathbb{N} \]

Esercizio 2.7
Dimostrare che ogni intero positivo \(n\) può essere scritto come somma di potenze distinte con base \(2\).

Suggerimento
Il caso base \(n=1\) è ovvio, in quanto \(2^{0}=1\). Supponiamo ora che la proposizione sia vera per ogni \(k \le n\); consideriamo quindi l’intero \(n+1\) e sia \(t\) il più grande intero tale che \(2^{t} \le n+1\). Quindi concludere.

Esercizio 2.8
Dimostrare che le due formulazioni del principio di induzione sono in realtà equivalenti.

2.3) Principio del buon ordinamento

Sia \(A\) un sottoinsieme non vuoto di \(\mathbb{N}\). Un elemento \( x \in A\) si dice elemento minimo di \(A\) se per ogni elemento \(n \in A\) si ha \(x \le n\). Un insieme si dice bene ordinato rispetto ad una relazione di ordine, se ogni sottoinsieme non vuoto ha un elemento minimo.

Principio del buon ordinamento dei numeri naturali
L’insieme dei numeri naturali è bene ordinato. Cioè ogni sottoinsieme non vuoto di interi non negativi ha un elemento minimo.

Teorema 2.1
Il principio del buon ordinamento è equivalente al principio di induzione.

Dimostrazione
Dimostriamo soltanto che il principio induzione segue dal principio del buon ordinamento. Supponiamo quindi che valga il principio del buon ordinamento. Sia \(A\) un insieme che contiene un intero non negativo \(n_{0}\), e inoltre per ogni \(n \ge n_{0}\in A\) allora anche \(n+1 \in A\). Dobbiamo dimostrare che \(A\) contiene tutti i numeri naturali \(n \ge n_{0}\).
Sia \(x\) un intero tale che \(x \gt n_{0}\) e supponiamo per assurdo che \(x \not \in A\). Allora anche \(x-1\) non appartiene ad \(A\), altrimenti \(x-1+1\) dovrebbe appartenere all’insieme. Inoltre \(x \neq n_{0}\) in quanto \(n_{0} \in A\), ma allora abbiamo \(x -1 \gt n_{0}\). Poiché \(x-1\) ha le stesse proprietà di \(x\) possiamo ripetere all’infinito il ragionamento senza arrivare ad un elemento minimo.

Esercizio 2.9
Utilizzare il principio del buon ordinamento per dimostrare che se \(a\) è un intero e \(b\) è un intero positivo, allora esistono due unici interi \(q,r\) tali che

\[ a = bq + r \quad 0 \le r \lt b \]

Suggerimento
Considerare l’insieme degli interi non negativi \(r\) della forma \(r=a-bq\) con \(q \in \mathbb{Z}\). Dimostrare che è un insieme non vuoto e quindi ha un elemento minimo.

Esercizio 2.10
Dimostrare nuovamente la formula \(S_{1}(n)=\sum\limits_{k=1}^{n}k=\dfrac{n(n+1)}{2}\) mediante il principio di buon ordinamento.

Suggerimento
Supporre che la formula non valga per ogni numero naturale, cioè esista un intero positivo \(n_{0}\) tale che \(S_{1}(n_{0}) \neq \dfrac{n_{0}(n_{0}+1)}{2}\). Quindi arrivare ad una contraddizione.

3) Risoluzione di problemi mediante il metodo di induzione matematica

La natura della matematica è un argomento che ha interessato i filosofi e i matematici fin dall’antichità. Sono state elaborate due concezioni fondamentali, rappresentate dai due filosofi più importanti dell’antichità, Platone e Aristotele:

• analitica: matematica come attività di risoluzione dei problemi;
• assiomatica: matematica come dimostrazione dei teoremi, a partire da un insieme finito di assiomi e definizioni iniziali.

Un problema è un compito per il quale non si conosce già un metodo di soluzione. Si tratta quindi di un concetto relativo, che dipende anche dalle conoscenze che ha l’individuo al quale viene posto il problema.
In questo paragrafo vedremo come utilizzare il principio di induzione per la soluzione di problemi ed esercizi matematici di varia natura. Nel paragrafo successivo descriveremo alcuni esempi di dimostrazione di teoremi tramite il principio di induzione.
Per una guida generale alla soluzione dei problemi e alla dimostrazione dei teoremi vedere i due importanti testi di Polya (^[1] e ^[4]).

3.1) Problemi di algebra e calcolo combinatorio

Esercizio 3.1
Dimostrare che \(x-y\) divide \(x^{n}-y^{n}\) per ogni intero positivo \(n\).

Suggerimento
Per il passo induttivo utilizzare la formula

\[ x^{n+1}- y^{n+1}=x^{n+1}- x^{n}y+ x^{n}y- y^{n+1} \]

Esercizio 3.2
Dimostrare che per ogni intero positivo \(n\) vale la formula

\[ x^{n}- y^{n}=(x-y)(x^{n-1} + x^{n-2}y + x^{n-3}y^{2} + \cdots + xy^{n-2} + y^{n-1}) \]

Esercizio 3.3
Se \(n\) è un intero non negativo allora \(5|(n^{5}-n)\).

Esercizio 3.4
Se \(n\) è un intero non negativo allora

\[ 1 \cdot 3 + 2 \cdot 4 + 3 \cdot 5 + \cdots + n(n+2) = \frac{n(n+1)(2n+7)}{6} \]

Esercizio 3.5
Se \(n\) è un intero positivo allora

\[ S_{n}= 1+3 + 5 + \cdots + (2n-1) = n^{2} \]

Esercizio 3.6
Mediante l’induzione matematica dimostrare che per \(n \ge 1\) si ha

\[ (-1)\cdot 1 + (-1)^{2}\cdot 2 + (-1)^{3}\cdot 3 + \cdots + (-1)^{n}\cdot n = \frac{(-1)^{n}(2n+1)-1}{4} \]

Esercizio 3.7
Mediante l’induzione matematica dimostrare che

\[ 2^{n} \ge n+1 \ , \quad n \in \mathbb{N} \]

Esercizio 3.8 – Progressione geometrica
Siano \(a,x\) due numeri reali con \(x \neq 1\). Dimostrare la formula

\[ a +ax+ ax^{2}+ \cdots + ax^{n-1}=\frac{a(x^{n}-1)}{x-1} \]

Esercizio 3.9
Dimostrare che la somma dei cubi di tre numeri naturali positivi consecutivi è divisibile per \(9\).

Suggerimento
Dobbiamo dimostrare che

\[ n^{3}+ (n+1)^{3}+(n+2)^{3}=9k \ , \quad k \in \mathbb{N} \]

Per il passo induttivo utilizzare al formula

\[ (n+1)^{3}+ (n+2)^{3}+(n+3)^{3}= (n^{3}+ (n+1)^{3}+(n+2)^{3}) + 9(n^{2}+3n+3) \]

Esercizio 3.10
Utilizzare il metodo di induzione per dimostrare le seguenti formule:

\[ \begin{array}{l} \sum\limits_{k=1}^{n}\dfrac{1}{k(k+1)} = \dfrac{1}{1 \cdot 2}+ \dfrac{1}{2\cdot 3}+ \cdots + \dfrac{1}{n(n+1)}= \dfrac{n}{n+1} \\ \\ \sum\limits_{k=1}^{n}\dfrac{1}{(2k-1)(2k+1)} = \dfrac{1}{1 \cdot 3}+ \dfrac{1}{3 \cdot 5}+ \cdots + \dfrac{1}{(2n-1)(2n+1)}= \dfrac{n}{2n+1} \\ \end{array} \]

Le stesse formule possono esser dimostrate più semplicemente osservando che

\[ \begin{array}{l} \dfrac{1}{k(k+1)}=\dfrac{1}{k}- \dfrac{1}{k+1} \\ \dfrac{2}{(2k-1)(2k+1)}=\dfrac{1}{2k-1}- \dfrac{1}{2k+1} \end{array} \]

Esercizio 3.11 – I numeri di Fibonacci
I numeri di Fibonacci \(F_{n}\) sono così definiti:

\[ \begin{array}{l} F_{0}=0 \ , \quad F_{1}=1 \\ F_{n}=F_{n-1}+ F_{n-2} \ , \quad n \ge 2 \end{array} \]

Dimostrare con il metodo di induzione che

\[ \begin{array}{l} F_{n}=\dfrac{1}{\sqrt{5}}\left(\dfrac{1+\sqrt{5}}{2}\right)^{n} – \dfrac{1}{\sqrt{5}}\left(\dfrac{1-\sqrt{5}}{2}\right)^{n} \end{array} \]

Il numero \(\varphi =\dfrac{1+\sqrt{5}}{2} \approx 1,618033\) è chiamato rapporto aureo.

Esercizio 3.12 – I numeri di Lucas
I numeri di Lucas \(L_{n}\) sono così definiti:

\[ \begin{array}{l} L_{0}=2 \ , \quad L_{1}=1 \\ L_{n}=L_{n-1}+ L_{n-2} \ , \quad n \ge 2 \end{array} \]

Dimostrare con il metodo di induzione che

\[ \begin{array}{l} L_{n}=\left(\dfrac{1+\sqrt{5}}{2}\right)^{n} + \left(\dfrac{1-\sqrt{5}}{2}\right)^{n} \end{array} \]

Esercizio 3.13 – Identità di Cassini

\[ \begin{array}{l} F_{n}^{2}-F_{n-1} F_{n+1} = (-1)^{n+1} \ , \quad n \ge 1 \\ L_{n}^{2} -L_{n+1} L_{n-1} = 5(-1)^{n} \ , \quad n \ge 0 \\ \end{array} \]

Esercizio 3.14
Dimostrare il teorema binomiale di Newton:

\[ (a+b)^{n}= \sum\limits_{k=0}^{n}\binom{n}{k}a^{n-k}b^{k}= \\ a^{n}+na^{n-1}b + \frac{n(n-1)}{2!}a^{n-2}b^{2}+ \cdots + nab^{n-1}+ b^{n} \]

Esercizio 3.15
Dimostrare con il metodo di induzione matematica la seguente formula:

\[ \sum\limits_{k=0}^{r}\binom{n}{k}\binom{m}{r-k} = \binom{n+m}{r} \]

La formula precedente può essere dimostrata senza fare nessun calcolo, semplicemente ricordando il significato combinatorio del coefficiente binomiale. Dati due insiemi, uno con \(n\) oggetti e un altro con \(m\) oggetti, il numero delle combinazioni di \(n+m\) oggetti presi a gruppi di \(r\) si ottiene contando tutti i possibili modi di prendere \(k\) oggetti dal primo insieme e \((r-k)\) oggetti dal secondo, con \(k=0,1,\cdots,r\).

Esercizio 3.16
Mediante l’induzione matematica dimostrare che

\[ 3 | n^{3}+ 2n \ , \quad n \in \mathbb{N} \]

Esercizio 3.17
Sia data la seguente matrice:

\[ A =\begin{pmatrix} 3 & 1 \\ 0 & 2\\ \end{pmatrix} \]

Dimostrare che per \(n \ge 1\) si ha

\[ A^{n} =\begin{pmatrix} 3^{n} & 3^{n}-2^{n} \\ 0 & 2^{n}\\ \end{pmatrix} \]

Esercizio 3.18

\[ 1+ \dfrac{1}{2^{3}}+ \dfrac{1}{3^{3}}+ \cdots + \dfrac{1}{n^{3}} \lt \dfrac{3}{2} \]

Esercizio 3.19
Utilizzare il metodo di induzione per dimostrare la seguente formula:

\[ \begin{array}{l} \sum\limits_{k=1}^{n}(2k-1)^{2}=1^{2}+ 3^{2}+ \cdots + (2n-1)^{2}=\dfrac{n(2n-1)(2n+1)}{3} \\ \end{array} \]

Esercizio 3.20
Utilizzare il metodo di induzione per dimostrare la seguente formula:

\[ \begin{array}{l} \prod\limits_{k=1}^{n}(2k-1)=\dfrac{(2n)!}{2^{n}n!} \end{array} \]

3.2) Problemi di geometria e trigonometria

Esercizio 3.21

\[ \sum\limits_{k=1}^{n}\cos(2k-1)x = \frac{\sin 2nx}{2\sin x} \]

Suggerimento
Conviene utilizzare la forma complessa del coseno: \(\cos x=\dfrac{e^{ix}+ e^{-ix}}{2}\). Calcolare la somma geometrica

\[ \sum_{k=1}^{n}e^{(2k-1)ix}= e^{ix}+ e^{3ix}+ \cdots + e^{(2n-1)ix} \]

e quindi separare la parte reale dalla parte immaginaria.

Esercizio 3.22
Dinostrare che \(n\) linee rette nel piano che passano per uno stesso punto dividono il piano in \(2n\) parti.

Suggerimento
Nel passo induttivo osservare che l’aggiunta di una nuova retta che passa nel punto in comune aggiunge due nuove parti di piano a quelle già presenti.

Esercizio 3.23
Siano dati \(n\) piani che passano in un punto comune e non ci siano tre piani che passano attraverso una stessa retta. Dimostrare che dividono lo spazio in \(x_{n}=n(n-1) +2 \) parti.

Suggerimento
Nel passo induttivo osservare che il nuovo piano aggiunto ad \(n\) piani già esistenti interseca ciascuno degli \(n\) piani lungo una data retta. Quindi utilizzare l’esercizio precedente, secondo il quale \(n\) differenti rette dividono il piano in \(2n\) parti.

Esercizio 3.24
Sia dato un triangolo rettangolo \(\bigtriangleup{ABC}\), con l’angolo \(\angle ABC =90^{\circ}\) e lunghezze dei lati \(BC=a, AC=b, AB=c\). Dimostrare che

\[ a^{n} \ge b^{n}+ c^{n} \ , \quad n=2,3,4,\cdots \]

Suggerimento
Per dimostrare che \(a^{n+1} \ge b^{n+1}+ c^{n+1}\) dimostrare che

\[ a(b^{n}+c^{n}) \ge b^{n+1}+ c^{n+1} \]

Esercizio 3.25
Determinare in quanti parti un piano è suddiviso da \(n\) rette, tali che ogni coppia di rette si interseca in un punto e non ci sono tre rette che hanno un punto in comune.

Soluzione
Indichiamo con \(g(n)\) il numero di parti da calcolare. Osserviamo che \(n\) punti di una retta dividono la retta in \(n+1\) parti. Se aggiungiamo una retta ad \(n\), allora per ipotesi la nuova retta interseca le altre rette in \(n\) punti diversi. Questi \(n\) punti dividono la retta in \(n+1\) parti. Quindi la nuova retta taglia \(n+1\) delle parti già esistenti e aggiunge quindi \(n+1\) parti a quelle preesistenti, cioè \(g(n+1)=g(n)+ n+1\).
Ora abbiamo \(g(1)=2, g(2)=g(1)+2=4, \cdots\). Quindi si ricava facilmente la formula

\[ g(n)= 2 + (2 + 3 + 4 + \cdots + n) = 1+ \frac{n(n+1)}{2}= \frac{n^{2}+n+2}{2} \]

3.3) Problemi di analisi matematica

Esercizio 3.26 – Disuguaglianza di Bernoulli
Dimostrare mediante il metodo di induzione la seguente disuguaglianza:

\[ (1+x)^{n} \ge 1+nx \ , \quad x \ge -1 \ , \quad n=0,1,2,\cdots \]

Esercizio 3.27
Dimostrare che

\[ \frac{1}{2}\frac{3}{4}\cdots \frac{2n-1}{2n}\le \frac{1}{\sqrt{3n+1}} \]

Esercizio 3.28
Dimostrare che \(n! \leq n^{n}\) con \(n=0,1,2,\cdots\).

Suggerimento
Notare che se \(n! \le n^{n}\) allora

\[ (n+1)!=(n+1)n!\le (n+1)n^n \lt (n+1)(n+1)^{n}=(n+1)^{n+1} \]

Esercizio 3.29
Dimostrare che per \(n \ge 1\) si ha

\[ \frac{d^{n}}{dx^{n}}\left(e^{x^{2}}\right)=P_{n}(x)e^{x^{2}} \]

dove \(P_{n}(x)\) è un polinomio di grado \(n\).

Esercizio 3.30 – Funzione Gamma
Dimostrare la seguente formula:

\[ \Gamma(n+1)= \int\limits_{0}^{\infty}x^{n}e^{-x}dx=n! \ , \quad n \ge 0 \]

Suggerimento
Per il passo induttivo utilizzare l’integrazione per parti.

Esercizio 3.31

\[ I_{n}= \int\limits_{0}^{\pi}\sin^{2n}x \,dx =\frac{\pi}{2^{2n}}\frac{(2n)!}{(n!)^{2}} \ , \quad n \in \mathbb{N} \]

Suggerimento
Mediante l’integrazione per parti dimostrare la formula

\[ I_{n+1}=\frac{2n+1}{2n+2}I_{n} \]

Quindi utilizzare questa formula nel passo induttivo.

Esercizio 3.32
Dimostrare la seguente disuguaglianza

\[ e^{x} \gt 1 + x + \frac{x^{2}}{2!}+ \cdots + \frac{x^{n}}{n!} \ , \quad x \gt 0 \ , \quad n \ge 0 \]

Suggerimento
Sfruttare questa proprietà degli integrali: se \(f(x),g(x)\) sono due funzioni continue in un intervallo chiuso \([a,b]\), e se \(f(x) \lt g(x)\) per ogni \(x \in [a,b]\), allora

\[ \int\limits_{a}^{b}f(x) \lt \int\limits_{a}^{b}g(x) \]

Risolvere lo stesso esercizio studiando la derivata prima della differenza delle due funzioni.

Esercizio 3.33
Sia \(x_{1}=\sqrt{2}\) e \(x_{n+1}=\sqrt{x_{n}+ 2}\).
Dimostrare che

\[ x_{n}=2 \cos \frac{\pi}{2^{n+1}} \]

4) Dimostrazione di teoremi mediante il metodo di induzione matematica

La matematica è un edificio molto complesso costituito da varie branche principali: algebra, geometria, analisi, probabilità, ecc. Questo edificio è stato costruito a partire da un piccolo numero di assiomi e postulati. Tutti i teoremi della matematica vengono dimostrati a partire da questi concetti elementari, utilizzando gli strumenti della logica. Un teorema è una proposizione logica che può assumere i valori di vero e falso. Si assume valida la legge del terzo escluso, già enunciata da Aristotele (tertium non datur). Ad esempio tutti i teoremi della geometria euclidea sono dimostrati a partire dai postulati e dagli assiomi di Euclide.
La differenza fra soluzione di problemi e dimostrazione di teoremi non è così netta, ma c’è una sovrapposizione. Secondo alcuni autori addirittura la dimostrazione di un teorema è equivalente alla soluzione di un problema.
Una regola fondamentale nelle dimostrazioni è la regola modus ponens per due proposizioni \(P,Q\), che in forma simbolica può essere così formulata:

\[ P \land (P \implies Q) \implies Q \]

Cioè se la proposizione \(P\) è vera, e se la proposizione \(P\) implica la proposizione \(Q\), in simboli \(P \implies Q\), allora anche la proposizione \(Q\) è vera.

Esempio 4.1
Consideriamo le due proposizioni, relative ad un triangolo \(\Delta ABC\):

\[ \begin{array}{l} P : \text{il triangolo è equilatero} \\ Q : \text{il triangolo ha gli angoli uguali} \end{array} \]

Dalla geometria euclidea sappiamo che \(P \implies Q\), quindi se \(P\) è vera, allora anche \(Q\) è vera.

Tra i principali metodi di dimostrazione ricordiamo i seguenti:

• dimostrazione diretta
• dimostrazione per assurdo
• dimostrazione per contrapposizione
• mediante il metodo di induzione matematica

Per una illustrazione dei vari metodi di dimostrazione vedere ad esempio il testo ^[3].
Di seguito vediamo alcuni esempi di dimostrazione di teoremi con il metodo di induzione matematica.

Esercizio 4.1
Ricordiamo che, se \(n \ge 2\) è un numero composto, allora esistono due numeri naturali \(a,b\) tali che \(n=ab\) e \( 1 \lt a,b\lt n\).
Dimostrare tramite l’induzione completa che ogni numero naturale \(n \ge 2\) è divisibile da almeno un numero primo.

Suggerimento
Il caso base \(n=2\) è un numero primo e quindi la proposizione è vera. Supporre vera la proposizione per tutti i numeri naturali \(2 \le k \le n\). Distinguere i due casi con \(n+1\) primo e \(n+1\) composto.

Esercizio 4.2 – Teorema fondamentale aritmetica
Dimostrare che ogni intero \(n \gt 1\) può essere espresso come prodotto di numeri primi:

\[ n = p_{1}p_{2}\cdots p_{t} \]

dove i numeri primi \(p_{k}\) con \(k=1,2,\cdots,t\) non sono necessariamente distinti.

Suggerimento
Utilizzare il metodo di induzione forte. Per dimostrare il passo induttivo, distinguere il caso in cui l’intero \(n+1\) è primo oppure composto.

Esercizio 4.3 – Il piccolo teorema di Fermat
Sia \(p\) un numero primo ed \(n\) un intero positivo. Allora

\[ p | n^{p}-n \]

In altre parole esiste un intero positivo \(k\) tale che \(n^{p}-n=pk\).

Suggerimento
Utilizzare la formula binomiale \(\displaystyle (n+1)^{p}=\sum\limits_{k=0}^{p}\binom{p}{k}n^{k}\) e ricordare la seguente proprietà dei coefficienti binomiali:

\[ p | \binom{p}{k} \ , \quad 1 \le k \le p-1 \]

Esercizio 4.4 – Principio dei cassetti di Dirichlet
Sia \(n \ge 1\) un numero naturale. Sia \(S\) un insieme che contiene più di \(n\) elementi e siano \(S_{1},S_{2},\cdots,S_{n}\) dei sottoinsiemi di \(S\) tali che \(S= S_{1}\cup S_{2}\cup \cdots \cup S_{n}\). Allora esiste almeno un sottoinsieme \(S_{k}\), con \(k=1,2,\cdots, n\), che contiene due o più elementi di \(S\).

Suggerimento
Il caso base è ovvio. Per il passo induttivo distinguere il caso in cui l’insieme \(S_{n+1}\) contiene almeno \(2\) elementi, da quello in cui contiene un solo elemento oppure nessun elemento.

5) Il metodo della discesa infinita di Fermat

Il metodo della discesa infinita è stato sviluppato da Fermat (1601-1665). In particolare Fermat ha utilizzato questo metodo per dimostrare che l’equazione

\[ x^{4}+y^{4}=z^{2} \]

non ha soluzioni intere, ad eccezione di quelle banali, come ad esempio \((x,y,z)=(1,0,1)\).
Il metodo si basa sostanzialmente sul principio del buon ordinamento dei numeri naturali, che come abbiamo visto è equivalente al principio di induzione matematica.
L’idea base del metodo è che non può esistere una successione infinita \(\{x_{n}\}\) di numeri naturali decrescenti. Data una soluzione di un’equazione in interi positivi, il metodo consiste nel trovare una soluzione più piccola, e quindi arrivare ad una contraddizione.
I passi per utilizzare il metodo di Fermat per dimostrare che una proposizione \(P(n)\) sui numeri naturali è falsa sono i seguenti:

• si suppone che \(P(n)\) sia vera per un certo numero naturale \(n\);
• quindi si dimostra che è vera anche per un numero naturale \(m \lt n\);
• il processo può essere ripetuto all’infinito, creando una successione decrescente di numeri naturali;
• da questo si arriva ad una contraddizione, e quindi si deduce che \(P(n)\) è falsa.

Esempio 5.1
Utilizzare il metodo della discesa infinita per dimostrare che \(\sqrt{2}\) è un numero irrazionale.

Soluzione
Supponiamo che la radice di \(2\) sia un numero razionale, cioè \(\sqrt{2}=\dfrac{x}{y}\), con \(x,y\) interi. Definiamo il massimo comune denominatore \(d=(x,y)\) come misura della soluzione trovata. Abbiamo

\[ 2y^{2}=x^{2} \]

Quindi \(x\) è pari, cioè \(x=2x_{1}\) e quindi anche \(y=2y_{1}\). Abbiamo trovato una nuova soluzione \(\sqrt{2}=\dfrac{x_{1}}{y_{1}}\). Il massimo comune divisore \(d_{1}=(x_{1},y_{1})\) della nuova coppia è minore di quello della precedente, esattamente la metà. Possiamo applicare lo stesso procedimento alla coppia \(x_{1},y_{1}\) ottenendo un’altra coppia \(x_{2},y_{2}\), che ha un massimo comune denominatore minore. Questo processo può essere ripetuto all’infinito, ottenendo una contraddizione.

L’esercizio seguente è una generalizzazione del teorema precedente. Riportiamo la dimostrazione di Dedekind.

Esercizio 5.1
Sia \(d\) un intero positivo, non quadrato perfetto. Dimostrare che \(\sqrt{d}\) è un numero irrazionale.

Suggerimento
Supponiamo che \(\sqrt{d}\) sia un numero razionale. Poiché \(d\) non è un quadrato perfetto, esiste un intero positivo \(k\) tale che

\[ k \lt \sqrt{d} \lt k+1 \]

Possiamo porre

\[ \sqrt{d} = k + \frac{m}{n} \]

dove \(0 \lt m \lt n\). Eliminiamo ora la radice e il denominatore ottenendo

\[ dn^{2}=k^{2}n^{2}+ 2kmn +m^{2} \]

Poniamo \(nq=dn^{2}-k^{2}n^{2}- 2kmn=m^{2}\). Risulta \(\dfrac{q}{m}=\dfrac{m}{n}\), quindi

\[ \sqrt{d} = k + \frac{m}{n}= k + \frac{q}{m} \]

Poiché \(0 \lt q \lt m\), abbiamo un’altra rappresentazione di \(\sqrt{d}\), con una frazione con un denominatore più piccolo. Ripetendo il processo all’infinito abbiamo una contraddizione.

Esercizio 5.2 – Il numero aureo
Il numero aureo è definito come la soluzione positiva della seguente equazione:

\[ x^{2}-x -1 = 0 \]

La soluzione positiva è

\[ \varphi = \frac{1+ \sqrt{5}}{2} \]

Il numero aureo è chiaramente irrazionale, in quanto \(\sqrt{5}\) è irrazionale.
Dimostriamo ora che il numero aureo è irrazionale mediante il metodo della discesa infinita. Supponiamo per assurdo che sia razionale, cioè \(\varphi = \dfrac{a}{b}\) con \(a,b\) interi positivi. Allora

\[ a^{2} = b^{2} + ab \]

Chiaramente entrambi gli interi \(a,b\) devono essere pari. Possiamo quindi porre

\[ \begin{array}{l} a = 2a_{1} \\ b = 2b_{1} \end{array} \]

Sostituendo nell’equazione, abbiamo

\[ a_{1}^{2} = b_{1}^{2} + a_{1}b_{1} \]

Si tratta della stessa equazione iniziale e quindi abbiamo una contraddizione. L’ipotesi che \(\varphi\) sia razionale è quindi falsa.

Esercizio 5.3
Dimostrare che non può esistere una progressione aritmetica infinita \((x_{n})\) i cui termini siano tutti quadrati perfetti.

Suggerimento
Osservare che per una progressione aritmetica deve essere

\[ x_{n+1}^{2}- x_{n}^{2}= x_{n}^{2}- x_{n-1}^{2} \ , \quad n \ge 2 \]

Inoltre ovviamente abbiamo

\[ x_{n+1} + x_{n} \gt x_{n} + x_{n-1} \ , \quad n \ge 2 \]

Mettendo insieme le due relazione precedenti otteniamo una successione decrescente di interi positivi

\[ x_{2} – x_{1} \gt x_{3} – x_{2} \gt x_{4} – x_{3} \cdots \ , \quad n \ge 2 \]

e quindi una contraddizione.
Per un approfondimento del metodo di induzione matematica vedere ad esempio il testo ^[2].

6) Esercizi proposti da svolgere

Esercizio 6.1
Dimostrare con il metodo di induzione che per tutti i numeri dispari \(n \ge 3\) si ha

\[ 8| n^{2}-1 \]

Dimostrare la stessa proposizione senza utilizzare il metodo di induzione. Supporre \(n=2k+1\) e quindi continuare.

Esercizio 6.2
Data la successione \(x_{n}=n(3n+1)\), dimostrare che

\[ \sum\limits_{k=0}^{n}x_{n}=n(n+1)^{2} \]

Esercizio 6.3

\[ \sum\limits_{K=2}^{n}\dfrac{1}{k^{2}-1}= \dfrac{(n-1)(3n+2)}{4n(n+1)} \]

Esercizio 6.4 – Formula di Taylor
Sia \(f: \mathbb{R} \to \mathbb{R}\) una funzione continua e differenziabile fino all’ordine \(n+1\). Allora per ogni \(x \in \mathbb{R}\) abbiamo

\[ f(x)= f(0) + \frac{f'(0)x}{1!}+ \frac{f^{(2)}(0)x^{2}}{2!}+\cdots + \frac{f^{(n)}(0)x^{n}}{n!} + R_{n}(x) \\ R_{n}(x)= \frac{1}{n!}\int\limits_{0}^{x}f^{(n+1)}(t)(x-t)^{n}dt \]

Suggerimento
Dimostrare con il metodo di induzione, utilizzando l’integrazione per parti.

Esercizio 6.5
Se \(n\) è un intero non negativo allora

\[ \sum\limits_{k=0}^{n}k \cdot k!=(n+1)! – 1 \]

Esercizio 6.6

\[ \int_{0}^{\pi/2}\cos^{2n+1}x \,dx=\frac{2^{2n}(n!)^{2}}{(2n+1)!} \ , \quad n=0,1,2,\cdots \]

Esercizio 6.7

\[ \sum\limits_{k=0}^{n}\binom{n}{k}^{2}= \binom{2n}{n} \]

Esercizio 6.8

\[ S_{n}= 1-2^{2}+3^{2}-4^{2}+ \cdots + (-1)^{n-1}n^{2}=(-1)^{n-1}\frac{n(n+1)}{2} \]

Esercizio 6.9

\[ \cos \alpha \cos 2\alpha \cos 4\alpha \cdots \cos 2^{n}\alpha = \frac{\sin 2^{n+1}\alpha}{2^{n+1}\sin\alpha} \]

Esercizio 6.10

\[ \cos \frac{\pi}{2^{n+1}}= \frac{\sqrt{2+ \sqrt{2+ \cdots + \sqrt{2}}}}{2} \ , \quad \text{n radici quadrate} \]

Suggerimento
Per il passo induttivo utilizzare la formula di bisezione del coseno:

\[ \cos \frac{\alpha}{2}=\pm \sqrt{\frac{1+ \cos \alpha}{2}} \]

Esercizio 6.11

\[ \frac{1}{n+1}+ \frac{1}{n+2}+ \cdots + \frac{1}{2n} = 1 – \frac{1}{2}+ \frac{1}{3}- \cdots + \frac{1}{2n-1}- \frac{1}{2n} \]

Esercizio 6.12

\[ \frac{1}{1 \cdot 2 \cdot 3}+ \frac{1}{2 \cdot 3 \cdot 4}+ \cdots + \frac{1}{n(n+1)(n+2)} = \frac{n(n+3)}{4(n+1)(n+2)} \]

Esercizio 6.13

\[ \frac{1^{2}}{1 \cdot 3}+ \frac{2^{2}}{3 \cdot 5}+ \cdots + \frac{n^{2}}{(2n-1)(2n+1)} = \frac{n(n+1)}{2(2n+1)} \]

Esercizio 6.14
Determinare per quali numeri naturali è verificata la seguente disuguaglianza:

\[ 2^{n} \gt n^{2} \]

Soluzione: \([n=0;n=1; n \gt 4]\)

Esercizio 6.15
Determinare che per ogni intero positivo \(a\) si ha

\[ \frac{1}{a(a+1)}+ \frac{1}{(a+1)(a+2)}+ \cdots + \frac{1}{(a+n-1)(a+n)}= \frac{n}{a(a+n)} \]

Esercizio 6.16 – Polinomi di Hermite
I polinomi di Hermite (1822-1901) \(H_{n}(x)\) sono definiti mediante la seguente formula ricorsiva:

\[ \begin{array}{l} H_{0}(x)=1 \\ H_{1}(x) = 2x \\ H_{n+1}(x)= 2x H_{n}(x) – 2nH_{n-1}(x) \ , \quad n \ge 1 \\ \end{array} \]

Dimostrare mediante il metodo di induzione che

\[ \begin{array}{l} \dfrac{d H_{n}(x)}{dx} = 2nH_{n-1}(x) \\ H_{2n}(0)= (-1)^{n}\dfrac{(2n)!}{n!} \\ H_{2n+1}(0) = 0 \end{array} \]

Esercizio 6.17
Siano \(A,B,M\) matrici invertibili \(n \times n\), cioè matrici che ammettono la matrice inversa. Ad esempio esiste una matrice \(A^{-1}\), inversa della matrice \(A\), tale che \(AA^{-1}=A^{-1}A=I\), dove \(I\) è la matrice identità, che ha gli elementi nella diagonale principale uguali ad \(1\) e tutti gli altri uguali \(0\).
Dimostrare che se \(B=MAM^{-1}\) allora

\[ B^{k}=MA^{k}M^{-1} \ , \quad k \ge 0 \]

Conclusione

Il metodo di induzione matematica è uno strumento molto utile per dimostrare teoremi e risolvere problemi. Naturalmente per poterlo utilizzare bisogna fare delle congetture sulla formula che si vuole dimostrare. Se applicabile, il metodo da una garanzia della validità di una proposizione.
Tuttavia non sempre è possibile utilizzare questo metodo. Inoltre, anche nel caso sia applicabile, il metodo spesso non garantisce una comprensione completa del significato del teorema che è stato dimostrato. Per questo è utile dimostrare uno stesso teorema in una pluralità di modi, utilizzando anche altri metodi come il metodo diretto, il metodo di contrapposizione o la dimostrazione per assurdo.

---

Bibliografia

^[1]G. Polya – How to Solve It: A New Aspect of Mathematical Method (Princeton U.P.)

^[2]D. Gunderson – Handbook of Mathematical Induction: Theory and Applications (Chapman and Hall/CRC)

^[3]Daniel J. Velleman – How to Prove It: A Structured Approach (Cambridge U.P.)

^[4]G. Polya – Mathematics and Plausible Reasoning, Volume 1/2: Induction and Analogy in Mathematics (Princeton U.P.)