Please turn on javascript in your browser to play chess.
Posers and Puzzles

Posers and Puzzles

  1. Standard member genius
    Wayward Soul
    03 Dec '04 17:42 / 1 edit
    this was in my tutorial questions for this week as an optional question, but my tutor didn't go over it on the basis that it was "mental", so i've not seen a decent solution to it. mine works, but it's kinda hard to explain...(i confused my tutor 3 times during the tutorial today...i don't have the gift of explanation...)

    For fixed positive real numbers a and b, prove by induction that (a + b)^n < (2^n).((a^n) + (b^n))
  2. 03 Dec '04 21:03 / 5 edits
    This thing IS mental. But I have proven it (on request I can remake it in LaTeX for readability):

    Okay. The basic step is easy:

    n=0: 1<2 -- check
    n=1: a+b < 2(a+b) -- check

    Now for the induction:

    We assume that (a+b)^n < 2^n*(a^n+b^n)
    (a+b)^n+1 = (a+b)*(a+b)^n < (a+b)*2^n*(a^n + b^n) = 2^n*(a^(n+1) + b*a^n + a*b^n + b^(n+1))
    We want this to be less than or equal to 2^(n+1)*(a^(n+1) + b^(n+1))
    This is the case when b*a^n + a*b^n <= a^(n+1)*b^(n+1)
    Now we assume that a<=b so that a = l*b with 0<=l<=1
    Then we must check that l^n*b^(n+1)+l*b^(n+1) <= l^(n+1)*b^(n+1) + b^(n+1)
    or, that l^n + l <= l^(n+1) + 1 (since b is positive)

    We prove this once again by induction (can anyone do this easier?):
    n=0: 1+l <= l+1 -- check

    Now, we assume that l^n + l - l^(n+1) -1 <= 0
    l^(n+1) + l - l^(n+2) - 1 = l*(l^n + 1 - l^(n+1)) - 1 = l*((l^n + l - l^(n+1) - 1) + 2 - l) - 1 = -l^2 + 2*l + l*(l^n + l - l^(n+1) - 1) - 1. We want this less than or equal to 0.
    Since l^n + l - l^(n+1) - 1 <= 0 we must show that 0 <= l^2 - 2*l + 1
    Luckily this is the case, as l^2 - 2*l + 1 >= 0 for l in [0,1].
    So l^n + l <= l^(n+1) + 1 and (a+b)^n < 2^n*(a^n+b^n) for all n>0

    QED

    Is this easier than your explanation?
  3. Standard member genius
    Wayward Soul
    04 Dec '04 15:41 / 3 edits
    well-i prefer mine, but i think that's just cause i did it...

    (a + b)^n < (2^n).((a^n) + (b^n))

    Prove for n = 1

    (a + b) < 2.(a + b)

    thus, true for n = 1


    Assume for n = k

    (a + b)^k < (2^k).((a^k) + (b^k))


    Prove for n = k + 1

    (a + b)^(k + 1) < (2^(k + 1)).((a^(k + 1)) + (b^(k + 1)))

    if we multiply both sides of the equation for n = k by (a + b),

    (a + b).(a + b)^k < (2^k).((a^k) + (b^k)) thus,
    (a + b)^(k + 1) < (2^k).((a^k) + (b^k)) first part of second equation is smaller than the second part of the first equation multiplied by (a + b))

    Assume (2^k).((a^k) + (b^k)) < (2^(k + 1)).((a^(k + 1)) + (b^(k + 1))) -- (*)

    => (a^k) + (b^k) < 2.((a^(k + 1)) + (b^(k + 1)))
    =>a.(a^k) + a.(b^k) + b.(a^k) + b.(b^k) < 2.(a.(a^k) + b.(b^k))
    =>a.(b^k) + b.(a^k) < a.(a^k) + b.(b^k)
    =>0 < a.(a^k) + b.(b^k) - b.(a^k) - a.(b^k)
    =>0 < (a-b).((a^k) - (b^k))

    which is true.

    as assumption(*) is true then, but induction, problem is true for all n.