# Mathematical induction question

1. Dec 22, 2011

### pc2-brazil

1. The problem statement, all variables and given/known data
Suppose a and b are real numbers with 0 < b < a. Show that, if n is a positive integer, then
$$a^n - b^n \leq na^{n-1}(a-b)$$

2. Relevant equations

3. The attempt at a solution
I'm trying to show this by induction.
Let P(n) be the proposition that $a^n - b^n \leq na^{n-1}(a-b)$
I've already verified that P(1) is true, which completes the basis step.
Inductive step:
I must show that, if P(k), then P(k+1).
So, I first assume that this is true for an arbitrary k: $a^k - b^k \leq ka^{k-1}(a-b)$
Then, I must show that, if P(k) is true, it follows that $a^{k+1} - b^{k+1} \leq (k+1)a^k(a-b)$.
This is where I'm having trouble.
I'm trying to find that $a^{k+1} - b^{k+1}$ is less than or equal to an expression involving $a^k - b^k$, so that I can use the expression for P(k) to derive an inequality for $a^{k+1} - b^{k+1}$.
I've tried several ways, like trying to rewrite $a^{k+1} - b^{k+1}$ as $aa^k - bb^{k}$ and then writing that $aa^k - bb^k \geq aa^k - ab^k = a(a^k - b^k)$ (since a > b), but this doesn't help, because I'm looking for something that $a^{k+1} - b^{k+1}$ is less than or equal to, not greater than or equal to.

2. Dec 22, 2011

### Dansuer

EDIT: nevermind. i though i had it but i did not

Last edited: Dec 22, 2011
3. Dec 22, 2011

### Deveno

if b < a, then a = b + c for some positive number c.

$$(b+c)^n - b^n \leq n(b+c)^{n-1}c$$

now expand the powers of b+c with the binomial formula.

4. Dec 22, 2011

### SammyS

Staff Emeritus
It can be instructive to see how the inequality works for the first few values of n. This isn't good enough for a proof, but it may give you some ideas for the proof.

For n=2:
$\displaystyle a^2-b^2\ \ ?\,\leq\,? \ \ 2a^1(a-b)$

Factor the left side.

$\displaystyle (a-b)(a+b)\ \ ?\,\leq\,? \ \ 2a(a-b)$

Of course, (a+b) < 2a because a < b .

So, this case doesn't appear to need induction.​

For n=3:
We have a somewhat similar result with the difference of cubes giving a3-b3 = (a-b)(a2+ab+b2). Then the inequality holds if a2+ab+b2 ≤ 3a2, and this is true for a < b. Again, this doesn't require induction.​

For general n:
Did you know that $\displaystyle a^n-b^n=(a-b)(a^{n-1}+a^{n-2}b+a^{n-3}b^{2}+\dots+a^{((n-1)-k)}\,b^{k}+\dots +a^{2}b^{n+3}+a\,b^{n-2}+b^{n-1})\,?$

Each of the n terms in the last factor is less than or equal to an-1.
For instance: $\displaystyle a^{12}-b^{12}=(a-b)(a^{11}+a^{10}b+a^{9}b^{2}+\dots+a^{5}\,b^{6}+ \dots +a^{2}b^{9}+a\,b^{10}+b^{11})$​

5. Dec 23, 2011

### Curious3141

Building on Sammy's post, you might find it easier to put x = b/a, where 0<x<1

Use polynomial long division to see that for positive integral n,

$$(1-x^n) = (1-x)(1+x+x^2+...x^{n-1})$$

Alternatively you can just multiply the terms on the RHS, cancel out lots of adjacent terms and end up with the LHS. This is one of the polynomial identities which it's really good to know.

Now,

$$1+x+x^2+...x^{n-1}$$ has n terms, each of which is less than or equal to 1. Hence the whole sum is less than or equal to n.

So,

$$a^n - b^n = a^n(1 - x^n) = a^n(1-x)(1+x+x^2+...+x^{n-1}) = a(1-x).a^{n-1}.(1+x+x^2+...+x^{n-1}) = (a-b).a^{n-1}.(1+x+x^2+...+x^{n-1}) \leq (a-b).n.a^{n-1}$$

and you're done.

Last edited: Dec 23, 2011
6. Dec 28, 2011

### pc2-brazil

Very interesting idea.
I knew that result for an - bn, but I didn't think of using it.
This leads directly to the desired result, not requiring induction.