a question from putnam competition

sean9991

It's essentially (m+n)^(m+n) > C(m+n, m) * m^m * n^n. LHS is the total count of sampling (m+n) times from (m+n) objects with replacement. RHS is the count by (1) seperate the (m+n) objects into two subsets of m and n objects, respectively (2) sampling each subsets by the number of members of the subsets. appearantly, LHS is much greater than RHS.   www.ddhw.com

sean9991

this is a counting problem.  Left hand side is the total possible arrangements of m+n choices from m+n objects, with replacement.  Right hand side is just partial count, since it's more restricted. www.ddhw.com

husonghu

我想sean9991用的是非常smart的方法。我试着用笨办法做 --- 数学规纳法。 因n和m是完全对称的，故可固定其中之一(n)，规纳法证明该式对另一变量(m)为任 意正整数成立即可。 re-write the original as: (n+m)!/(n!m!)<[(n+m)^(n+m)]/[(n^n)(m^m)] when m=1, (n+1)!/(n!1!)<[(n+1)^(n+1)]/[(n^n)(1^1)] is true, as it can be simplified to show: n+1<(n+1)[(n+1)/n]^nwww.ddhw.com Assume: (n+k)!/(n!k!)<[(n+k)^(n+k)]/[(n^n)(k^k)] ......(1) Obviously: [1+1/(n+k)]^(n+k)>(1+1/k)^k which is combined with (1), we have: (n+k)!/(n!k!)<[(n+k)^(n+k)]/[(n^n)(k^k)] <[(n+k)^(n+k)][1+1/(n+k)]^(n+k)/[(n^n)(k^k)(1+1/k)^k] =[(n+k+1)^(n+k)]/[(n^n)((k+1)^k)] .......(2) Multiply the two sides of (2) by (n+k+1)/(k+1), and simplify, we got: (n+k+1)!/[n!(k+1)!]<[(n+k+1)^(n+k+1)]/{(n^n)[(k+1)^(k+1)]} Done.www.ddhw.com