Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

Does this function have a complement on the positive integers in the sense that the range of the complement should be the complement of the range of the function?

$$\frac{1}{8} \left(1-(-1)^n+2 n (2+n)\right)$$

Here is the inverse/complement which I got from Generic Human:

$$\left\lfloor \sqrt{4 n-1}\right\rfloor +n+1$$

Edit per @robjohn:

Domain is $\mathbb{N}$. I'm trying to use the Lambek-Moser theorem to generate complimentary sets.

The formula generates the pronic numbers interleaved with the squares. $\{1,2,4,6,9,12,16,20,25,30\}$

I want to generate the complementary set of everything else.

The Lambek-Moser theorem uses the inverse to generate the complement.

My question is: am I interpreting this scenario properly?

share|cite|improve this question
What is its domain? Its range? – Alex Becker Jul 1 '12 at 12:03
If the domain is $\mathbb{N}$ and you are asking whether the "map" is injective, the answer is yes. The quadratic part is injective, and the term $(-1)^n$ is irrelevant for $n$ sufficiently large. You need to check the the "first" terms are distinct.… – Siminore Jul 1 '12 at 12:05
would you add that to the question, please – robjohn Jul 1 '12 at 12:44
up vote 1 down vote accepted

Note: If all you care about is existence of such a function, then the Lambek-Moser theorem guarantees the existence of such a function simply because $F$ is increasing. But if you want a nice closed-form expression, then Lambek-Moser doesn't tell you that it exists, it can just help you find it.

In the context of the Lambek-Moser theorem, you have the increasing function from $\mathbb N^*\to\mathbb N^*$: $$F(2k)=k(k+1)\\ F(2k+1)=(k+1)^2$$ Define $f(n)=F(n)-n$, which happens to coincide with $F(n-2)$: $$f(2k)=k(k-1)\\ f(2k+1)=(k-1)^2$$ Since $f(2k)=(k-1/2)^2-1/4$, we can write $$f(n)=\left\lfloor \frac{(n-1)^2}{4} \right\rfloor$$ Given $n\ge 1$, we're looking for $p\ge 0$ such that $$f(p)<n\le f(p+1)$$ $$\frac{(p-1)^2}{4}<n\le \frac{p^2}{4}$$ $$(p-1)^2<4n\le p^2$$ $$(p-1)^2\le 4n-1<p^2$$ $$p-1=\lfloor \sqrt{4n-1} \rfloor$$ giving us finally: $$f^*(n)=1+\lfloor \sqrt{4n-1} \rfloor$$ $$\boxed{G(n)=1+n+\left\lfloor \sqrt{4n-1} \right\rfloor}$$ so that $\{F(n):n\ge 1\}$ and $\{G(n):n\ge 1\}$ form a partition of $\mathbb N^*$.

share|cite|improve this answer
In fact, because a square is always congruent to 0 or 1 mod 4, $$\lfloor\sqrt{4n-1}\rfloor = \lfloor\sqrt{4n-2}\rfloor = \lfloor\sqrt{4n-3}\rfloor$$ so the expressions are equivalent. – Generic Human Jul 2 '12 at 16:20

$f(-2)=f(-1)=f(0)=0$ so if the domain is the integers it does not have an inverse. In fact, $f(n)=f(-2-n)$

However, this function is monotonic increasing on the non-negative integers, so it does have an inverse if the domain is the non-negative integers.

Suppose $$ m=\frac18\left(1-(-1)^n+2n(2+n)\right) $$ If $n$ is even, then $(n+1)^2=4m+1$

If $n$ is odd, then $(n+1)^2=4m$

Therefore, here is the inverse:

If $4m$ is a perfect square, then $n=\sqrt{4m}-1$

If $4m+1$ is a perfect square, then $n=\sqrt{4m+1}-1$

If neither $4m$ nor $4m+1$ is a perfect square, then $m$ is not in the range of the function.

share|cite|improve this answer
The OP wrote that the domain is $\mathbb{N}$. – Siminore Jul 1 '12 at 12:36
@Siminore: Thanks. That was added after I started writing my answer, so I didn't see it. However, that part should actually be in the question, not the comments. – robjohn Jul 1 '12 at 12:54
@FredDanielKline: what kind of inverse do you need? Why does the inverse I give explicitly above not work? – robjohn Jul 2 '12 at 13:41
@robjohn, I added two examples to the OP. – Fred Kline Jul 2 '12 at 14:48
@FredDanielKline: So you don't really want an inverse to your function. From your example it looks as if you want a function that generates the complement of the range of the given function. This is a different question altogether. Not only was the question confusing, but also that you accepted clark's answer, since it answers the same question that my answer does. – robjohn Jul 2 '12 at 15:07

write $a_n = \frac{1}{8} \left(1-(-1)^n+2 n (2+n)\right)$ then $a_{n+1}-a_n=\frac{1}{8} \left(1-(-1)^n+2(n+1)(3+n)-(1-(-1)^n+2 n (2+n)\right) =$ $\frac{1}{8} ( (-1)^{n+2}+{-1}^n+10n+6)) \geq \frac{1}{8} (-2+6+10n) >0$ since $a_n$ is increasing it is $1-1$ and it can be inverted using as domain its range.

share|cite|improve this answer

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.