Anotações - Qual Sequência Cresce Mais Rápido - 2023-2

Advertência: Estas anotações são super resumidas. Recomandamos que você assista ao vídeo correspondente. Qual sequência cresce mais rápido? 2^n ou n^10? Vamos tentar olhar o gráfico de f(x) = x^10 / 2^x Inicialmente, parece que x^10 cresce muito mais rápido que 2^x Qual sequência cresce mais rápido? 2^n ou n^10? Vamos tentar olhar o gráfico de f(x) = x^10 / 2^x Cuidado! A situação muda quando consideramos valores maiores de x. Qual sequência cresce mais rápido? 2^n ou n^10? Afirmação: lim (n->∞) n^10 / 2^n = 0 Fato geral: (Assintoticamente) O crescimento exponencial é muito mais rápido que o crescimento polinomial. Fato geral: Para qualquer b>1 e qualquer k \lim_{n \to \infty} \frac{n^k}{b^n} = 0 Demonstração: seja \ a_n = \frac{n^k}{b^n} Afirmação: \{a_n\} é decrescente a partir de um certo termo Além disso, a_n > 0 \ para \ todo \ n Prova da afirmação: \frac{a_{n+1}}{a_n} = \frac{(n+1)^k}{b} \frac{b^n}{n^k} = \left(\frac{(n+1)^k}{n^k}\right) \frac{1}{b} \to \frac{1}{b} < 1 \Rightarrow a_{n+1} < a_n \ \ a \ partir \ de \ um \ certo \ n \Rightarrow \{a_n\} é convergente, a_n \to L Se \, L \neq 0, \frac{a_{n+1}}{a_n} \to \frac{L}{L} = 1 \ \ absurdo! Portanto, \ L = 0 Vamos usar a notação \ a_n \ll b_n \ quando \lim_{n \to \infty} \frac{a_n}{b_n} = 0 Isso quer dizer que assintoticamente b_n é muito maior que a_n Acabamos de mostrar que \ n^k \ll b^n \ \ se \ b>1. Vamos agora ver que: \ ln(n) \ll n^k \ll b^n \ll n! \ll n^n k > 0 \ não \ precisa \ ser \ inteiro em \ particular \ ln(n) \ll \sqrt{n} Afirmação: Se \ r > 0 \, \lim_{n \to \infty} \frac{ln(n)}{n^r} = 0 Prova: Considera \ f(x) = \frac{ln(x)}{x^r} \ , \ x \geq 1 \ , \ variável \ contínua L'Hôpital \Downarrow \lim_{x \to \infty} \frac{ln(x)}{x^r} = \lim_{x \to \infty} \frac{1/x}{r x^{r-1}} = \lim_{x \to \infty} \frac{1}{r x^r} = 0 Portanto, \frac{ln(n)}{n^r} \to 0. O mesmo vale para qualquer base de logaritmo pois \ log_b n = \frac{ln(n)}{ln(b)} Já sabemos: ln(n) << n^k << b^n Falta ainda mostrar: b^n << n! << n^n É intuitivo: b^n = b.b.b...b n fatores fixos n! = 1.2...n n fatores, alguns muito grandes n^n = n.n...n n fatores, todos muito grandes Mas vamos argumentar com rigor. Daqui a pouco. Pra testar a intuição: Baralho comum com 52 cartas De quantas maneiras diferentes podemos ordenar as cartas? 52.51.50...1 = 52! ≈ 8.10^67 Número de átomos no planeta Terra ≈ 10^50 Teorema: Para qualquer b lim b^n/n! = 0 n->∞ Demonstração: (supondo b>0) seja x_n = b^n/n! Afirmação: {x_n} é decrescente a partir de um certo termo Além disso, x_n > 0 para todo n Prova da afirmação: x_{n+1}/x_n = b^{n+1}/(n+1)! * n!/b^n = b/(n+1) < 1, se n é grande ⇒ x_{n+1} < x_n a partir de um certo n {x_n} é convergente x_n -> L, L=? x_{n+1} = b/(n+1) x_n, faz n->∞ obtém L = 0.L ⇒ L = 0 Afirmação: lim n→∞ n!/n^n = 0 Prova: 0 < n!/n^n = 1⋅2⋅3⋯n / n⋅n⋅n⋯n = 1/n ⋅ (2⋅3⋯n / n⋅n⋅n) < 1/n Resumindo, 0 < n!/n^n < 1/n → 0 Pelo Teorema do Sanduíche, n!/n^n → 0 Aproximação de Stirling n! ∼ √(2πn) (n/e)^n Isso significa que lim n→∞ n!/√(2πn) (n/e)^n = 1