a *mental* induction proof

genius
Posers and Puzzles 03 Dec '04 17:42
1. genius
Wayward Soul
03 Dec '04 17:421 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 &quot;mental&quot;, 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 &lt; (2^n).((a^n) + (b^n))
2. 03 Dec '04 21:035 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&lt;2 -- check
n=1: a+b &lt; 2(a+b) -- check

Now for the induction:

We assume that (a+b)^n &lt; 2^n*(a^n+b^n)
(a+b)^n+1 = (a+b)*(a+b)^n &lt; (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 &lt;= a^(n+1)*b^(n+1)
Now we assume that a&lt;=b so that a = l*b with 0&lt;=l&lt;=1
Then we must check that l^n*b^(n+1)+l*b^(n+1) &lt;= l^(n+1)*b^(n+1) + b^(n+1)
or, that l^n + l &lt;= l^(n+1) + 1 (since b is positive)

We prove this once again by induction ðŸ˜› (can anyone do this easier?):
n=0: 1+l &lt;= l+1 -- check

Now, we assume that l^n + l - l^(n+1) -1 &lt;= 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 &lt;= 0 we must show that 0 &lt;= l^2 - 2*l + 1
Luckily this is the case, as l^2 - 2*l + 1 &gt;= 0 for l in [0,1].
So l^n + l &lt;= l^(n+1) + 1 and (a+b)^n &lt; 2^n*(a^n+b^n) for all n&gt;0

QED

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

(a + b)^n &lt; (2^n).((a^n) + (b^n))

Prove for n = 1

(a + b) &lt; 2.(a + b)

thus, true for n = 1

Assume for n = k

(a + b)^k &lt; (2^k).((a^k) + (b^k))

Prove for n = k + 1

(a + b)^(k + 1) &lt; (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 &lt; (2^k).((a^k) + (b^k)) thus,
(a + b)^(k + 1) &lt; (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)) &lt; (2^(k + 1)).((a^(k + 1)) + (b^(k + 1))) -- (*)

=&gt; (a^k) + (b^k) &lt; 2.((a^(k + 1)) + (b^(k + 1)))
=&gt;a.(a^k) + a.(b^k) + b.(a^k) + b.(b^k) &lt; 2.(a.(a^k) + b.(b^k))
=&gt;a.(b^k) + b.(a^k) &lt; a.(a^k) + b.(b^k)
=&gt;0 &lt; a.(a^k) + b.(b^k) - b.(a^k) - a.(b^k)
=&gt;0 &lt; (a-b).((a^k) - (b^k))

which is true.

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