Riflessioni di preparazione per il compito di Matematica Discreta

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).

Non solo; il corso di MD da 12 crediti è stato soppresso, quindi dovevo contattare la segreteria didattica con "largo anticipo" per permettere la riapertura, solo per me, del corso di MD da 12 crediti.

Occhio: il corso da 12 crediti ha esattamente lo stesso programma dei due da sei. Per fortuna, contattato il prof mi ha risposto che posso procedere con l'esame del 16 e avere voto e crediti dopo Algebra.

Bene. Veniamo al dunque.

---

1. Ragionare e non presumere di sapere già la risposta. Ragionare e cercare una controprova che il ragionamento fila
2. Leggere attentamente quello che c'è scritto. Molti errori sono dovuti a cattive interpretazioni.

Ora i consigli della nonna sono finiti, passiamo a quelli più specifici.

3. Quando si dimostra per induzione, bisogna usare in qualche punto l'ipotesi induttiva, altrimenti qualcosa non torna.
4. Quando si dimostra per induzione, a volte ci sono due proposizioni con un confronto in mezzo, per esempio A=B oppure C<D. In questo caso bisogna trasformare A in B oppure C in qualcosa <D

Esempio di 4: compito del 23/05/2011, es. 1

Si dimostri per induzione che 1+2+3+...+n≤nⁿ

Base: 1 ≤ 1¹che è evidentemente vero

Passo induttivo: 1+2+3+...+n≤nⁿ ⇒ 1+2+3+...+n + (n+1) ≤(n+1)⁽ⁿ⁺¹⁾

Tutta la parte in grassetto può essere sostituita con nⁿ, quindi si può scrivere

nⁿ+ (n+1) ≤(n+1)⁽ⁿ⁺¹⁾

A questo punto, la tentazione sarebbe di semplificare tutto, per esempio così:

nⁿ+ (n+1) ≤(n+1)⁽ⁿ⁺¹⁾ ⇒ nⁿ+ (n+1) ≤(n+1)ⁿ * (n+1) ⇒ nⁿ≤(n+1)ⁿ

Essendo n∈ℕ, quindi sempre positivo, è possibile scrivere n≤(n+1), che è sempre vero. MA... questo sistema non è corretto!

Il sistema corretto è considerare tutta la parte a sinistra e "trasformarla" nella parte destra. In questo caso possiamo anche "aggiungere" dei valori, perché abbiamo a che fare con una disuguaglianza.

$\stackrel{\text{Parte "sinistra"}}{\text{1+2+3+4+...+n}+\left(n+1\right)}\le \stackrel{\text{Parte "destra"}}{{\left(\mathrm{n}+1\right)}^{\left(\mathrm{n}+1\right)}}$

In qualche modo dobbiamo trasformare la parte sinistra nella parte destra, garantendo che la disuguaglianza sia sempre soddisfatta.

Per ipotesi induttiva,

1+2+3+4+...+n+(n+1) si può scrivere come nⁿ+ (n+1)

nⁿ+ (n+1) è sempre ≤ (n+1)ⁿ+ (n+1)

Riflessione: ho una somma, ma mi farebbe più comodo un prodotto! Devo riuscire ad aggiungere qualche elemento per far sì che (n+1)ⁿ+ (n+1) diventi (n+1)⁽ⁿ⁺¹⁾. Scompongo (n+1)⁽ⁿ⁺¹⁾ in (n+1)ⁿ*(n+1) e poi ancora n(n+1)ⁿ+(n+1) ottengo la strada per arrivare alla soluzione:

(n+1)ⁿ+ (n+1) ≤ n(n+1)ⁿ+(n+1), poiché n è sempre > 0

e n(n+1)ⁿ+(n+1) = (n+1)⁽ⁿ⁺¹⁾

In questa dimostrazione c'è "più algebra", è più complicata, ma è la dimostrazione corretta.

5. Fare esempi può aiutare (o salvare la vita)

Esempio di 5: compito del 23/05/2013, esercizio 3

Si provi per induzione che

$2^n-1=\underset{0\le k\le n-1}{\overset{\mathrm{n}}{\Sigma }}{2}^k$

La base è 1¹ = 1, che è vero.

Il passo induttivo è

$2^n-1=\underset{0\le k\le n-1}{\overset{\mathrm{k}}{\Sigma }}{2}^k\Rightarrow 2^{\left(n+1\right)}-1=\underset{0\le k\le n}{\overset{\mathrm{k}}{\Sigma }}{2}^k$

Come scompongo la sommatoria? Facciamo un esempio, immaginiamo che n-1 sia 3.
La somma di 2⁰+2¹+2²+2³ è 1+2+4+8 = 15

Per arrivare a n bisogna aggiungere altri 16, cioè 2⁴

In effetti arriviamo a 31, che è 2⁵-1.

$\underset{0\le k\le n}{\overset{\mathrm{k}}{\Sigma }}{2}^k=\underset{0\le k\le n-1}{\overset{\mathrm{k}}{\Sigma }}{2}^k+2^n$

Applichiamo l'ipotesi induttiva e otteniamo:
(2ⁿ-1) + 2ⁿ = 2(2ⁿ) - 1 = 2ⁿ⁺¹ - 1

6. I compiti di Gennaio sono più facili di quelli di Maggio. Devo passare. ORA.
7. Quando si indica un numero pari n, si scrive n = 2k con k∈ℕ, per i dispari n=2k+1
8. Una premessa falsa NON rende falsa la implicazione.

Esempio di 8: compito del 9/01/2013, es. 1 (entrambe le versioni sono simili)

La relazione R è sui professori. xRy sse x insegna nello stesso corso di y e x ha pubblicato meno articoli di y (nel testo dell'esame è più preciso).

Riflessiva? No, perché xRx significa che x insegna nello stesso corso di se stesso (vero) E x ha pubblicato meno di x, che è falso

Simmetrica? No, perché se x insegna nello stesso corso di y allora y insegna nello stesso corso di x, MA se x ha pubblicato meno di y, non è vero che y ha pubblicato meno di x

Transitiva? Sì, perché se x ha pubblicato meno di y e y meno di z allora x ha pubblicato meno di z

Antisimmetrica? La proprietà AS dice che se xRy e yRx allora significa che x=y. In questo caso, xRy ⇒ ¬yRx, quindi la premessa è falsa. Questo è il punto a cui bisogna prestare attenzione: PREMESSE FALSE implicano CONSEGUENZE VERE.

In pratica, siccome non succede mai che xRy e yRx allora la proprietà antisimmetrica è vera.

9. Sulla congruenza. Se chiede 3x ≡ 24 (mod 17)... 3·8 è congruo a 24 in qualunque modulo!