# Apply a 1% discount 100 times - elegant way to solve?

A recent story about Kohl's treating "60% off, followed by 25% off" as being equivalent to "85% off" made me think about the extreme case of this:

A "100% discount" by applying a 1% discount 100 times.

(On a separate note, I have not convinced myself that this is truly the extreme case of this, as defined by the highest final price while the sum of discount percentage points equals 100. Is there a way to prove or disprove that a 1% discount x 100 times is the extreme?)

Now what's left is to find the final price. If $P$ is the initial price and $D$ is the price after all discounts are applied, I believe the solution is in this form:

$D = P (\frac{99}{100})^{100}$

But is there a way to simplify this any further, hopefully to the point that I can just use pen and paper to solve this?

-

You can't do better than that for a exact solution, but when $n$ is large:

$$\left(1-\frac{1}{n}\right)^n \approx \frac{1}{e}$$

In the case of $n=100$, above, the value is $0.36603234...$, which is a little less than $\frac{1}{e}\approx0.36788...$.

A closer estimate can be found with these bounds:$$e^{-1}e^{-\frac{1}{2n-2}}<\left(1-\frac{1}{n}\right)^n < e^{-1}e^{-\frac{1}{2n}}$$

You can get this by starting with the power series formula:

$$-\ln (1-z) = z + z^2/2 + z^3/3 + ...$$

For $0<z<1$, we clearly have:

$$z+z^2/2 < -\ln(1-z) < z + z^2/2(1+z+z^2\dots) = z+\frac{z^2}{2(1-z)}$$

Set $z=\frac{1}{n}$ and multiply both sided by $n$ gives you:

$$1+\frac{1}{2n} < -n\ln(1-1/n) < 1 + \frac{1}{2n-2}$$

Multiply by $-1$ and then exponentiate to get the above inequality.

-
Thanks, @Thomas. Can you say how you arrived at those bounds? – Philip Feb 4 '13 at 20:16

More extreme would be $200$ reductions by $0.5\%$, $1000$ reductions by $0.1\%$, etc., although as shown in Thomas's answer you can't get much worse than you already had by this method.

But so far we've only considered the case where all of the discounts are equal. To check that this is the "most extreme," suppose instead that we take $n$ discounts at percentages $100a_1\%, 100a_2\%,\ldots,100a_n\%$, such that the percentages add up to $100\%$, or in other words, $a_1+a_2+\cdots+a_n=1$. It turns out that the corresponding discount will always be at least as great as in the case of taking $n$ discounts of $100\dfrac{1}{n}\%$. In other words, $$(1-a_1)(1-a_2)\cdots (1-a_n)\leq \left(1-\dfrac1{n}\right)^n.$$

This is a consequence of the AM–GM inequality:

$$\sqrt[n]{(1-a_1)\cdots(1-a_n)}\leq\dfrac{(1-a_1)+\cdots+(1-a_n)}{n}=\dfrac{n-1}{n}=1-\frac{1}{n}.$$

Therefore, taking all of the percentages to be equal is "most extreme" in terms of how this unfortunate mis-advertising method would overcharge customers with its "100% off" sale.

-

You can use $\lim_{n \to \infty}(1-\frac 1n)^ n=\frac 1e \approx 0.3679$

-
the two numbers differ in the third decimal place, probably close enough for government work. – Lubin Feb 4 '13 at 19:47