Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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?

share|improve this question
    
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. –  Harald Hanche-Olsen Jan 25 at 13:32
    
You've forgotten to show that $n\in\mathbb N$. Otherwise we couldn't prove the inequality using induction. –  mathh Jan 25 at 13:39
    
Corrected. Thank you. @HaraldHanche-Olsen Thanks for the hint, i'll try to prove it once again. –  aydio Jan 25 at 13:43

1 Answer 1

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.

share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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