Passa al tema normale
Discussioni su Algebra astratta, Logica Matematica, Teoria dei Numeri, Matematica Discreta, Teoria dei Codici, Algebra degli insiemi finiti, Crittografia.

Regole del forum

Consulta il nostro regolamento e la guida per scrivere le formule
Rispondi al messaggio

Dimostrazione per induzione Matematica Discreta

12/01/2018, 19:43

Salve ragazzi, in Matematica Discreta abbiamo fatto il principio d'induzione ma diciamo che mi è indigesto, sto provando a fare un esercizio ma senza risultato!

Il testo dell'esercizio recita: i dimostri per induzione che per ogni n>=5 si ha: \(\displaystyle 3 * 2^{n} < 2 * n! \)

Ora, io dovrei dimostrare il tutto per n+1 ma non riesco a capire come! Qualcuno che abbia voglia di illustrarmi chiaramente come si procede? Grazie!

Re: Dimostrazione per induzione Matematica Discreta

12/01/2018, 23:09

Per prima cosa il passo base, devi dimostrare che la proposizione è vera per $n=5$.
In caso affermativo, supponi che $3 \cdot 2^n < 2 \cdot n!$ sia vera per un certo $n$ e sfruttando questa ipotesi provi, per $n+1$, se è vera la tesi per cui $3 \cdot 2^{n+1} < 2 \cdot (n+1)!$.

i) passo base, $3 \cdot 2^5 < 2 \cdot 5!$
ii) passo induttivo,
$3 \cdot 2^{n+1} < 2 \cdot (n+1)!$
$3 \cdot 2^n \cdot 2 < 2 \cdot n! \cdot (n+1)$
...

Re: Dimostrazione per induzione Matematica Discreta

13/01/2018, 10:26

Si, fin li c'ero arrivato! Da li in poi non riesco a continuare

Re: Dimostrazione per induzione Matematica Discreta

13/01/2018, 11:23

$n!(n+1)=(n+1)!$

Re: Dimostrazione per induzione Matematica Discreta

13/01/2018, 11:33

NerdMind ha scritto:Si, fin li c'ero arrivato! Da li in poi non riesco a continuare



$(3 \cdot 2n) \cdot 2 < (2 \cdot n!) \cdot (n+1)$
e per ipotesi hai $(3 \cdot 2n) < (2 \cdot n!)$
rimane da verificare cosa ? potresti chiederti per quali $n$ si ha $2 < (n+1)$ !?

Re: Dimostrazione per induzione Matematica Discreta

13/01/2018, 11:57

Ok, seguendo un esempio simile del libro sono arrivato a questa soluzione (non so se sia corretta):

\(\displaystyle 3 * 2^{n+1} = 2 * 3 * 2^{n} < 2 * n! < 2 * n! * (n+1) = 2 * (n+1)! \)

L'unica cosa che non ho ben capito è perché devo mettere tutto quello a partire dal secondo minore, qualche spiegazione?

Re: Dimostrazione per induzione Matematica Discreta

13/01/2018, 17:56

NerdMind ha scritto:Ok, seguendo un esempio simile del libro sono arrivato a questa soluzione (non so se sia corretta):

\(\displaystyle 3 * 2^{n+1} = 2 * 3 * 2^{n} < 2 * n! < 2 * n! * (n+1) = 2 * (n+1)! \)

L'unica cosa che non ho ben capito è perché devo mettere tutto quello a partire dal secondo minore, qualche spiegazione?


Io direi come segue.
$3 \cdot 2^{n+1}=3 \cdot 2^n \cdot 2$, fin qui ok. Ora data l'ipotesi per cui $3 \cdot 2^n < 2 \cdot n!$, se moltiplico a sinistra per $2$ e a destra per $(n+1)$, con $n>=5$, la disuguaglianza rimane certamente vera e a questo punto è corretto scrivere
$3 \cdot 2^{n+1}=3 \cdot 2^n \cdot 2 < 2 \cdot n! \cdot (n+1)= 2 \cdot (n+1)!$.

Re: Dimostrazione per induzione Matematica Discreta

16/01/2018, 09:35

algibro ha scritto:
NerdMind ha scritto:Ok, seguendo un esempio simile del libro sono arrivato a questa soluzione (non so se sia corretta):

\(\displaystyle 3 * 2^{n+1} = 2 * 3 * 2^{n} < 2 * n! < 2 * n! * (n+1) = 2 * (n+1)! \)

L'unica cosa che non ho ben capito è perché devo mettere tutto quello a partire dal secondo minore, qualche spiegazione?


Io direi come segue.
$3 \cdot 2^{n+1}=3 \cdot 2^n \cdot 2$, fin qui ok. Ora data l'ipotesi per cui $3 \cdot 2^n < 2 \cdot n!$, se moltiplico a sinistra per $2$ e a destra per $(n+1)$, con $n>=5$, la disuguaglianza rimane certamente vera e a questo punto è corretto scrivere
$3 \cdot 2^{n+1}=3 \cdot 2^n \cdot 2 < 2 \cdot n! \cdot (n+1)= 2 \cdot (n+1)!$.


Oook, penso di aver capito! Grazie :D
Rispondi al messaggio