Fra n e n!
Fra n e n!
Problema
Provare che vale la seguente catena di disuguaglianze per ogni $ n $ dispari maggiore di 3
$ n\le 2^{\phi(n)}\le 2^n\le n! $
e dire se e quando possono valere le uguaglianze
Provare che vale la seguente catena di disuguaglianze per ogni $ n $ dispari maggiore di 3
$ n\le 2^{\phi(n)}\le 2^n\le n! $
e dire se e quando possono valere le uguaglianze
1)$ n\leq 2^{\varphi(n)} $
Se n = 2K+1, allora abbiamo che
i numeri da $ \frac{n-1}{2} $ a $ n $ sono primi con n, quindi :
$ \varphi(n)\geq \frac{n+1}{2} $
Ci basta dunque dimostrare che $ 2^{\frac{n+1}{2}}\geq n $
Dimostriamolo per induzione:
per n = 5 abbiamo 8 > 5 vera
Supponiamola ora vera per un generico n dispari, vogliamo dimostrarla per n+2,cioè :
$ 2^{\frac{n+3}{2}}\geq n+2 $
Scriviamo dunque:
$ 2^{\frac{n+1}{2}}\geq n $
moltiplicando ambo i membri per 2 otteniamo:
$ 2^{\frac{n+3}{2}}\geq 2n $
Poichè $ 2n\geq (n+2) \forall n \geq 2 $, la nostra tesi è dimostrata.
Affinchè si verifichi l'uguaglianza, deve essere innanzitutto $ n=2^k $
con $ K \in N $, ma poichè per ipotesi n è dispari e maggiore di 3, non abbiamo n che verificano l'uguaglianza
2)$ 2^{\varphi(n)} \leq 2^n $
Discende banalmente dal fatto, evidente, che $ n \geq \varphi(n) \forall n $
L'uguaglianza non è mai verificata.
3)$ 2^n\leq n! $
Procediamo di nuovo per induzione:
.n = 5 : 32 < 120 vera
Ora vogliamo dimostrare $ 2^{n+1}\leq (n+1)! $, supposto vero che
$ 2^n\leq n! $
Moltiplicando ambo i membri per 2, otteniamo
$ 2^{n+1}\leq 2n! $
Bisogna ora dimostrare che $ (n+1)!\geq 2n! \forall n > 3 $
Dividendo infatti entrambi i membri per n!, troviamo proprio n > 3.
Anche in questo caso l'uguaglianza non è mai verificata.
Se n = 2K+1, allora abbiamo che
i numeri da $ \frac{n-1}{2} $ a $ n $ sono primi con n, quindi :
$ \varphi(n)\geq \frac{n+1}{2} $
Ci basta dunque dimostrare che $ 2^{\frac{n+1}{2}}\geq n $
Dimostriamolo per induzione:
per n = 5 abbiamo 8 > 5 vera
Supponiamola ora vera per un generico n dispari, vogliamo dimostrarla per n+2,cioè :
$ 2^{\frac{n+3}{2}}\geq n+2 $
Scriviamo dunque:
$ 2^{\frac{n+1}{2}}\geq n $
moltiplicando ambo i membri per 2 otteniamo:
$ 2^{\frac{n+3}{2}}\geq 2n $
Poichè $ 2n\geq (n+2) \forall n \geq 2 $, la nostra tesi è dimostrata.
Affinchè si verifichi l'uguaglianza, deve essere innanzitutto $ n=2^k $
con $ K \in N $, ma poichè per ipotesi n è dispari e maggiore di 3, non abbiamo n che verificano l'uguaglianza
2)$ 2^{\varphi(n)} \leq 2^n $
Discende banalmente dal fatto, evidente, che $ n \geq \varphi(n) \forall n $
L'uguaglianza non è mai verificata.
3)$ 2^n\leq n! $
Procediamo di nuovo per induzione:
.n = 5 : 32 < 120 vera
Ora vogliamo dimostrare $ 2^{n+1}\leq (n+1)! $, supposto vero che
$ 2^n\leq n! $
Moltiplicando ambo i membri per 2, otteniamo
$ 2^{n+1}\leq 2n! $
Bisogna ora dimostrare che $ (n+1)!\geq 2n! \forall n > 3 $
Dividendo infatti entrambi i membri per n!, troviamo proprio n > 3.
Anche in questo caso l'uguaglianza non è mai verificata.
Sia $ n = 9 $. E allora $ (n-1)/2 = 4 $, eppure $ \gcd(6,9) > 1 $...Igor ha scritto:[...] Se n = 2K+1, allora abbiamo che i numeri da $ \frac{n-1}{2} $ a $ n $ sono primi con n [...]
Ehmmm... Per quanto imbarazzante sia, a qualcuno toccherà pur dirlo, che davvero $ \varphi(1) = 1 $...Igor ha scritto: 2)$ 2^{\varphi(n)} \leq 2^n $. Discende banalmente dal fatto, evidente, che $ n \geq \varphi(n) \forall n $. L'uguaglianza non è mai verificata.
Sarà stato pur dispari e maggiore di 3, mio amicabile Bollazzo, ma vale quel ch'è scritto, non già quel ch'è presunto... Pertanto, se Igor sostiene, come ha fatto, che $ \varphi(n) > n $, per ogni $ n $, beh... personalmente non posso fare a meno di ravvisarci un'inesattezza, e a stento mi trattengo dal dire piuttosto di un errore! La tua dialettica, poi, è così misera che neanche mi disturbo d'insultarti, tuo profitto, al modo in cui di certo avresti titolo e merito di essere insultato, per questo e analoghi altri casi e innumerevoli de' quali, pur tuttavia, ti risparmio, per eccessiva mia benevolenza, la menzione o l'elenco in forma estesa. In quanto ai casi banali, temo davvero - ciao, Evaristo!!! - che possa, e comprensibilmente, cagionare la mancata conquista di qualche punto la confusa leggerezza con cui si è per lo più soliti trattarli... E se mi sbaglio, e non mi sbaglio, mi si linci!!!
amabili nuge...
Lemma #1: la funzione $ f(\cdot): \mathbb{R} \mapsto \mathbb{R}: t \mapsto 2^{t/2} - t $ ha segno positivo, per ogni $ t > 4 $.Boll ha scritto:Problema
Provare che, [...] per ogni $ n $ dispari maggiore di 3: $ n\le 2^{\phi(n)} $, [...] e dire se e quando possono valere le uguaglianze.
Dim.: è sufficiente osservare che, per ogni $ t\in\mathbb{R} $: $ f'(t) = 2^{t/2}\cdot\ln \sqrt{2} - 1 $, cosicché $ f(\cdot) $ è monotona (strettamente) crescente se $ t > 2(1 - \log_2 \ln 2) $. Poiché $ 3 < 2(1 - \log_2\ln 2) < 4 $ ed $ f(4) = 0 $, tanto basta a provare l'asserto.
La soluzione: poiché $ \varphi(5) = 4 $, banalmente $ 2^{\varphi(5)} > 5 $, e pertanto si può supporre per il seguito che $ n $ sia un intero $ > 6 $. In base alla disuguaglianza di Kendall-Osborn (click!), per ogni intero $ n > 6 $: $ \varphi(n) \geq \sqrt{n} $. E allora, stante il lemma #1, se $ n $ è un intero $ > 6 $: $ 2^{\varphi(n)/2} \geq 2^{\sqrt{n}/2} > \sqrt{n} $, e quindi $ 2^{\varphi(n)} > n $. FINE.
Re: Fra n e n!
scusate posso fare delle domande? per quanto banali possano essere..
..cosa significa $ {\phi(n)} $ ?
edit: ah dimenticavo: come è possibile che n < n??
..cosa significa $ {\phi(n)} $ ?
edit: ah dimenticavo: come è possibile che n < n??
Ultima modifica di freeware il 13 mag 2005, 20:00, modificato 1 volta in totale.
Si tenta di spiegarlo qui, freeware... Prova a cliccare, su!!! Tieni conto di un fatto essenziale, priva di avventurarti nella lettura: quel che Bollazzo indica con $ \phi(\cdot) $, altri denotano con $ \varphi(\cdot) $, e tanto ti basti.
Ho il sospetto che tu sia caduto nel mio stesso erre di lettura. cioè, poichè le formule $ \LaTeX $ ti vengono tagliate tu non abbia visto il fattoriale dopo n, che trosforma n<n in n<n!, cosa verissima per n>2. Ecco un esempio di come le formule tagliate in $ \LaTeX $ possano dare fastidio agli utenti...freeware ha scritto:guarda hitleuler io sono un pochino (pochino ! ..) ignorante in materia..per cui a me maiuscolo o minuscolo non fa grande differenza..solo non capisco da dove partire per provare una cosa del genere, perche per me è piuttosto strano, come dicevo, che n < n..
la classe non so' Boll' di sapooon'...
Ma certo che c'è, Bollazzo! Soltanto ch'è un po' standard, e proprio non volevo rinunciare a un'occasione così ghiotta per fare uso della disuguaglianza di Kendall-Osborn. Spero non ti dispiaccia! In ogni caso, siccome lo chiedi...Boll ha scritto:Uh, addirittura derivare!!!! Il quesito me l'ero, per così dire, inventato, pensando a ben altro, quindi dovrebbe esistere un modo di dimostrarlo totalmente elementare.
Dalla disuguaglianza di Bernoulli, per ogni primo naturale $ p\geq 3 $: $ 2^{p-1} > p $. Se poi $ k\in\mathbb{N}_0 $ e $ \displaystyle 2^{p^{k-1}(p-1)} > p^k $, allora: $ \displaystyle 2^{p^{k}(p-1)} > p^{pk} > p^{k+1} $, sicché (per induzione): $ \displaystyle 2^{p^{k-1}(p-1)} > p^k $, per ogni $ k\in\mathbb{N}_0 $. Sia dunque $ n $ un dispari intero $ \geq 3 $.
In base al teorema fondamentale dell'Aritmetica, può porsi allora $ \displaystyle n = \prod_{i=1}^r p_i^{\alpha_i} $, ove $ r\in\mathbb{N}_0 $, $ p_1, p_2, \ldots, p_r $ sono primi naturali a due a due distinti ed $ \alpha_i\in\mathbb{N}_0 $, per ogni $ i=1, 2, \ldots, r $. Viste le premesse, qual che sia $ i=1, 2, \ldots, r $: $ \displaystyle 2^{p_i^{\alpha_i - 1}(p_i - 1)} > p_i^{\alpha_i} $, e perciò $ \displaystyle n = \prod_{i=1}^r p_i^{\alpha_i} < 2^{\sum_{i=1}^r p_i^{\alpha_i - 1}(p_i - 1)} < 2^{\prod_{i=1}^r p_i^{\alpha_i - 1}(p_i - 1)} = 2^{\varphi(n)} $. Può bastare?