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 can't seem to figure out how to find an algebraic formula for the following sequence of numbers. $$0,\ 1,\ 1,\ 0,\ -1,\ -1,\ 0,\ 1,\ 1,\ 0,\ -1,\ -1,\ 0,\ 1,\ 1,\ 0,\ -1,\ -1,\ 0$$

Can somebody help?

share|improve this question

6 Answers 6

Well, I can think of two ways you may have approached this problem. As noted above already, you could have noticed $f(n)=f(n-1)-f(n-2)$ and solved the recurrence algebraically. Perhaps more easy to notice is the fact that this series is periodic with period 6 and then use fourier analysis. In fact if you plot the series you will immediately notice that it looks very much like a sine curve and $f(n)= \frac{2}{\sqrt 3} \sin(\frac{\pi}{3}n)$ fits perfectly.

share|improve this answer

(Inspired by a comment...)

To find the $160$th term, you could notice that the pattern repeats every six numbers.

So we divide by $6$ and look at the remainder.

The $n$th term is

  • $1$ if the remainder is $1,2$
  • $0$ if the remainder is $0,3$
  • $-1$ if the remainder is $4,5$

Since the remainder of $160$ when divided by $6$ is $0$, the $160$th term is $0$.

share|improve this answer

Let $\alpha=\frac{1+i\sqrt{3}}{2}$ and $\beta=\frac{1-i\sqrt{3}}{2}$. Then both $\alpha$ and $\beta$ satisfy $x^2=x-1$. Thus, both $x_k=\alpha^k$ and $x_k=\beta^k$ satisfy $$ x_k=x_{k-1}+x_{k-2}\tag{1} $$ which the desired sequence also satisfies. Therefore, $$ x_k=\frac{\alpha^{k}-\beta^{k}}{i\sqrt{3}}\tag{2} $$ does, too. Furthermore, $x_k$ as given in $(2)$ matches the desired sequence: $x_0=0$ and $x_1=1$. Therefore, the general term in your sequence is given by $(2)$.

Another way to look at this is to consider $$ x_k=\frac{2}{\sqrt{3}}\sin\left(\frac{\pi}{3}k\right)\tag{3} $$ $(3)$ matches for $k$ from $0$ through $5$ and it has period $6$, just like the desired sequence. Thus, $x_k$ as given in $(3)$ also matches your sequence.

share|improve this answer

I'm not sure what you mean by "an algebraic formula", but would you be happy with the observation that it satisfies the recurrence $f(n) = f(n-1) - f(n-2)$?

Addendum: Since you know that it satisfies the recurrence, each term depends only on the previous two terms. Now suppose you know that $f(m) = f(n)$ and $f(m+1) = f(n+1)$ for some $m$ and $n$. Then you know that $f(m+2) = f(n+2)$ also, and, by induction, $f(m+k) = f(n+k)$ for all positive $k$.

But from your enumeration above, you know that $f(0) = f(6)$ and $f(1) = f(7)$. So you can conclude that $f(k) = f(6+k)$ for all positive $k$. So the function has a period of 6.

In particular, for any $k$, $f(k) = f(6+k) = f(12+k) = … = f(6j+k)$ for any $j$. Now if someone gives you $n$, you can write $n$ in the form $n = 6j+k$ where $k$ is in $[0…5]$. You do this by dividing n by 6; $j$ is the quotient and $k$ is the remainder. And we know $f(n) = f(6j+k) = f(k)$. But $k$ is in $[0…5]$ so $f(k)$ is easy to calculate.

To compute $f(n)$ for any $n$, calculate $n÷6$ and find the remainder $k$. Then:

  • If $k$ is 1 or 2, $f(n)=-1$
  • If $k$ is 0 or 3, $f(n)=0$
  • If $k$ is 4 or 5, $f(n)=1$
share|improve this answer
    
I already realize that. I'm trying to come up with a way to know the nth term immediately. Say I want to find the 160th term. I would need an algebraic formula to obtain the answer wouldn't I? That's where I'm stuck. –  Cs132 Apr 13 '12 at 19:16
    
Cs132, this information would be good to include in your question. You can edit it and put what you know and/or what you're trying to find out (more precisely) –  The Chaz 2.0 Apr 13 '12 at 19:22

Define $x \mod N$ to be the remainder $r$ of $x$ when divided by $N$ with $0 \le r \lt N$.

Then your $n^{th}$ term (starting from $0$) is

$$ (n^2 \mod 3) \times (-1)^{\left\lfloor(n \mod 6)/3 \right\rfloor}$$

share|improve this answer
    
Of course, if you wanted to actually use a computer to calculate it, Chaz's answer is probably the fastest and simplest. –  Aryabhata Apr 13 '12 at 19:37
    
It seems to be a quasi-polynomial! –  hkju Apr 13 '12 at 20:32
    
@hkju: I have no idea what that means! –  Aryabhata Apr 13 '12 at 20:50

If you accept trigonometry then (as proposed earlier by others)

$$\dfrac{\sin\left(\dfrac {n\pi}3\right)}{\sin\left(\dfrac {\pi}3\right)}\quad \ \text{else}\quad \ \left|\left(n-\dfrac 32\right) \bmod 6-3\right|-\dfrac 32$$

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.