# Obtain the formula for the following sequence

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?

-

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

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

-

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.

-

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}$$

-
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

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.

-

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

-