Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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

share|improve this question
    
You could "solve for $n$" by completing the square. –  The Chaz 2.0 Jul 16 '12 at 2:51
    
Thank you for commenting, I have edited my post to match my needs. What do you mean by 'completing the square'? –  Tyymo Jul 16 '12 at 3:16

3 Answers 3

up vote 2 down vote accepted

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

share|improve this answer
    
Thanks so much! That was exactly the solution I was looking for, very useful in general for other needs. –  Tyymo Jul 16 '12 at 3:23
    
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 –  The Chaz 2.0 Jul 16 '12 at 3:29

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.

share|improve this answer

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.

share|improve this answer

Your Answer

 
discard

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.