- 03 Dec '04 17:42 / 1 editthis 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*)) - 03 Dec '04 21:03 / 5 editsThis 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? - 04 Dec '04 15:41 / 3 editswell-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.