Matematica discreta / 6 - 16/10/2015

Una delle definizioni alternative di principio di induzione prevede che P_(n) sia vero solo per un n>x tale che x>1, come sempre con x e n ∈ℕ.
Per esempio, si provi che n²>7n+1 ∀ n>8.

(nota mia: in realtà è facile capire anche che n²>8n+1 ∀ n>9, n²>9n+1 ∀ n>10 eccetera)

Base: per n=8, n²=64 e 64>57, quindi P₍₈₎ è vera.

Passo induttivo.
Supponiamo vero P_(n).

(n+1)² equivale a n²+2n+1

Siccome l'ipotesi induttiva dice che n² > 7n+1, allora possiamo dire che n²+2n+1 > 7n+1+2n+1

Vogliamo ottenere 7(n+1)+1 più qualcos'altro per concludere la dimostrazione, quindi aggiungiamo +7 e -7:

n²+2n+1 > 7n+7+1 +2n+1-7

raccogliamo 7 nell'espressione 7n+7 e sommiamo +1 e -7

Otteniamo

n²+2n+1 > 7(n+1)+1 +2n-6

2n-6 è una quantità sempre positiva, perché vale come minimo 10 (per n=8, poi cresce sempre), quindi

(n+1)² > 7(n+1)+1 ∀ n>8

Seconda forma (forte) del Principio di Induzione

Mentre la prima forma richiede un'ipotesi di base P₍₁₎ è vera e "se P_(n) è vera allora è vera anche P_(n+1)" è vera, e quindi è necessario che siano vere solo la base e P_(n), nella seconda forma è richiesto che sia vero qualunque elemento minore di n.

Prima forma:
1, 2, 3, 4, 5,..., n ⇒ n+1

Seconda forma:
1, 2, 3, 4, 5,..., n-3, n-2, n-1 ⇒ n

Nell'esempio riportato a lezione, dimostriamo che, data una funzione U definita così:

• U₁ = 1
• U₂ = 5
• U_n+1 = 5U_n-6U_n-1 ∀ n≥2

si provi che U_n = 3ⁿ-2ⁿ ∀ n∈ℕ.

Il principio di induzione nella sua prima forma non torna utile, perché la mia ipotesi induttiva può considerare U_n, ma non può fare ipotesi su U_n-1!

Nella seconda forma posso dare per veri tutti gli elementi minori di n, compreso n-1.

Base

Verifico U₁, che è 3¹-2¹ = 1.

Verifico U₂, che è 3²-2² = 5.

Passo induttivo

U_n+1 = 5U_n-6U_n-1

Sostituisco U_n con la formula 3ⁿ-2ⁿ, provata per tutti i naturali fino a n.

U_n+1 = 5(3ⁿ-2ⁿ)-6(3^n-1-2^n-1)

Siccome 3ⁿ = 3·3^n-1 e 2ⁿ = 2·2^n-1, posso riscrivere l'espressione come

U_n+1 = 5(3·3^n-1-2·2^n-1)-6(3^n-1-2^n-1)

e poi moltiplico la prima parte per il 5 fuori dalla parentesi e la seconda per 6

U_n+1 = 5(3·3^n-1-2·2^n-1)-6(3^n-1-2^n-1) = 5·3·3^n-1 - 5·2·2^n-1-6·3^n-1+6·2^n-1

Raccolgo 3^n-1 e 2^n-1
U_n+1 = 5·3·3^n-1 - 5·2·2^n-1-6·3^n-1+6·2^n-1 = 9·3^n-1-4·2^n-1

ora, 9 = 3³, quindi 9·3^n-1 = 3·3·3^n-1 = 3·3ⁿ = 3ⁿ⁺¹

discorso omologo per -4·2^n-1

Ottengo 3ⁿ⁺¹-2ⁿ⁺¹, che dimostra che anche P_n+1 è vera.

Per il PdI posso affermare che P_(n) è vero ∀ n∈ℕ.

Ricorrenza

Molto brevemente, si definisce un numero (o più numeri) e si ricavano i successivi dal primo.

I due "classici" esempi scelti sono il fattoriale e la serie di Fibonacci.

Fattoriale

Il fattoriale di un numero naturale è il prodotto del numero stesso per tutti i numeri precedenti. Si indica con un punto esclamativo dopo il numero o l'incognita.

1! = 1

2! = 1x2 = 2

3! = 2! x 3 = 6

4! = 3! x 4 = 24

5! = 4! x 5 = 120

6! = 5! x 6 = 720

Fibonacci

Un numero di Fibonacci Φ₍₁₎ = 1, Φ₍₂₎ = 1, quelli successivi sono dati dalla somma del precedente e di quello prima.

1. Φ₍₁₎ = 1
2. Φ₍₂₎ = 1
3. Φ₍₃₎ = 2
4. Φ₍₄₎ = 3
5. Φ₍₅₎ = 5
6. Φ₍₆₎ = 8
7. Φ₍₇₎ = 13
8. Φ₍₈₎ = 21
9. Φ₍₉₎ = 28

Funzioni

Su funzioni, minimi e massimi ho già scritto qui: https://diario.softml.it/prima-lezione.
Quanto scritto si applica ai numeri reali ℝ, mentre minimo e massimo in ℕ sono leggermente diversi.

Mentre ℕ non ha massimo, perché per ogni numero n∈ℕ che voglio tentare di considerare massimo, posso pensare a un n+1, al contrario ha un minimo definito = 1.

Anche i sottoinsiemi ≠∅ di ℕ possono avere minimo e massimo (es. i numeri minori di 10) oppure possono non avere massimo (es. i numeri pari), ma ogni sottoinsieme ≠∅ ha sempre un minimo.

Esempio: sia un insieme X = {n∈ℕ t.c. n²+2n ≤ 60}, trovare, se esiste, minimo e massimo.

Il numero più piccolo che possiamo "dare in pasto" a n²+2n perché il risultato sia minore o uguale a 60 è 1, che è quindi il nostro minimo.

Il massimo, andando per tentativi, è 6.

Dimostrazione dell'esistenza del minimo.

Usiamo il PdI nella seconda forma.

S(n); se X ⊆ ℕ, n∈X, allora X ha minimo

Base: S₍₁₎ è vero? Sì, perché contiene 1, che è minimo di ℕ.

Passo induttivo: supponiamo che S_i sia vero ∀ i ≥ 1 e i ≤ k.
Consideriamo S_(k+1), k+1∈X.

Distinguiamo due casi:

• ∀ x∈X si ha x>k ⇒ k+1 è il minimo di X
• ∃ y∈X, 1≤y≤k, allora S_(y) è vero

Per ipotesi induttiva, X ha minimo.