Induzione - HackMD

# Induzione ###### tags: `md` #### Ricorsione ###### Definizione Una definizione ricorsiva è una regola che, dato il valore del termine inziale, mostra come calcolare il termine n + 1-esimo dal termine n-esimo (es. fattoriale). L'induzione invece è uno strumento che serve per dimostrare qualcosa (un enunciato). #### Principio di induzione ###### Principio Supponiamo che $P(n)$ sia un predicato che dipende da un intero $n \in \mathbb{Z}$. Dato un numero intero $n_0$ vale che: * $P(n_0)$ è vera (base dell'induzione); * Per ogni $k \ge n_0$, è vera l'implicazione $P(k)⇒P(k + 1)$ (passo induttivo, $P(k)$ si chiama ipotesi induttiva); allora possiamo concludere che è vera la proposizione $Q$: "per ogni $n \ge n_0$ vale $P(N)$". #### Progressione aritmetica Una successione di numeri reali $a_0,a_1,...,a_n$ è una progressione aritmetica se le differenze $a_i - a_{i-1}$ sono tutte uguali fra loro (uguali al numero $a$). In generale, si può dire che per ogni $i \in \mathbb{N}, a_i = ai + b$ per certi numeri reali fissati $a$ e $b$. Termine n-esimo: $a_n = a_s + d(r - s)$ La somma dei numeri di una progressione aritmetica si chiama serie aritmetica. $S_n = \frac{1}{2}n(a_1 + a_n)$ #### Progressione geometrica Una successione di numeri reali non nulli $b_0,b_1,...,b_n$ è una progressione geometrica se i rapporti $\frac{b_i}{b_{i-1}}$ sono tutti uguali tra loro (uguali al numero $k$). In generale, si può dire che per ogni $i \in \mathbb{N}, b_i=ck^i$ per certi numeri reali non nulli fissati $c$ e $k$. Termine n-esimo: $a_n = a_1r^{n - 1}$. ###### Definizione ###### Relazioni d'ordine Un ordine totale è un insieme su cui è definita una relazione binaria $\le$ che verifica le seguenti proprietà: * $x \le y \ \land \ y \le z \Rightarrow x \le z$ * $x \le x$ * $x \le y \ \land \ y \le x \Rightarrow x = y$ * $x \le y \ \lor \ y \le x$ Se omettiamo la totalità si ottiene la notazione di ordine parziale. Un esempio di ordine parziale è dato dalla relazione $x$ divide $y$ tra numeri naturali. ###### Definizione Un insieme totalmente ordinato è un buon ordine, o è bene ordinato, se non ammette successioni infinite decrescenti.