¿Qué tan rápido puede crecer mi tesoro?

Question

Imagina un juego jugado con fichas. Empiezas sin nada. Cada turno, recibes$2^k$fichas, donde$k$es el número total de tokens que ya tienes. ¿Cuántas fichas tienes después de la$n$el turno?

(Como ejemplo, el primer turno tiene cero fichas, por lo que recibe una. El segundo turno tiene una ficha, por lo que recibe dos. El tercer turno tiene tres fichas, por lo que recibe ocho. El cuarto turno tiene once fichas, por lo que recibe 2048.)

Tengo curiosidad si hay un formulario cerrado para esto. Sospecho que no la hay, por lo que también estaría satisfecho con la tasa de crecimiento asintótico (la "gran O"). Ciertamente parece crecer más rápido que exponencial, pero no puedo calcular cuánto más rápido.

Mi mejor intento de una definición recursiva hasta ahora es$a_0 = 0$,$a_n = a_{n-1} + 2^{a_{n-1}}$, pero esto es bastante poco elegante y difícil de hacer.

(Esta pregunta surgió durante un juego de Magic: the Gathering , usando dos cartas en particular: Anointed Procession dice que si "creas" una ficha (la pones en juego), "creas" el doble en su lugar, y Mythos of Illuna crea una ficha que es una copia de otra carta. La mesa virtual falla en la cuarta iteración, y tengo curiosidad por lo ridículo que podría volverse si continuara).

Answer 1

La recursión está dada por$a_0 = 0$y$a_n = a_{n-1} + 2^{a_{n-1}}$

Esto no parece tener una forma cerrada y Wolfram tampoco cree que la haya [link]

Ya que$a_{n-1} = o(2^{a_n-1})$, asintóticamente,$a_n$crecería por esa función que parece tetración .

$a(n) = \Omega(2^{a(n-1)})$es decir, crece al menos tan rápido como la tetración. Aymptóticamente, ya que el otro$a_{n-1}$es mucho más pequeño, debería sostener que$a(n) = \Theta(2^{a(n-1)})$

En cualquier caso, la función de tetración no es elemental por lo que no debería tener forma cerrada en funciones elementales.

Answer 2

La respuesta intuitiva es que$2^n \gg n$, asi que$2^n +n\approx 2^n$. Una vez que acepta eso, después$k$turnos que tienes$2 \uparrow^k 0$(Sobre, ignorando los pocos que tenías antes) fichas. Como dices, después de cuatro turnos tienes$0+1+2+8+2048=2059$. Mi expresión da$2048$, que no es tan diferente. Cuando se habla de funciones de rápido crecimiento, las pequeñas diferencias desaparecen rápidamente.