Matematica discreta Categoria

Dimostrare per induzione che n² ≥ 2n + 5 ∀ n ≥ 4

Base: 4² ≥ 2·4 + 5 ⇒ 16 ≥ 13: verificato

Passo induttivo: n² ≥ 2n + 5 ⇒ (n+1)² ≥ 2(n+1) + 5

(n+1)² = n² + 2n + 1

per ipotesi induttiva (l'ipotesi è n² ≥ 2n + 5) possiamo dire che

n² + 2n + 1 ≥ 2n + 5 + 2n + 1

2n + 5 + 2n + 1 = 2n + 2 + 2n + 4 = 2(n+1) + 2(n+2)

il passo induttivo è dimostrato se 2(n+1) + 2(n+2) ≥ 2(n+1) + 5 ⇒ 2n+4 ≥ 5 ⇒ 2n ≥ 5-4 che è vero ∀ n ≥ 4 ∎

Premessa. Qualche mese fa mi sono preso un bidone: mi ero iscritto all'anno accademico 2014-2015, ma a causa dei crediti riconosciuti dalla carriera precedente mi sono ritrovato iscritto con l'ordinamento 2013-2014.

"amen - ho pensato - tanto le materie saranno sempre le stesse". E invece, mi sono ritrovato con Calcolo 1 e Calcolo 2 trasformati in Calcolo e basta (12 crediti) e Matematica Discreta + Algebra lineare trasformati in Matematica Discreta (12 crediti).
Keep reading →

Durante una delle lezioni ci è stata proposta la seguente serie, descritta come sommatoria:

$f\left(n\right)=\sum _{k=1}^{n}4k+3$

Dal cilindro il prof ci ha estratto questa formula:

$f\left(n\right)=\sum _{k=1}^{n}4k+3=$2n²+5n

Poi, con il principio di induzione, ha dimostrato che è vera. E ci ha anche detto che a volte è richiesto che lo studente risalga a questa funzione da solo.

Panico.
Panico da Settimana Enigmistica, ma comunque panico.

Come si risale da una sommatoria a una funzione? Questa è una domanda molto importante soprattutto quando si studiano algoritmi e strutture dati, perché una serie che considera il risultato precedente ha delle prestazioni decisamente più scadenti di una "formuletta" non ricorsiva.

Per risolvere l'enigma, ho pensato alla semplice sommatoria di tutti i numeri da 1 a n:

$\sum _{k=1}^{n}k=\frac{k·\left(k+1\right)}{2}$

che crea la serie

• P₁ = 1
• P₂ = P₁ + 2 = 3
• P₃ = P₂ + 3 = 6
• P₄ = P₃ + 4 = 10
• P₅ = P₄ + 5 = 15
• P₆ = P₅ + 6 = 21
• P₇ = P₆ + 7 = 28
• P_... = P_... + ... = ...

Cosa succede se moltiplico per (ad esempio) 3 l'indice?

$\sum _{k=1}^{n}3k=\text{???}$

• P₁ = 3
• P₂ = P₁ + 6 = 9
• P₃ = P₂ + 9 = 18
• P₄ = P₃ + 12 = 30
• P₅ = P₄ + 15 = 45
• P₆ = P₅ + 18 = 63
• P₇ = P₆ + 21 = 84
• P_... = P_... + ... = ...

La soluzione non può essere molto distante da

$\frac{k·\left(k+1\right)}{2}$

Infatti, dopo qualche tentativo, ho trovato questa formula:

$\frac{3k·\left(k+1\right)}{2}$

Apparentemente la formula sembra applicarsi ai numeri razionali, e non ai naturali, perché è evidente il 3/2.
Però è vero anche che tra n e n+1 uno dei due DEVE essere pari, e quello si semplifica con il 2 al denominatore.

Poi ho provato ad aggiungere una costante alla sommatoria, per cercare in che modo la costante cambia la formula.

$\sum _{k=1}^{n}k+4=\text{???}$

• P₁ = 5
• P₂ = P₁ + 2 + 4 = 11
• P₃ = P₂ + 3 + 4 = 18
• P₄ = P₃ + 4 + 4 = 26
• P₅ = P₄ + 5 + 4 = 35
• P₆ = P₅ + 6 + 4 = 45
• P₇ = P₆ + 7 + 4 = 56
• P_... = P_... + ... = ...

Siccome ogni volta che aggiungo la costante me la "porto dietro" per k volte, ho provato semplicemente ad aggiungere k 4 volte alla formula:

$\frac{k·\left(k+1\right)}{2}+4k$

(no, non ci sono arrivato subito, al primo tentativo, in maniera brillante e sicura)

A questo punto ho tutto quanto mi serve per affrontare la serie proposta dal prof.

$f\left(n\right)=\sum _{k=1}^{n}4k+3$

diventa

$\frac{4k·\left(k+1\right)}{2}+3k$

Questo non assomiglia per niente alla 2n²+5n, ma proviamo a fare qualche passaggio in più.

e abbiamo ottenuto la Formula del Prof©

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.

Una delle formulazioni del principio di induzione è il seguente:dati m, n ∈ ℕ, non è possibile che m < n < m+1In altre parole, tra due numeri consecutivi non esiste alcun altro numero.Tolto il PdI, gli altri assiomi sono validi anche per altri insiemi, come ℤ⁺ e ℝ⁺ (gli interi e i reali positivi).
Keep reading →

Note preliminari

• per la corretta visualizzazione di questa pagina occorre utilizzare un browser che supporta mathml.
• il testo di riferimento (in inglese) è Discrete mathematics di Norman L. Biggs
• sono utilizzati i seguenti caratteri, di cui si suppone che il lettore conosca il significato:
  • ℕ l'insieme dei numeri naturali
  • ∩ intersezione di insiemi
  • ∅ insieme vuoto
  • ∈ appartiene all'insieme (es. n∈ℕ significa n appartiene all'insieme dei naturali)
  • ∀ per ogni (es. n+1=n+1 ∀ n∈ℕ si legge n+1=n+1 per ogni n appartenente di naturali)
  • ∃ Esiste
  • ⇒ determina (es. a<b, b<c ⇒ a<c)
  • < minore, > maggiore, ≤ minore o uguale, ≥ maggiore o uguale, ≠ diverso

Numeri naturali

I numeri naturali sono il primo insieme, che tutti pensano di conoscere

Keep reading →

Mi sono trovato quasi per caso alla lezione odierna di MD, e mi è piaciuta molto.

L'argomento che ha tenuto banco per tutta la sera è l'insieme ℤ, con un'attenzione particolare alla corrispondenza con gli elementi dell'insieme ℕ. Pur senza dirlo esplicitamente, si è dimostrato che la cardinalità dei due insiemi è sempre ℵ₀.

Keep reading →