Quão rápido meu tesouro pode crescer?

Question

Imagine um jogo jogado com fichas. Você começa com nada. A cada turno, você recebe$2^k$tokens, onde$k$é o número total de tokens que você já possui. Quantos tokens você tem após o$n$ª volta?

(Por exemplo, no primeiro turno você tem zero tokens, então você recebe um. No segundo turno você tem um token, então você recebe dois. No terceiro turno você tem três tokens, então você recebe oito. No quarto turno você tem onze tokens, então você recebe 2048.)

Estou curioso para saber se existe um formulário fechado para isso. Suspeito que não haja, então também ficaria satisfeito com a taxa de crescimento assintótica (o "grande O"). Certamente parece crescer mais rápido do que exponencial, mas não consigo descobrir o quanto mais rápido.

Minha melhor tentativa de uma definição recursiva até agora é$a_0 = 0$,$a_n = a_{n-1} + 2^{a_{n-1}}$, mas isso é bastante deselegante e difícil de fazer qualquer coisa.

(Esta questão surgiu durante um jogo de Magic: the Gathering , usando duas cartas em particular: Ungido Procession diz que se você "criar" um token (colocá-lo em jogo), você "cria" o dobro disso, e Mythos de Illuna cria um token que é uma cópia de outro cartão. O tampo da mesa virtual falha na quarta iteração e estou curioso para saber como isso poderia ficar ridículo se continuasse funcionando.)

Answer 1

A recursão é dada por$a_0 = 0$e$a_n = a_{n-1} + 2^{a_{n-1}}$

Isso não parece ter um formulário fechado e Wolfram também não acredita que exista [link]

Desde$a_{n-1} = o(2^{a_n-1})$, assintoticamente,$a_n$iria crescer por essa função que se parece com tetration .

$a(n) = \Omega(2^{a(n-1)})$isto é, cresce pelo menos tão rápido quanto a tetração. Asintoticamente, já que o outro$a_{n-1}$é muito menor, deve conter que$a(n) = \Theta(2^{a(n-1)})$

De qualquer forma, a função de tetração não é elementar, portanto não deve ter uma forma fechada em funções elementares.

Answer 2

A resposta intuitiva é que$2^n \gg n$, assim$2^n +n\approx 2^n$. Depois de aceitar isso, depois$k$voltas que você tem$2 \uparrow^k 0$(sobre, ignorando os poucos que você tinha antes) tokens. Como você diz, depois de quatro voltas você tem$0+1+2+8+2048=2059$. minha expressão dá$2048$, o que não é tão diferente. Quando você está falando de funções de crescimento rápido, pequenas diferenças são eliminadas rapidamente.