Quanto velocemente può crescere il mio tesoro?

Question

Immagina un gioco giocato con i gettoni. Inizi con niente. Ad ogni turno, ricevi$2^k$gettoni, dove$k$è il numero totale di token che hai già. Quanti token hai dopo il file$n$esimo turno?

(Ad esempio, il primo turno hai zero gettoni, quindi ne ricevi uno. Il secondo turno hai un gettone, quindi ne ricevi due. Il terzo turno hai tre gettoni, quindi ne ricevi otto. Il quarto turno ne hai undici token, quindi ricevi 2048.)

Sono curioso di sapere se c'è un modulo chiuso per questo. Sospetto che non ci sia, quindi sarei soddisfatto anche del tasso di crescita asintotico (la "grande O"). Certamente sembra crescere più velocemente dell'esponenziale, ma non riesco a capire quanto più velocemente.

Il mio miglior tentativo di una definizione ricorsiva finora è$a_0 = 0$,$a_n = a_{n-1} + 2^{a_{n-1}}$, ma questo è piuttosto poco elegante e difficile da usare.

(Questa domanda è emersa durante una partita di Magic: the Gathering , usando due carte in particolare: Anointed Procession dice che se vuoi "creare" una pedina (metterla in gioco), ne "crei" invece il doppio, e Mythos of Illuna crea un gettone che è una copia di un'altra carta.Il piano del tavolo virtuale va in crash alla quarta iterazione e sono curioso di quanto potrebbe diventare ridicolo se continuasse.)

Answer 1

La ricorsione è data da$a_0 = 0$e$a_n = a_{n-1} + 2^{a_{n-1}}$

Questo non sembra avere una forma chiusa e Wolfram non pensa che ce ne sia nemmeno una [link]

Da$a_{n-1} = o(2^{a_n-1})$, asintoticamente,$a_n$crescerebbe di quella funzione che assomiglia a tetration .

$a(n) = \Omega(2^{a(n-1)})$cioè cresce almeno tanto velocemente quanto la tetrazione. Sintoticamente, dall'altro$a_{n-1}$è molto più piccolo, dovrebbe contenerlo$a(n) = \Theta(2^{a(n-1)})$

In ogni caso la funzione di tetrazione non è elementare quindi non dovrebbe avere una forma chiusa nelle funzioni elementari.

Answer 2

La risposta intuitiva è quella$2^n \gg n$, Così$2^n +n\approx 2^n$. Una volta che lo accetti, dopo$k$turni che hai$2 \uparrow^k 0$(circa, ignorando i pochi che avevi prima) gettoni. Come dici tu, dopo quattro turni hai$0+1+2+8+2048=2059$. La mia espressione cede$2048$, che non è poi così diverso. Quando parli di funzioni in rapida crescita, le piccole differenze vengono eliminate rapidamente.