A combinatorial proof of Lindstr”om’s theorem on unions of subsets of a finite set

Cosmin Pohoata, A combinatorial proof of Lindstr”om’s theorem on unions of subsets of a finite set. (Link to the PDF file)

In this note, we give a combinatorial proof of Bernt Lindstr\”om’s theorem that if A_{1}, A_{2},…, A_{n+1} are nonempty subsets of an n-element set, then we can find two disjoint and nonempty groups of indices \left\{i_{1},\ i_{2},\ \ldots,\ i_{k}\right\} and \left\{j_{1},\ j_{2},\ \ldots,\ j_{m}\right\} such that
A_{i_{1}} \cup A_{i_{2}} \cup \ldots \cup A_{i_{k}} = A_{j_{1}} \cup A_{j_{2}} \cup \ldots \cup A_{j_{m}}.

Generalizing a curious combinatorial identity

Cosmin Pohoata, Generalizing a curious combinatorial identity, submitted. (Link to the PDF file)

This (very short) note is rather a consequence of founding Theorem 1 from my post from http://www.mathlinks.ro/viewtopic.php?p=1101215#1101215.)

In [5] Simons proved a binomial coefficient identity using repeated differentiation which can be equivalently written as
\sum_{k=0}^{n}{\binom{n}{k}\binom{n+k}{k}(-1)^{n-k}(1+x)^{k}}==\sum_{k=0}^{n}{\binom{n}{k}}{\binom{n+k}{k}x^{k}}.
Proofs of this identity have been given by Chapman [1] using generating functions and by Prodinger [3] using Cauchy’s integral formula. Using Prodinger’s approach Munarini [2] established some generalizations of Simons’ identity and other neat identities, some of them proved by Shattuck recently in [4], using elegant combinatorial arguments. In the following we present an alternate generalization, different from the ones given by Munarini. The proof is very elementary, based on a simple algebraic manipulation.

Cosmin Pohoata, Boole’s formula as a consequence of Lagrange’s interpolating polynomial theorem, INTEGERS: The Electronic Journal of Combinatorial Number Theory, 8 (2008), #A23. (Link to the PDF file).
Another variant of the paper can be downloaded from http://arxiv.org/abs/0807.1133.)

We present a slightly more general version of Boole’s additive formula for factorials as a simple consequence of Lagrange’s Interpolating Polynomial theorem.

Cezar Lupu, Cosmin Pohoata, About a nice inequality, Mathematical Reflections, 1 (2007). (Link to the journal’s PDF file)

We consider two proofs for Darij Grinberg’s a^2+b^2+c^2 + 2abc +1 \geq 2(ab+bc+ca), which lead us to solving several other three-variable inequalities: one from the Romanian National Mathematics Olympiad from 2004, one from the Romanian BMO 2005 Team Selection Tests, one from the Asian Pacific Mathematics Olympiad from 2004 and also one from the USA IMO 2000 Team Selection Tests.