1
$\begingroup$

It's commonplace in combinatorics to prove $A = B$ by describing a bijection between sets of size $A$ and $B$.

What are some examples of proving $A < B$ by describing an injection between sets of size $A$ and $B$, or of proving $A > B$ by describing a surjection?

Here's an example of what I'm looking for. Ideally, I'd like some examples that are very elementary (so I can teach them to students without background in a particular area).

$\endgroup$
1
  • 1
    $\begingroup$ Probably too simple, let $B$ be the power set of $A$, map $a$ to $\{a\}$. $\endgroup$
    – André Nicolas
    Oct 21, 2015 at 16:01

1 Answer 1

Reset to default
1
$\begingroup$

Many bounds on binomial coefficients can be proven this way.

For instance, this answer provides such a proof of the inequality $\binom{2n}{n+1} \geq 2^n$.

$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .