2010/9/16 Marcelo Salhab Brogliato msbro...@gmail.com:
Olá, Guilherme,
por indução:
Hipótese: ln(n!) = nln(n) - n + O(log(n))
Tese: ln((n+1)!) = (n+1)ln(n+1) - n + 1 + O(log(n+1))
Entretanto, vamos dar uma ajustada na tese.
Sabemos que 1 \in O(ln(n)), logo: 1 + O(ln(n+1)) = O(ln(n)).
Também sabemos que ln(n+1) + O(ln(n+1)) = O(ln(n+1)).
Assim:
Tese: ln((n+1)!) = nln(n+1) - n + O(ln(n+1))
Demo:
ln((n+1)!) = ln((n+1)n!) = ln(n+1) + ln(n!)
Usando a hipótese, temos:
ln((n+1)!) = ln(n+1) + nln(n) - n + O(ln(n))
Bem, como O(ln(n)) \subset O(ln(n+1)) e ln(n+1) \in O(ln(n+1)), temos:
ln((n+1)!) = nln(n) - n + O(ln(n+1))
Somando e subtraindo nln(n+1), temos:
ln((n+1)!) = nln(n+1) + nln(n) - nln(n+1) - n + O(ln(n+1))
Bom, agora, temos que mostrar que nln(n) - nln(n+1) \in O(ln(n+1)), e esta
fechada a demonstração.
Dei uma mexida mas ainda não saiu...
n(ln(n) - ln(n+1)) \in O(1) na verdade, já que ln'(n) = 1/n. Ou então
porque você sabe que ln(1 - eps) ~ eps, e daí fica ln( n/(n+1) ) = ln(
1 - 1/(n+1) ) ~ 1/(n+1)
Alguém ajuda?! hehehe :)
Eu atrapalho, serve ?
Deixa só eu fazer uma mudança na sua demo. Vou mostrar algo muito mais preciso:
ln(n!) = n*ln(n) + O(1)
Da mesma forma, façamos ln((n+1)!) = ln(n+1) + ln(n!) = ln(n+1) + n*ln(n) + O(1)
Somando e subtraindo n*ln(n+1), obtemos
ln((n+1)!) = (n+1)*ln(n+1) + n*ln(n) - n*ln(n+1) + O(1). Do que eu
acabei de dizer, n*[ ln(n) - ln(n+1) ] é aproximadamente -1, e
portanto está em O(1).
Bom, com *certeza* uma das demonstrações está errada (já que elas
demonstram resultados incompatíveis). Eu voto as duas... (mas a do
Marcelo dá pra corrigir, enquanto a minha, que prova algo falso, é
incorrigível). Mas a pergunta fica: onde estas demonstrações entraram
pelo cano???
abraços,
Salhab
abraços (e mesmo que eu fale bem de indução, é algo a se manipular com
mito cuidado)
2010/9/16 Guilherme Vieira rjguilhermevie...@hotmail.com
Prezado Paulo,
Creio que não há como fazer a demonstração através de indução. Na
internet, vi esse resultado. Não sei, contudo, se o desenvolvimento que o
justifica está correto. É muito complexo. Ver, por exemplo, o site abaixo.
http://en.wikipedia.org/wiki/Stirling's_approximation
O mais simples e natural (a meu ver) é obter ln(n!) ~ n*ln(n) - n +
ln(n) / 2 + O(1) por integração de 1 até n+1 do logaritmo:
integral de 1 a n+1 de log(x) dx é aproximadamente igual à soma dos
trapézios de coordenadas (i, 0), (i+1, 0), (i+1, ln(i+1)), (i,ln(i))
(faça um desenho !!!). A área dos trapézios é igual à ln(n!) + ln(n+1)
/ 2 (cada trapézio dá [ ln(i) + ln(i+1) ]/2, e daí você telescopa no
n!).
Resta estimar o erro, que é a soma das integrais de i a i+1 de log(x)
- {reta afim ligando (i,ln(i)) a (i+1, ln(i+1))}. Aqui, tem que fazer
mais contas... e ajuda fazer mudanças de variáveis nas integrais,
porque a equação da reta fica mais simples se a gente fizer a integral
de zero a 1. (pense assim: se 0 corresponde ao ponto i, temos ln(i),
no ponto 1 temos ln(i+1), isso dá direto o coeficiente diretor e o
coeficiente afim ; ao mesmo tempo, teremos agora ln(i+x) em vez de
ln(x)...)
erro(i) = integral de zero a 1 de ln(i+x) - [ ln(i) + [ln(i+1) - ln(i)]*x ] dx
= integral de ln(1 + x/i) - x*ln(1 + 1/i) dx
e aqui você vê que a diferença entre os dois termos é do tipo
phi(x)/i^2 (a derivada de ambas em 0 é a mesma, logo elas só podem
diferir em segunda ordem, que é o caso). Se você conhece equivalentes
(ou séries de Taylor) o primeiro é ~ x/i - x^2/2*i^2 + O(x^3/i^3) e o
segundo ~ x*[ 1/i -1/2*i^2 + O(1/i^3) ]. Como x está entre 0 e 1, ele
é limitado, e portanto a integral será algo do tipo Const/i^2 (mais
termos de ordem superior, claro). O legal é que a soma desses termos
(em i) é convergente, logo limitada, logo o erro é controlado por uma
constante que não depende de quantos termos de erro a gente somar.
Ufa, deu O(1). Ah, sim, tem que integrar ln(x) de 1 a n+1 também, mas
isso eu deixo para você fazer e ver que dá (n+1)*ln(n+1) - n, e usando
(de novo) que a diferença entre n*ln(n) e n*ln(n+1) é O(1) você
termina com:
Integral = Soma dos trapézios + resto
(n+1)*ln(n+1) - n = ln(n!) + ln(n+1) / 2 + O(1)
Logo
ln(n!) = n*ln(n+1) - n + ln(n+1)/2 + O(1) =
n*ln(n) - n + ln(n)/2 + O(1) + n[ln(n+1) - ln(n)] + [ln(n+1) - ln(n)]/2 =
n*ln(n) - n + ln(n)/2 + O(1) + O(1) + O(1/n) = n*ln(n) - n + ln(n)/2 + O(1)
Grande abraço,
Guilherme
Abraços,
--
Bernardo Freitas Paulo da Costa
=
Instruções para entrar na lista, sair da lista e usar a lista em
http://www.mat.puc-rio.br/~obmlistas/obm-l.html
=
