3
$\begingroup$

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

  • 0
    Thank you for commenting, I have edited my post to match my needs. What do you mean by 'completing the square'?2012-07-16

3 Answers 3

2

(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)

  • 0
    Like I said, there are some details that you'll need to mind, depending on the sequence. You were able to "reverse engineer" the positive integer sequence because addition and multiplication are invertible (one-to-one). Some functions [are not](http://en.wikipedia.org/wiki/Inverse_function#Example:_squaring_and_square_root_functions)2012-07-16
0

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.

0

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.