Lambek-Moser theorem

In combinatorics, Lambek-Moser theorem applies to an increasing arithmetic function with non-negative integral value "f"("n"), Let

:$f^*$

be an integral-valued function such that

:

Then

:$f^\{**\}\; =\; f$.

Let

:$F(n)\; =\; f(n)+n,\; G=f*(n)+n$.

Then the result states that $F,G$ are strictly increasing and the ranges of $F,G$ form a partition of the positive integers.

The theorem was discovered by Leo Moser and Joachim Lambek.

References

*cite journal|last = Lambek|first = J.|coauthors = Moser, L.|title = Inverse and Complementary Sequences of Natural Numbers|journal = The American Mathematical Monthly|volume = 61|issue = 7|date = Aug-Sep, 1954|pages = 454–458|url = http://links.jstor.org/sici?sici=0002-9890%28195408%2F09%2961%3A7%3C454%3AIACSON%3E2.0.CO%3B2-6|accessdate = 2007-04-13|doi = 10.2307/2308078

ee also

*Beatty's theorem

External links

* [http://www.math.ust.hk/excalibur/v3_n4.pdf]
* [http://www.math.ust.hk/excalibur/v4_n1.pdf]
* [http://www.cs.utexas.edu/users/EWD/ewd07xx/EWD753.PDF]