I naturali, i numeri triangolari e la formula di Gauss Flashcards
Da quali clausole è costituita la definizione induttiva di un insieme?
La clausola base.
La clausola induttiva.
La clausola terminale.
Dare una definizione induttiva dell’insieme dei naturali.
- 0 appartiene a N.
- Se n appartiene a N, n + 1 appartiene a N.
- Nessun altro numero appartiene a N.
Definizione induttiva di numeri triangolari.
Per ogni naturale, il numero triangolare Tn è uguale alla somma dei numeri minori o uguali a n.
Definizione ricorsiva di numeri triangolari.
T0 = 0; Tn+1 = Tn + n+1
Principio di induzione sui naturali
Presupposto: (CASO BASE) P(0) è vera, (PASSO INDUTTIVO), vale che se P(n) è vera, allora P(n+1) è vera, per ogni naturale.
Conseguenza:
P(m) è vera per ogni naturale.
Formula di Gauss
Tn = n (n+1) / 2
Dimostra la formula di gauss
1) T(0) = 0.
2) assumiamo che T(n) = n(n+1)/2. Dimostriamo che T(n+1) = (n+1)(n+2) / 2.
Per definizione, T(n+1) = T(n) + n + 1 = n(n+1)/2 + n + 1 = (n+1)(n+2)/2.
Definizione induttiva dei numeri pari
L’insieme Np dei numeri pari è l’insieme più piccolo che soddisfa due proprietà:
1) 0 appartiene ai pari.
2) se n appartiene ai pari, allora n+2 appartiene ai pari.
Definizione induttiva dell’insieme Pow-2 delle potenze di due.
L’insieme pow-2 è l’insieme più piccolo per cui valgono due proprietà.
1) 1 appartiene a pow-2
2) se n appartiene a pow-2, allora n*2 appartiene a pow-2.
Definizione induttiva di fattoriale
0! = 1 (n+1)! = n! * (n+1)
Dimostra che il fattoriale cresce più velocemente dell’esponenziale.
Caso base: 1! = 1 = 2^0 = 1
Passo induttivo: n! >= 2^n-1
(n+1)! = n! * (n + 1) >= 2^n-1 * (n + 1) >= 2^n-1 * 2 = 2^n
Consideri la successione
S0 = 0
Sn+1 = Sn + 1 + 2*n.
Si dimostri che Sn = n*2
Caso base: S0 = 0 = 0^2.
Passo induttivo: supponiamo che Sn = n*2. Dimostriamo che Sn+1 = (n+1)^2.
Sn+1 = Sn + 1 + 2n = n2 + 2*n + 1 = (n+1)^2.
Per induzione, è vero.
Principio di induzione forte
Se vale che se P(0), P(1), P(2)… P(n) sono vere, allora anche P(n+1) è vera, P(m) è vera per ogni m naturale.
Teorema fondamentale dell’Aritmetica
Ogni numero naturale maggiore di uno è primo o è esprimibile come prodotto di numeri primi.
