Question

a) Prove algebraically that(m+n | p+n)≥(m | p) for all m, p, n ∈ N and such that m≥p.

b) Prove the above inequality by providing a combinatorial proof. Hint: this can be done by creating a story to count the RHS exactly (and explain why that count is correct), and then providing justification as to why the LHS counts a larger number of options.

a) Prove algebraically that p for all m, p, n EN, and such that m 2p b) Prove the above inequality by providing a combinatorial proof. Hint: this can be done by creating a story to count the RHS exactly (and explain why that count is correct) and then providing justification as to why the LHS counts larger number of options

Answer 1

and

(m n)! (mn)! т+ n (mn pn) (pn)! (m - p) (p+n)! p n

т! (т - р)!p! р 72

Taking their ratio we get

'т+п (т - р)\p! (т + п)! (т — р)(р+ п)! р+n х "т т!

Which is

(m+n (mn)p! p+n m!(pn) m

That is

(m+n p+n (m+n)! m! P+n! p! (m

Coming out to be the product

m+n (mn)(mn 1). (m1) (p+n)(p+n 1)(p+1) p+n

But as
m pmk >p+ k m+k 2 1 p+k
for
kp,p- 1,1

And so

m+n m n1 X m1 m n p+n >1 x 1 x 1...1 1 X . m pn p+n - 1 p1

Thus,

(m+n p+n > 1 (m AI

So that ${\binom{m+n}{p+n}\geq }{\binom{m}{p}}$

b) Combinatorially, RHS counts number of ways of selecting m objects out of p

Adding n objects to both, the LHS counts the number of ways of selecting m+n objects out of p+n

To all the combinations that belong to the first category, we can simply add to them the newly added n objects to get a new combination of m+n objects out of p+n

There are other combinations which are not of this form also for example, ones which might not use any of the m objects at all

So that ${\binom{m+n}{p+n}\geq }{\binom{m}{p}}$