Dimostrazione per induzione Matematica Discreta

Messaggioda NerdMind » 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!
NerdMind
Junior Member
Junior Member
 
Messaggio: 43 di 128
Iscritto il: 21/02/2017, 19:07

Re: Dimostrazione per induzione Matematica Discreta

Messaggioda algibro » 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)$
...
algibro
Junior Member
Junior Member
 
Messaggio: 129 di 378
Iscritto il: 29/01/2017, 15:16

Re: Dimostrazione per induzione Matematica Discreta

Messaggioda NerdMind » 13/01/2018, 10:26

Si, fin li c'ero arrivato! Da li in poi non riesco a continuare
NerdMind
Junior Member
Junior Member
 
Messaggio: 44 di 128
Iscritto il: 21/02/2017, 19:07

Re: Dimostrazione per induzione Matematica Discreta

Messaggioda killing_buddha » 13/01/2018, 11:23

$n!(n+1)=(n+1)!$
- "Everything in Mathematics that can be categorized, is trivial" (P. J. Freyd), which should be understood as: "category theory is good ideas rather than complicated techniques".
- "I always disliked Analysis" (P. J. Freyd)
Avatar utente
killing_buddha
Cannot live without
Cannot live without
 
Messaggio: 1875 di 5766
Iscritto il: 03/05/2008, 17:33

Re: Dimostrazione per induzione Matematica Discreta

Messaggioda algibro » 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)$ !?
algibro
Junior Member
Junior Member
 
Messaggio: 131 di 378
Iscritto il: 29/01/2017, 15:16

Re: Dimostrazione per induzione Matematica Discreta

Messaggioda NerdMind » 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?
NerdMind
Junior Member
Junior Member
 
Messaggio: 45 di 128
Iscritto il: 21/02/2017, 19:07

Re: Dimostrazione per induzione Matematica Discreta

Messaggioda algibro » 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)!$.
algibro
Junior Member
Junior Member
 
Messaggio: 132 di 378
Iscritto il: 29/01/2017, 15:16

Re: Dimostrazione per induzione Matematica Discreta

Messaggioda NerdMind » 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
NerdMind
Junior Member
Junior Member
 
Messaggio: 46 di 128
Iscritto il: 21/02/2017, 19:07


Torna a Algebra, logica, teoria dei numeri e matematica discreta

Chi c’è in linea

Visitano il forum: Google Adsense [Bot] e 1 ospite