# Does there exist a function whose range is the complement of the range of this function?

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.
$\{3,5,7,8,10,11,13,14,15,17\}$

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

My question is: am I interpreting this scenario properly?

-
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. wolframalpha.com/input/… – Siminore Jul 1 '12 at 12:05
would you add that to the question, please – robjohn Jul 1 '12 at 12:44

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^*$.

-
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.

-
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.

-