Disuguaglianza (facile)
Decisamente non per esperti. Sia $p_n$ l'ennesimo numero primo. Dimostrare che $p_n<2^(2^(n-1))$.
Risposte
arrogantemente scrivo in piccolo, quasi fossi sicuro di quello che dico... ma se volete controllare e' meglio 
base: $p_0=2$ e $2<2^{2^{1-0}}=4$
supponiamo che $p_n < 2^{2^{n-1}}$
adesso pensiamo al teorema di euclide. Infiniti numeri primi,
abbiamo che:
$p_{n+1} <= 2*3*...*p_n + 1$ (1)
questo e' facile da vedere perche' se supponiamo per assurdo
$p_{n+1} > 2*3*...*p_n + 1$ abbiamo che
$p_{n} < 2*3...*p_n + 1 < p_{n+1}$, ma dato che $2*3...*p_n+1$ e' primo, la disuguaglianza
e' un assurdo.
Allora da (1) e dall'ipo di induzione segue che
$p_{n+1} <= 2*3...*p_n +1 <= 2^{2^{n-1}}+1 < 2^{2^{n}}$
posso chiederti dove trovi queste disuguaglianze? perche' anche in informatica avere dimestichezza con
maggiorazioni e' utilissimo e se c'e' qualche posto in rete da cui prendere esercizi simili mi piacerebbe saperlo
base: $p_0=2$ e $2<2^{2^{1-0}}=4$
supponiamo che $p_n < 2^{2^{n-1}}$
adesso pensiamo al teorema di euclide. Infiniti numeri primi,
abbiamo che:
$p_{n+1} <= 2*3*...*p_n + 1$ (1)
questo e' facile da vedere perche' se supponiamo per assurdo
$p_{n+1} > 2*3*...*p_n + 1$ abbiamo che
$p_{n} < 2*3...*p_n + 1 < p_{n+1}$, ma dato che $2*3...*p_n+1$ e' primo, la disuguaglianza
e' un assurdo.
Allora da (1) e dall'ipo di induzione segue che
$p_{n+1} <= 2*3...*p_n +1 <= 2^{2^{n-1}}+1 < 2^{2^{n}}$
posso chiederti dove trovi queste disuguaglianze? perche' anche in informatica avere dimestichezza con
maggiorazioni e' utilissimo e se c'e' qualche posto in rete da cui prendere esercizi simili mi piacerebbe saperlo
"vl4d":
posso chiederti dove trovi queste disuguaglianze?
Questa però è veramente larga!
perche' anche in informatica avere dimestichezza con
maggiorazioni e' utilissimo
Si è vero, è utile a stimare ad esempio la complessità spaziale o temporale di un algoritmo
e se c'e' qualche posto in rete da cui prendere esercizi simili mi piacerebbe saperlo
Se cerchi con Emule "Apostols Introduction to Analitic Number Theory" trovi una maggiorazione ben più stretta, non ti preoccupare non richiede grandi conoscenze di matematica
Ok perfetto, non sapevo che apostol avesse scritto un libro di teoria dei numeri(non sono per niente esperto)...
l'anno scorso ho studiato analisi 1 dall'apostol e devo dire che e' il piu' bel libro
di matematica che abbia mai letto... grazie per la dritta
casomai servisse a qualcuno googlando ho trovato anche questo, e' scaricabile gratuitamente
http://shoup.net/ntb/
http://shoup.net/ntl/
l'anno scorso ho studiato analisi 1 dall'apostol e devo dire che e' il piu' bel libro
di matematica che abbia mai letto... grazie per la dritta
casomai servisse a qualcuno googlando ho trovato anche questo, e' scaricabile gratuitamente
http://shoup.net/ntb/
http://shoup.net/ntl/
C'è anche un libro (non facile, però) di Zaccagnini "Introduzione alla Teoria Analitica dei Numeri"..
A me piacciono i problemi di tdn all'esterno dell'informatica, per esempio. Li trovo molto più belli non applicati a nessun'altra scienza..
A me piacciono i problemi di tdn all'esterno dell'informatica, per esempio. Li trovo molto più belli non applicati a nessun'altra scienza..
Accedi a tutti gli appunti
Tutor AI: studia meglio e in meno tempo