# Mathematical Induction problem

#### eric34

##### New member
Hello folks, I have an induction problem that I have been working on, and I am at my wit's end. If anybody could provide me with a nudge in the correct direction, I would greatly appreciate it. I have attempted to factor out a number of terms to find something remotely intuitive here to present and I just cannot find anything. I've managed to come up with (n+1) > a, though I'm not certain that will even help me. The problem is below.

a^n - b^n <= n*(a^n-1)*(a-b) hypothesis

I used p(1) for a basis step. for the inductive step of p(k+1) I'm really at a loss here. Any thoughts on how I may tackle this, whatsoever, will be appreciated.

#### Evgeny.Makarov

##### Well-known member
MHB Math Scholar
You can first prove that $$a^n-b^n=\left(\sum_{i=1}^na^{n-i}b^{i-1}\right)(a-b)$$. This can be proved directly by induction or, as explained here, from the formula for the sum of geometric progression $$\sum_{k=0}^{n-1}x^{k}= \frac{1 - x^n}{1-x}$$, which can be proved by induction.

#### Opalg

##### MHB Oldtimer
Staff member
Hello folks, I have an induction problem that I have been working on, and I am at my wit's end. If anybody could provide me with a nudge in the correct direction, I would greatly appreciate it. I have attempted to factor out a number of terms to find something remotely intuitive here to present and I just cannot find anything. I've managed to come up with (n+1) > a, though I'm not certain that will even help me. The problem is below.

a^n - b^n <= n*(a^n-1)*(a-b) hypothesis

I used p(1) for a basis step. for the inductive step of p(k+1) I'm really at a loss here. Any thoughts on how I may tackle this, whatsoever, will be appreciated.
Hi Eric34, and welcome to MHB.

For the inequality $a^n - b^n \leqslant na^{n-1}(a-b)$ to be true, I think you will have to assume that $a$ and $b$ are positive. The inequality can go wrong if $a$ or $b$ is allowed to be negative.

If you assume that $a\geqslant0$ and $b\geqslant0$, then the inequality is true. But I don't see how to prove it by using induction.

To prove it using algebra, you can factorise $a^n - b^n$ as $$a^n - b^n = (a-b)(a^{n-1}+a^{n-2}b+a^{n-3}b^2 + \ldots + b^{n-1}).$$ If $b\leqslant a$ then $a^{n-1}+a^{n-2}b+a^{n-3}b^2 + \ldots + b^{n-1} \leqslant na^{n-1}$, and so $a^n - b^n \leqslant na^{n-1}(a-b)$. On the other hand, if $a\leqslant b$ then $a^{n-1}+a^{n-2}b+a^{n-3}b^2 + \ldots + b^{n-1} \geqslant na^{n-1}$. Multiplying by $a-b$ (which is negative) changes the sign of the inequality so again we get $a^n - b^n \leqslant na^{n-1}(a-b)$.

To prove the inequality using calculus, divide both sides by $b^n$ and write $x=a/b$. The inequality then becomes $x^n-1\leqslant nx^{n-1}(x-1)$, or $(n-1)x^n - nx^{n-1}+1 \geqslant0.$ You can check that, for $x>0$, the function $f(x) = (n-1)x^n - nx^{n-1}+1$ has a minimum value of 0, when $x=1$, and is therefore positive for all other positive values of $x$.