Serie con logaritmo

[hamming_burst]

Salve,
vorrei chiedere un parere.

Avendo questa serie, posso maggiorarla in questo modo:

$sum_{k=0}^(n-1) log(n-k) <= sum_{k=0}^(n-1) log(n-1) = (n-1)*log(n-1) <= n*logn$

le maggiorazioni sono per arrivare ad una limitazione asintotica superiore, perciò $O(nlogn)$.

Domanda:
La sommatori dei logaritmi fino ad un valore $(n-1$) è sempre minore di $n*logn$?

$sum_{k=2}^(n) log_2(k) <= nlogn$ ?


Ringrazio chi aiuta

[Rigel1]

Nei passaggi intermedi al posto di $(n-1)$ c'è $n$:
$\sum_{k=0}^{n-1} \log(n-k) = \sum_{j=1}^n \log j \le \sum_{j=1}^n \log n = n\log n$.

PS: La sommatoria proposta è uguale a $\log(n!)$.

[gugo82]

Traduzione: "Ho appena dimostrato una cosa... Secondo voi quello che ho dimostrato è vero?".
Risposta: "Se la dimostrazione è fatta bene, sì".


Inoltre noto che:

[tex]$\sum_{k=0}^{n-1} \ln (n-k) = \sum_{h=1}^n \ln h =\ln \prod_{h=1}^{n} h =\ln n!$[/tex];

ma [tex]$n!\leq n^n$[/tex] (induzione: [tex]$n=1$[/tex] è vera; se è vera per [tex]$n$[/tex], si ha [tex]$(n+1)! =(n+1)\ n! \leq (n+1)\ n^n \leq (n+1)\ (n+1)^n =(n+1)^{n+1}$[/tex] e stop), quindi [tex]$\ln n! \leq n\ln n$[/tex] ed infine:

[tex]$\sum_{k=0}^{n-1} \ln (n-k) \leq n\ \ln n$[/tex].

[hamming_burst]

Ecco perfetto vi ringrazio.
Si vero potevo scrivere meglio la richiesta

si così è molto meglio,
non capivo perchè fosse possibile dire che $sum_{k=1}^n logk = log(n!)$ anche se è noto, non mi era ancora chiaro. Era una proprietà dei logaritmi della somma e prodotto, fantastico

perciò $log_2(n!) in O(nlogn)$

great, grazie mille