APMO Math Problem!?

Question

m and n are positive integers, such that n ≤ m. Prove that:
2^n * n! ≤ (m + n)! / (m - n)! ≤ (m^2 + m)^n

Please answer this problem with work and reasoning for what you did.

Thanks!

And does this problem require combinations in order for the inequality to be proved?

Or does it require AM-GM inquality?

I think I'm making it there!!!!

Don't answer this question until I say "OKAY!"

Thanks!

If you got the answer keep it to yourself for now.

Okay just answer freely. I'm still working on it though. I'll just not read this question for the time being.

I'm currently using a different method to solve this. Actually I'm doing homework =P.

And yea, I did think of it as 2n terms. For the proof I've been working on so far works with n terms seperately. I intend to use the AM-GM inquality after it. Not sure how it might come out.

Answer 1

(2n)! ≤ (m+n)!/(m-n)!
Since (m+n)!/(m-n)! is a product of 2n consecutive integers.
2^n*n! ≤ (2n)!
and the left inequality is established. For the right inequality, expand (m+n)!/(m-n)!,
(m+n)(m+n-1)(m+n-2) ... (m-n+1)
As stated before, there are 2n terms and we can pair each term to sum add up to 2m+1. For example, we can pair (m+n) with (m-n+1), (m+n-1) with (m-n+2), etc.
[(m+n)(m-n+1)] * [(m+n-1)(m-n+2)] * ... * [(m+1)(m)]
For any two positive integers whose sum add up to 2m+1, their product is biggest when the integers are consecutive(why?), namely m and m+1. So each pair's product is less than
m(m+1)=m^2+m
Since there are n pairs, their whole product is less than
(m^2+m)^n
which establishes the upper bound.

Answer 2

This is not too bad if you think of each as a product with 2n terms.

(m + n)! / (m - n)! =
(m+n) * ... * (m+1) * m * ... * (m-n+1)

2^n * n! ≤ (m + n)! / (m - n)! follows from the facts that:
(m-n+i) > i for all 1 <= i <= n and
(m+i) > 2 for all 1<= i <= n

To get (m + n)! / (m - n)! ≤ (m^2 + m)^n notice that:
m^2 + m = m(m+1) and
m(m+1) >= (m - i)(m+1+i) for all i > 0