In mathematics, the inequality

is not hard to prove with quadratic root discriminant.

But the problem is that my computer science roommate want me to give an induction method. So I tried a new method to prove it, in which I used a small trick deserving taking a note.

Let me firstly restate the problem here: it’s known that

, prove that

The equality holds if and only if

when

,

the inequality obviously holds true.

Assume that when

n=k,

the inequality holds true.

Then when

n=k+1,

if k+1=2m,

if k+1=2m-1,

Therein lies the problem, we cannot break the formula into two parts equally if induction is used.

Instead of proving this inequality directly, we consider another problem which has a subtle link with the issue we are dealing with. Say, when

Prove that

.

Actually, by induction method, because

m<2m-1

this statement holds true definitely. Further more, it gives

when .

Otherwise, the new problem value would be even smaller.

The inspring point for this method is to add a free variable to cater the old problem, though technical when applying it. And I hope this trick will bring me more stuff.

### Like this:

Like Loading...

*Related*

This simple idea is interesting which is widely used in optimization method, such as drift-plus-penalty method according to Michael Neely.

http://en.wikipedia.org/wiki/Drift_plus_penalty