Principio di induzione

uni 28/08/2023
Il principio di induzione (o procedimento induttivo), è una tecnica di dimostrazione che dimostra la validità di una tesi dalla verifica di due condizioni:

• la validità del passo zero
• la validità del passo induttivo
  Viene usato quando la tesi viene formulata in funzione dei numeri naturali $N$ N i numeri naturali.

Come

Se valgono le seguenti condizioni:

• passo zero: $P(n)$ vera per $n=0$, ovvero $P(0)$ vera
• passo induttivo: se $P(n)$ è vera per $n=0$ allora anche $P(n+1)$ è vera.
  Allora $P(n)$ è vera $\forall n\in N$

Esempi

Il principio di induzione si usa per dimostrare:
Disuguaglianza Bernoulli
Fattoriale
Binomio di Newton