Welcome to our community

Be a part of something great, join today!

Mathematical Induction problem

eric34

New member
Dec 9, 2012
2
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
Jan 30, 2012
2,506
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
Feb 7, 2012
2,725
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$.