- $1\in S$
- $n+1\in S\, \, ogni\, \, volta\, \, che\, \, n\in S$
allora S = N.
Tale principio si usa sovente per dimostrare alcuni teoremi, essendo un potente ed insostituibile metodo di dimostrazione. Precisamente se si vuol dimostrare una assegnata proprietà P(n), data per ogni n naturale (o positivo), si procede nel seguente modo:
- prima di tutto si prova che la P(n) è vera per n = 1, ossia si prova che P(1) è vera (base di induzione);
- poi si assume per vera P(n) e si dimostra che P(n+1) è vera;
Se si riesce in questi due passi (dimostrazioni) allora si può concludere che P(n) è vera per ogni n naturale (positivo). Quando si dimostra un teorema con tale principio si diche che si ragiona per ricorrenza.
Definizione pe induzione.- Mediante il principio di induzione matematica si possono definire svariati concetti matematici. (vedi successioni definite per ricorrenza)
Esempio 1.1.- Dimostrare con il principio di induzione che per $n\in N$ risulta \[1+3+5+7+…+(2n-1)=n^{2}\]
Dimostrazione
Dimostriamo che l’uguaglianza è vera per n = 1:
- Se n = 1 il primo membro si riduce a 1, infatti 2n – 1 diventa 1 sostituendo n =1; il secondo membro per n = 1 è $1^{2} = 1$. Pertanto per n =1 il primo membro e il secondo membro dell’uguaglianza sono uguali entrambi ad 1, ovvero l’uguaglianza è vera per n =1.
- Supponiamo ora che l’uguaglianza sia vera per n e dimostriamo che è vera per n + 1. Sviluppiamo fino ad n + 1 al primo membro e al secondo membro dell’uguaglianza suddetta. Si ha:
\[1+3+5+7+…+(2(n+1)-1)=(n+1)^{2}\]
ossia
\[1+3+5+7+…+(2n+1)=(n+1)^{2}\]
ossia
\[1+3+5+7+…+2n+(2n+1)=(n+1)^{2}\]
da cui
\[n^{2}+(2n+1)=(n+1)^{2}\]
e cioè
\[n^{2}+2n+1=(n+1)^{2}\]
Pertanto l’uguaglianza suddetta è vera per ogni n di N.
Esempio 1.2.- Dimostrare con il principio di induzione che per $n\in N$ risulta \[2+4+6+…+2n=n(n+1)\]
Esempio 1.3.- Dimostrare con il principio di induzione che per $n\in N$ risulta \[1^{2}+2^{2}+3^{2}+…+n^{2}=\frac{1}{6}n\left ( n+1 \right )\left ( 2n+1 \right )\]
Esempio 1.4.- Dimostrare con il principio di induzione che per $n\in N$ risulta \[5+10+15+…+5n=\frac{5}{2}n\left ( n+1 \right )\]
Esempio 1.5.- Dimostrare con il principio di induzione che per $n\in N$ \[1+2+3+4+5+…+n=\frac{n\left ( n+1 \right )}{2}\]
Esempio 2.1.- Dimostrare con il principio di induzione che un insieme finito S di n elementi ha $2^{n}$ sottoinsiemi.
Esempio 2.2.- Dimostrare che le applicazioni di S in T, ove S ha cardinalità n e T ha cardinalità m sono $m^{n}$.