0
$\begingroup$

I'm familiar with exponential growth, however I'm not sure how deal with situations where my quantities are discrete and rounding errors come into play.

To be concrete, say I got $N$ items arranged in a line. Now I have every fourth of them replaced by two items. So approximately, we've got N' = N + \frac N 4 = \frac 5 4 N items in the first step. Repeating the process, we have exponential growth.

Precisely however, we need to take into account that our $N$ usually cannot be split evenly into blocks of four, so we've got like

xxxxxxxxx (N=9)

xxx xx xxx xx x (N'=9+2)

So our correct iteration formula would be $N_{n+1} = N_n + \Big \lfloor \frac N 4 \Big \rfloor$ Now is there a closed form solution for $N_n$ after $n$ iterations, much like the exponential growth formula in the continuous case? Can one still apply some growth factor $\frac 5 4$ anywhere?

1 Answers 1

1

You can bound the values from above and below to exhibit the exponential growth. Thus

$N_{n+1}\gt\frac54N_n-1\;,$

so the solution $N_n=(N_0-4)\left(\frac54\right)^n+4$ of the corresponding recurrence relation is a lower bound, and similarly

$N_n\le\frac54N_n\;,$

so that the solution $N_n=N_0\left(\frac54\right)^n$ is an upper bound. Together, you have

$N_0-4\lt\left(\frac45\right)^nN_n\le N_0$

(where I've dropped the constant term to show only the exponential growth).