Prove the following inequality using induction: $$(1 + \epsilon)^n \leq 1+ (2^n - 1)\epsilon$$ for every $n \in \mathbb{N}: n \geq 1$ and $0 \leq \epsilon \leq 1$

I'm familiar with the concept of induction: first, prove for a base case (e.g. $n = 1$) and then prove the implication $A(n) \rightarrow A(n+1)$

But how do I proceed when more than one variable is involved? Begin with two base cases? What would be the next step?

  • $\begingroup$ There is only one variable suitable for induction here, and that is $n$. The other variable $\epsilon$ does not range over the natural numbers, so just treat it like any other unspecified quantity. $\endgroup$ – Harald Hanche-Olsen Jan 25 '14 at 13:32
  • $\begingroup$ You've forgotten to show that $n\in\mathbb N$. Otherwise we couldn't prove the inequality using induction. $\endgroup$ – user26486 Jan 25 '14 at 13:39
  • $\begingroup$ Corrected. Thank you. @HaraldHanche-Olsen Thanks for the hint, i'll try to prove it once again. $\endgroup$ – aydio Jan 25 '14 at 13:43

Let $A(n)$ denote the propositon $(1 + \varepsilon)^n \le 1 + (2^n - 1)\varepsilon$. Then $A(1)$ holds as both sides are equal.

Let's have a look at how much each side changes from $A(n)$ to $A(n+1)$. The left side is multiplied by $(1 + \varepsilon)$ in each step and the difference is therefore $\varepsilon(1 + \varepsilon)^n$. The difference of the right side is $2^{n+1} - 2^n = 2^n\varepsilon$.

The idea is now to compare the difference of both sides. If at the beginning the left side was less than or equal to the right side (and it was since $A(1)$ holds) and at the same time the difference between left and right side is not getting smaller, then the proposition holds for every $n$.

We will prove by induction that $A(n) \implies A(n+1)$. We can bound the difference of the left side with $\varepsilon\big(1 + (2^n - 1)\varepsilon\big) = \varepsilon + (2^n - 1)\varepsilon^2$, as we assume that $A(n)$ holds. We can further conclude that $$\varepsilon + (2^n - 1)\varepsilon^2 \le \varepsilon + (2^n - 1)\varepsilon,$$ as $\varepsilon \in [0,\ 1]$.

This yields the following inequality:

$$\varepsilon(1 + \varepsilon) \le \varepsilon + (2^n - 1)\varepsilon = 2^n\varepsilon,$$

which is the difference of the right side. Therefore $A(n+1)$ holds.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.