1. Limited time only! Sign up for a free 30min personal tutor trial with Chegg Tutors
    Dismiss Notice
Dismiss Notice
Join Physics Forums Today!
The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

Mathematical induction question

  1. Dec 22, 2011 #1
    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
    [tex]a^n - b^n \leq na^{n-1}(a-b)[/tex]

    2. Relevant equations

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

    Thank you in advance.
     
  2. jcsd
  3. Dec 22, 2011 #2
    EDIT: nevermind. i though i had it but i did not
     
    Last edited: Dec 22, 2011
  4. Dec 22, 2011 #3

    Deveno

    User Avatar
    Science Advisor

    i had one thought, which may or may not be helpful.

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

    so then your problem becomes:

    [tex](b+c)^n - b^n \leq n(b+c)^{n-1}c[/tex]

    now expand the powers of b+c with the binomial formula.
     
  5. Dec 22, 2011 #4

    SammyS

    User Avatar
    Staff Emeritus
    Science Advisor
    Homework Helper
    Gold Member

    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:
    [itex]\displaystyle a^2-b^2\ \ ?\,\leq\,? \ \ 2a^1(a-b)[/itex]

    Factor the left side.

    [itex]\displaystyle (a-b)(a+b)\ \ ?\,\leq\,? \ \ 2a(a-b)[/itex]

    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 [itex]\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})\,?[/itex]

    Each of the n terms in the last factor is less than or equal to an-1.
    For instance: [itex]\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})[/itex]​
     
  6. Dec 23, 2011 #5

    Curious3141

    User Avatar
    Homework Helper

    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,

    [tex](1-x^n) = (1-x)(1+x+x^2+...x^{n-1})[/tex]

    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,

    [tex]1+x+x^2+...x^{n-1}[/tex] 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,

    [tex]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}[/tex]

    and you're done.
     
    Last edited: Dec 23, 2011
  7. Dec 28, 2011 #6
    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.
     
Know someone interested in this topic? Share this thread via Reddit, Google+, Twitter, or Facebook




Similar Discussions: Mathematical induction question
  1. Mathematical Induction (Replies: 6)

  2. Mathematical Induction (Replies: 5)

  3. Mathematical induction (Replies: 8)

  4. Mathematical Induction (Replies: 11)

Loading...