Re: Proving an inequality
 by Hugo van der Sanden at 18:51 01/07/05 (Blogs::Hugo)
 ...or failing that one that a proper mathematician might be motivated to have a crack at: time to go ask around. So I went to the Math Forum to "Ask Dr. Math", and got two excellent replies which proved the result in two different ways. Unfortunately I didn't get an answer to "is it ok for me to publish those responses?", so I'll just have to try and reproduce them as best I can. To prove:` ((ks + 1) / (ks - 1))^k <= (s + 1) / (s - 1)` The first approach One way to simplify the problem is to cross-multiply to remove the fractions:``` (ks + 1)^k . (s - 1) <= (ks - 1)^k . (s + 1) ``` Now we can turn the powers into sums:``` sum_{i=0}^k {(s - 1) C(k, i) (ks)^(k - i)} <= sum_{i=0}^k {(s + 1) C(k, i) (ks)^(k - i) (-1)^i} ``` And subtract one side from the other:``` sum_{i=0}^k {((s + 1) (-1)^i - (s - 1)) C(k, i) (ks)^(k - i)} >= 0 ``` Now we can resolve the (-1)^i by splitting the sum into even and odd i:``` sum_{i=0}^{k/2} {2 C(k, 2i) (ks)^(k - 2i)} >= sum_{i=0}^{(k-1)/2} {2s C(k, 2i + 1) (ks)^(k - 2i - 1)} ``` All these terms are positive, and since we count from 0 there are at least as many even values of i as odd values, so if the inequality is satisfied when we match up the evens and odds in pairs we'll have proven the result. So we need:``` 2 C(k, 2i) (ks)^(k - 2i) >= 2s C(k, 2i + 1) (ks)^(k - 2i - 1) C(k, 2i) (ks)^(k - 2i) >= s C(k, 2i + 1) (ks)^(k - 2i - 1) C(k, 2i) (ks) >= s C(k, 2i + 1) k C(k, 2i) >= C(k, 2i + 1) k k! / ((2i)! (k - 2i)!) >= k! / ((2i + 1)! (k - 2i - 1)!) k / (k - 2i) >= 1 / (2i + 1) k(2i + 1) >= k - 2i ki >= i ```.. and since k >= 1, i >= 0 the proof is complete. The second approach We can make the two sides more similar to each other by raising to the power of s; since both sides are positive, and s >= 1 the sign of the inequality stays the same:``` ((ks + 1) / (ks - 1))^(ks) >= ((s + 1) / (s - 1))^s ``` Since we know k >= 1 this is equivalent to showing that ((x + 1) / (x - 1))^x is a decreasing function, which is true if its derivative is negative in the relevant range (ie when x > 1). Now I'm not entirely sure how to differentiate this - the simple form of the Chain Rule doesn't apply, so I think we need to use the more complex partial derivative version:``` f(x) = (x + 1) / (x - 1) g(x) = x z(f, g) = f(x)^g(x) dz/dx = ∂z/∂f df/dx + ∂z/∂g dg/dx ``` Assuming this is correct, we get:``` z' = g . f^(g - 1) f' + g' ln(f) f^f g' = z( f'g/f + g'^2 ln(f) ) = z( -2x / (x^2 - 1) + (ln(x + 1) - ln(x - 1) ) <= 0 ```and since z > 0, we just need:``` 2 x / (x^2 - 1) >= ln(x + 1) - ln(x - 1) ``` For the next bit a change of variables is in order so that we can take advantage of some standard expansions. Let y = 1/x so that our range becomes 0 < y < 1, and we then get:``` 2y / (1 - y^2) >= ln(1 + y) - ln(1 - y) ``` The LHS can be simplified to 1 / (1 - y) - 1 / (1 + y) which gives us the MacLaurin expansion:``` 2y + 2y^3 + 2y^5 + 2y^7 + ... ``` The RHS similarly expands to:``` 2y + 2y^3/3 + 2y^5/5 + 2y^7/7 + ... ``` Comparing these terms pairwise, since y is positive the LHS is trivially greater than or equal to the RHS for each pair, so the LHS sum is indeed greater than or equal to RHS sum, and once again we have proven our result. Hugo
 << Finding weird numbers Truth is stranger ... >>