Finding the inverse function, is there a technique?

Question

I came across a way to find whether some number is inside a sequence of numbers. For example the sequence (simple function for positive odd numbers): $$a(n) = 2n + 1.$$ So the numbers inside it go: $1, 3, 5, 7, \ldots$

If I want to test if the sequence contains a number $N,$ I reverse the formula to this: $$n = (N - 1) / 2.$$ If $n$ is an integer, then we know that $N$ is inside the sequence.

But, here is my question, how can I find the inverse function of this formula: $$a(n) = n(2n - 1)$$

---

Note: Please do comment every step and explain the logic behind it, so I'll understand

Answer 1

(Note: there is some fine print about domains and well-defined inverses, but I'll skip to the computations)

Completing the square is a method for isolating a variable in a quadratic equation. For example, if we were trying to solve $$x^2 + 4x = 5$$ we could add $4$ to both sides to get $$x^2 + 4x + 4 = 9$$ and then recognize the left hand side as a perfect square trinomial. So we could write $$(x+2)^2 = 9$$ and take square roots to get $$x + 2 = \pm 3 \Rightarrow x = -2 \pm 3$$

This gives us TWO values, so we won't have a "well-defined" function unless we restrict the domain.

In your case, you have $a = 2n^2 - n$, or $a/2 = n^2 - n/2$, and we'll add $\dfrac{1}{16}$ to both sides to get $$\dfrac{a}{2} + \dfrac{1}{16} = (n - \dfrac{1}{4})^2$$

Now take the square root and add $\dfrac{1}{16}$ to get $n$. (Insert comment on domain restrictions here)

Answer 2

So what you're describing a situation where any element of the sequence is defined as:$$ a_n = p(n), $$ where $p(n) \in \Bbb Z[n],$ i.e. a polynomial in $n$ with integer coefficients. Now to test that a particular integer $N$ is in the sequence it suffices to show that there exists some integer $n$ such that $p(n) - N = 0.$ This is equivalent to saying that the polynomial $p(n) - N$ has an integer roots.

This test for integer roots can be done by the rational root theorem. Equivalently, you can find the roots for the polynomial equation $p(n) - N = 0,$ e.g. by factoring, and then check whether any of the roots is an integer.

Answer 3

If $a$ is your test value then $a = n(2n-1)$ is a quadratic in $n$ with the solution

$$n = \dfrac{1 \pm \sqrt{8a+1}}{4}$$

and you will want this to be a positive integer if your test value is positive.