Pergunta assintótica

É $\frac {n!} {2!\cdot 4!\cdot 8!\dots (n/2)!}=O(4^n)$ ?

Estou realmente paralisado e acredito que é verdade, mas não sei como provar.

Qualquer ajuda seria apreciada!

asymptotics factorial big-o-notation Dudi Frid
fonte

O que você tentou provar isso? Você já tentou usar a definição de grande O ou limites?

ryan

o denominador não é claro. é isso

2! * 4! * 6! . . .

$2!*4!*6!...$ ? é isso

2! * 4! * 8! * 16! . . .

$2!*4!*8!*16!...$ ?

Lox

Tnx, eu editei a minha pergunta

Dudi Frid

Então parece que haverá

n - 2

$n-2$ termos no denominador. Você pode emparelhar cada um desses termos com um termo no numerador que seja maior ou igual a ele? Por exemplo, o último

n / 2

$n/2$ termos em

(n / 2)!

$(n/2)!$ iria emparelhar com o último

n / 2

$n/2$ termos em

n!

$n!$ no numerador e cancele. Tente isso com o denominador inteiro.

ryan

Você poderia elaborar sua resposta? E você prova ou desaprova isso?

Dudi Frid

Respostas:

Temos Usando a aproximação de Stirling, podemos obter assintóticos mais refinados, mas deixamos isso para o leitor interessado.

\frac{n!}{(n / 2)! (n / 4)! \dots 2!} = \frac{n!}{(n / 2)! (n / 2)!} \frac{(n / 2)!}{(n / 4)! (n / 4)!} \dots \frac{4!}{2! 2!} \frac{2!}{1! 1!} = (\binom{n}{n / 2}) (\binom{n / 2}{n / 4}) \dots (\binom{4}{2}) (\binom{2}{1}) \leq 2^{n} 2^{n / 2} \dots 2^{4} 2^{2} = 2^{n + n / 2 + \dots + 2 + 1} < 2^{2 n} = 4^{n} .

$\frac{n!}{(n/2)!(n/4)!\cdots 2!} = \frac{n!}{(n/2)!(n/2)!} \frac{(n/2)!}{(n/4)!(n/4)!} \cdots \frac{4!}{2!2!} \frac{2!}{1!1!} = \\ \binom{n}{n/2} \binom{n/2}{n/4} \cdots \binom{4}{2} \binom{2}{1} \leq 2^n 2^{n/2} \cdots 2^4 2^2 = 2^{n+n/2+\cdots+2+1} <2^{2n} = 4^n.$

Yuval Filmus
fonte

Como provar ? E se não for uma potência de ?

\frac{n}{2} + \frac{n}{4} + . . . + 2 + 1 < n

${n\over 2}+{n\over 4}+...+2+1\lt n$

n

$n$

2

$2$

Miniparser 01/09/19

Então, como é ?

n + \frac{n}{2} + \frac{n}{4} + . . . + 2 + 1 < n + n = 2 n

$n+{n\over 2}+{n\over 4}+...+2+1\lt n + n=2n$

miniparser 02/09/19

Meu comentário anterior estava errado. Temos .

n + n / 2 + n / 4 + \dots + 1 = n (1 + 1 / 2 + 1 / 4 + \dots + 1 / n) \leq n \sum_{i = 0}^{\infty} 2^{- i} = 2 n

$n + n/2 + n/4 + \cdots + 1 = n(1 + 1/2+1/4 + \cdots + 1/n) \leq n\sum_{i=0}^\infty 2^{-i} = 2n$

Yuval Filmus

A OP implicitamente assume que é uma potência de 2.

n

$n$

Yuval Filmus