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
Fra n e n!
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.
, per domande di base di tipo teorico come quella che hai posto c'è la apposita sezione "glossario"..
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!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.
In ogni caso, siccome lo chiedi...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?