4
$\begingroup$

I'm taking a basic discrete math course and I'm having a hard time with Mathematical Induction.

The problem is stated as:

Suppose that $ a $ and $b$ are real numbers with $0 < b < a$. Prove that if $n$ is a positive integer, then $a^n - b^n \leq na^{n-1}(a - b)$.

The work I have so far is:

  • Basis Step: $$\begin{aligned} P(1) \equiv a^1 - b^1 &\leq (1)a^{(0)}(a - b) \\\ a - b &\leq (1)(1)(a - b) \\\ a - b &\leq a - b \end{aligned}$$

  • Inductive Step: Assume that $P(k)$ is true for any fixed integer $k \geq 0$. Induction Hypothesis: $$ P(k) \equiv a^k-b^k \leq ka^{k-1}(a-b)$$ Prove that $ P(k+1) $ is true given $P(k)$: $$\begin{aligned} P(k+1) &\equiv& a^{k+1} - b^{k+1} &\leq (k+1)a^k(a-b)\\\ &\equiv& a\cdot a^k - b \cdot b^k &\leq (k+1)a^k(a-b)\\\ &\equiv& a\cdot a^k - b \cdot b^k &\leq ka^k(a-b) + a^k(a-b)\\\ &\equiv& a\cdot a^k - b \cdot b^k &\leq a \cdot \underbrace{\left( ka^{k-1}(a-b) \right)}_{IH} + a^k(a-b)\\\ \end{aligned}$$

Where I'm At

I don't really know where to go from there. I think I'm supposed to play around with the left side such that I can find the other part of my Induction Hypothesis on the left side, but I'm lost at that point.

$\endgroup$
  • 1
    $\begingroup$ I don't think $ 0 $ counts as a positive integer, so you should refactor your base case for $ n = 1 $. $\endgroup$ – Waleed Khan Mar 14 '13 at 3:47
  • $\begingroup$ True, I forgot about that somewhere in my transcription from paper to computer. $\endgroup$ – AntoineG Mar 14 '13 at 3:47
4
$\begingroup$

Hint (rather big, imo);

$$a^n-b^n=(a-b)(a^{n-1}+a^{n-2}b+\ldots+ab^{n-2}+b^{n-1})\le (a-b)(a^{n-1}+a^{n-1}+\ldots$$

| cite | improve this answer | |
$\endgroup$
  • $\begingroup$ For the right part of the inequation, how does $(a - b)(a^{n-1} + a^{n-1} + \ldots$ go past the dots? $\endgroup$ – AntoineG Mar 14 '13 at 14:39
  • 1
    $\begingroup$ I got it, thanks a lot! $\endgroup$ – AntoineG Mar 14 '13 at 16:36
3
$\begingroup$

Since $b<a$, then $0<a-b$, so $a^n-b^n\le na^{n-1}(a-b)$ if and only if $$\frac{a^n-b^n}{a-b}\le na^{n-1}.\tag{1}$$ We can write the left hand side of $(1)$ as $$\sum_{k=0}^{n-1}a^kb^{n-1-j}.\tag{2}$$ Use the fact that $0<b<a$ to get the rest of the way. There is no need for induction if you know that $(2)$ holds.

| cite | improve this answer | |
$\endgroup$

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.