Esercizio principio di induzione
salve. L'esercizio chiede di dimostrare che $ (2^n)*n! <= n^n $ per ogni $ n >= 6 $
applico passo base e verifico che sia valido per n=6
passo induttivo : ipotesi. affermo che la disequazione sia vera per n
tesi. calcolo per n+1 : $ 2^(n+1)*(n+1)! <= (n+1)^(n+1) $
svolgo:
$ (2^(n+1))*(n+1)! = (2^n)*n!*2*(n+1) <= n^n*2*(n+1) $ arrivato qui non riesco più a proseguire. ho ipotizzato che dovesse essere $ n^n*2 <= (n+1)^n $ in modo tale che moltiplicando per n+1 ottengo proprio la tesi. Purtroppo provando ad applicare il principio di induzione per verificare che $ n^n*2 <= (n+1)^n $ mi blocco .
infatti dopo aver supposto che $ n^n*2 <= (n+1)^n $ calcolo tale proprietà per n+1 ottenendo la tesi
$ 2*(n+1)^(n+1) <= (n+2)^(n+1) $ che però non sono in grado di verificare.
avete suggerimenti?
grazie mille
applico passo base e verifico che sia valido per n=6
passo induttivo : ipotesi. affermo che la disequazione sia vera per n
tesi. calcolo per n+1 : $ 2^(n+1)*(n+1)! <= (n+1)^(n+1) $
svolgo:
$ (2^(n+1))*(n+1)! = (2^n)*n!*2*(n+1) <= n^n*2*(n+1) $ arrivato qui non riesco più a proseguire. ho ipotizzato che dovesse essere $ n^n*2 <= (n+1)^n $ in modo tale che moltiplicando per n+1 ottengo proprio la tesi. Purtroppo provando ad applicare il principio di induzione per verificare che $ n^n*2 <= (n+1)^n $ mi blocco .
infatti dopo aver supposto che $ n^n*2 <= (n+1)^n $ calcolo tale proprietà per n+1 ottenendo la tesi
$ 2*(n+1)^(n+1) <= (n+2)^(n+1) $ che però non sono in grado di verificare.
avete suggerimenti?
grazie mille
Risposte
Abbiamo:
$ 2^n\cdot n! \le n^n \quad forall n \ge 6 $
Se $n=6$ allora $2^6\cdot 6! = 64\cdot720 = 46080 < 6^6 = 46656 $ vero.
Supposta vera per $n$ mostriamo che è vera per $n+1$ (d'ora e in avanti intendo il $\le$ come ipotetico):
$2^{n+1}\cdot(n+1)! = 2\cdot2^n \cdot (n+1)\cdot n! \le (n+1)^{n+1} = (n+1)^n\cdot(n+1)$
$2\cdot2^n \cdot (n+1)\cdot n! \le (n+1)^n\cdot(n+1)$
$2\cdot2^n \cdotn! \le (n+1)^n$
$2\cdot2^n \cdotn! \le \sum_{k=0}^{n} \((n),(k)) n^{n-k} = n^n\sum_{k=0}^{n} \((n),(k)) \frac{1}{n^k}$
Ora se proviamo che $\sum_{k=0}^{n} \((n),(k)) \frac{1}{n^k} \ge 2 $ abbiamo fatto.
$\sum_{k=0}^{n} \((n),(k)) \frac{1}{n^k} = 1 + n\cdot\frac{1}{n} + \sum_{k=2}^{n} \((n),(k)) \frac{1}{n^k} = 2+\sum_{k=2}^{n} \((n),(k)) \frac{1}{n^k}$
Il che conclude la dimostrazione.
$ 2^n\cdot n! \le n^n \quad forall n \ge 6 $
Se $n=6$ allora $2^6\cdot 6! = 64\cdot720 = 46080 < 6^6 = 46656 $ vero.
Supposta vera per $n$ mostriamo che è vera per $n+1$ (d'ora e in avanti intendo il $\le$ come ipotetico):
$2^{n+1}\cdot(n+1)! = 2\cdot2^n \cdot (n+1)\cdot n! \le (n+1)^{n+1} = (n+1)^n\cdot(n+1)$
$2\cdot2^n \cdot (n+1)\cdot n! \le (n+1)^n\cdot(n+1)$
$2\cdot2^n \cdotn! \le (n+1)^n$
$2\cdot2^n \cdotn! \le \sum_{k=0}^{n} \((n),(k)) n^{n-k} = n^n\sum_{k=0}^{n} \((n),(k)) \frac{1}{n^k}$
Ora se proviamo che $\sum_{k=0}^{n} \((n),(k)) \frac{1}{n^k} \ge 2 $ abbiamo fatto.
$\sum_{k=0}^{n} \((n),(k)) \frac{1}{n^k} = 1 + n\cdot\frac{1}{n} + \sum_{k=2}^{n} \((n),(k)) \frac{1}{n^k} = 2+\sum_{k=2}^{n} \((n),(k)) \frac{1}{n^k}$
Il che conclude la dimostrazione.
scusa per il ritardo nel rispondere e grazie mille per la risposta. purtroppo non riesco a capire. la sommatoria sarebbe il binomio di newton? e in che modo poi si riesce a dimostrare la tesi?
"anto.tesone1":
scusa per il ritardo nel rispondere e grazie mille per la risposta. purtroppo non riesco a capire. la sommatoria sarebbe il binomio di newton? e in che modo poi si riesce a dimostrare la tesi?
caspiterina! ti ha fatto una signora dimostrazione passo-passo (complimenti Bremen!!) cosa non ti è chiaro?
Sì la "sommatoria" è lo sviluppo del binonio di Newton, puoi controllarlo se non sei convinto!!
come si dimostra la tesi? E' stato chiarissimo!!!
$2\cdot2^n\cdotn!<=n^nsum_(k=0)^(n)((n),(k))1/(n^k)$
ma sappiamo anche che $2^(n)\cdotn!<=n^n$
quindi per dimostrare la tesi basta dimostrare che
$sum_(k=0)^(n)((n),(k))1/(n^k)>2$
ora dovrebbe essere più che chiaro....
Grazie mille a entrambi. Sono riuscito a capire. Il problema stava nel fatto che non mi ero accorto che Bremen aveva usato l ipotesi e che aveva svolto la sommatoria per n=0 e n=1.
Inoltre il procedimento usato da voi è diverso da quello che il prof ci ha fatto usare per la risoluzione degli esercizi. In pratica voi scomponete la tesi e semplificate ciò che compare sia a destra che a sinistra del simbolo di <= mentre io cercavo partendo dalla scomposizione della prima parte della tesi( tutto ciò che c'era a sinistra ) di arrivare tramite l ipotesi alla seconda parte della tesi. E infatti potete vederlo dal mio ragionamento postato nel primo messaggio.
Ancora grazie a entrambi per la disponibilità e l' aiuto.
Inoltre il procedimento usato da voi è diverso da quello che il prof ci ha fatto usare per la risoluzione degli esercizi. In pratica voi scomponete la tesi e semplificate ciò che compare sia a destra che a sinistra del simbolo di <= mentre io cercavo partendo dalla scomposizione della prima parte della tesi( tutto ciò che c'era a sinistra ) di arrivare tramite l ipotesi alla seconda parte della tesi. E infatti potete vederlo dal mio ragionamento postato nel primo messaggio.
Ancora grazie a entrambi per la disponibilità e l' aiuto.
Accedi a tutti gli appunti
Tutor AI: studia meglio e in meno tempo