Defining a repeating series with a simple expression.

Question

I'm looking for a simple expression with which I can define a repeating series.

$$f(0)=0$$ $$f(1)=1$$ $$f(2)=2$$ $$f(3)=3$$ $$f(4)=f(n-4)$$

So, the series goes $0, 1, 2, 3, 0, 1, 2, 3...$ and on and on. I feel like this should have something to do with exponents because in Discrete Math we figured out how to define a series that goes $1, -1, 1, -1...$ but I'm not sure how to even begin defining this.

I don't want anything recursive if I can possibly avoid it. Not sure if that will be a problem.

Thanks a bunch!

EDIT: Spoke to a professor about how to solve this and he says there is a way to do it involving only +/-/*/^/÷, but it involves complex numbers.

Answer 1

Just to add an alternative to the other answers: you can use generating functions to try to find an explicit solution to the recurrence relation. If $F(x)$ is the generating function for the sequence $f(n)$,

$$F(x)=\sum_{n\ge0}f(n)x^n=f(0)+f(1)x+f(2)x^2+f(3)x^3+\cdots$$

then from the recurrence given by

$$\begin{cases}f(0)=0\\f(1)=1\\f(2)=2\\f(3)=3\\f(n)=f(n-4)&\text{for }n\ge4\end{cases}$$

we have

$$\begin{align*} f(n-4)&=f(n)\\ \sum_{n\ge4}f(n-4)x^n&=\sum_{n\ge4}f(n)x^n\\ x^4\sum_{n\ge4}f(n-4)x^{n-4}&=\sum_{n\ge0}f(n)x^n-f(0)-f(1)x-f(2)x^2-f(3)x^3\\ x^4\sum_{n\ge0}f(n)x^n&=F(x)-x-2x^2-3x^3\\ x^4F(x)&=F(x)-x-2x^2-3x^3\\ (x^4-1)F(x)&=-x-2x^2-3x^3\\ F(x)&=\frac{x+2x^2+3x^3}{1-x^4} \end{align*}$$

Expanding into partial fractions, you have

$$F(x)=\frac32\frac1{1-x}-\frac12\frac1{1+x}-\frac1{1+x^2}-\frac x{1+x^2}$$

and expressing each term as a power series we arrive at

$$\begin{align*} F(x)&=\frac32\sum_{n\ge0}x^n-\frac12\sum_{n\ge0}(-x)^n-\sum_{n\ge0}(-x^2)^n-x\sum_{n\ge0}(-x^2)^n\\ F(x)&=\sum_{n\ge0}\left(\frac32-\frac12(-1)^n\right)x^n-\sum_{n\ge0}(-1)^nx^{2n}-\sum_{n\ge0}(-1)^nx^{2n+1} \end{align*}$$

each of which are valid for $|x|<1$.

Now,

$$\sum_{n\ge0}\left(\frac32-\frac12(-1)^n\right)x^n=1+2x+x^2+2x^3+\cdots$$ $$\sum_{n\ge0}(-1)^nx^{2n}=1-x^2+x^4-x^6+\cdots$$ $$\sum_{n\ge0}(-1)^nx^{2n+1}=x-x^3+x^5-x^7+\cdots$$

so it follows that

$$F(x)=\color{lightgray}{0+}\,x+2x^2+3x^3+\color{lightgray}{0x^4+}\,x^5+2x^6+3x^7+\cdots$$

Replace $n=k$ in the latter two series, then split up the first into the even and odd cases, letting $n=2k$ and $n=2k+1$, respectively, so that the generating function can be expressed as

$$F(x)=\begin{cases} \displaystyle\sum_{k\ge0}(1-(-1)^k)x^{2k}&n=2k\text{ is even}\\[1ex] \displaystyle\sum_{k\ge0}(2-(-1)^k)x^{2k+1}&n=2k+1\text{ is odd} \end{cases}$$

From this it follows that a closed form for $f(n)$ can be obtained by splitting into even/odd cases:

$$f(n)_{n\ge0}=\begin{cases}1-(-1)^{n/2}&n\text{ is even}\\2-(-1)^{(n-1)/2}&n\text{ is odd}\end{cases}$$

If I'm not mistaken, there should be a way to get an "even more explicit" form in terms of complex exponentials, but perhaps this result will suffice for your needs.

Answer 2

You could just write $$ f(n) = n \pmod{4} $$ ( a loose use of notation but perfectly clear) or $$ f(n) = n - 4 \lfloor n/4 \rfloor . $$

I think the first would be kinder to your reader.

Answer 3

If you want something along the lines of $(-1)^n$ (which produces $1,-1,1,-1,\ldots$), first consider $$ f_1(n) = \tfrac12\left(1 - (-1)^n\right),$$ which implies that $f_1(n) = 0,1,0,1,\ldots$ for $n = 0,1,2,3,\ldots.$

Example 1

We can slow down the rate of alternation of $f_1$ by making the exponent grow slower: $$ f_2(n) = \tfrac12\left(1 - (-1)^{\lfloor n/2\rfloor}\right),$$ where $\lfloor n/2\rfloor$ is the greatest integer less than or equal to $n/2.$ This function follows the pattern $f_2(n) = 0, 0, 1, 1, 0, 0, 1, 1,\ldots$ for $n=0,1,2,3,4,5,6,7,\ldots.$

Put this together in the form $f(n) = f_1(n) + 2f_2(n)$ and you have the function you asked for. That is, let $$ f(n) = \tfrac32 - \tfrac12(-1)^n - (-1)^{\lfloor n/2\rfloor}. $$

Example 2

If you don't like the greatest-integer function (used in the expression $\lfloor n/2\rfloor$), we can work around this by fiddling with sinusoidal functions. Let $g_1(n) = \cos\left(\frac12 n\pi - \frac14\pi\right),$ so that $\newcommand{s}{\frac{\sqrt2}{2}} g_1(n) = \s,\s,-\s,-\s,\s,\s,-\s,-\s,\ldots$ for $n=0,1,2,3,4,5,6,7,\ldots.$ Then let \begin{align} f(n) &= f_1(n) + 1 - \sqrt2g_1(n) \\ &= \tfrac32 - \tfrac12(-1)^n - \sqrt2\cos\left(\tfrac12 n\pi - \tfrac14\pi\right). \end{align}

Example 3

If you're willing to use complex numbers, notice that $\cos z = \tfrac12\left(e^{iz} + e^{-iz}\right).$ Using the function notation $\exp(z) = e^z$ to make the first equation below more readable, we get \begin{align} \cos\left(\tfrac12 n\pi - \tfrac14\pi\right) &= \tfrac12 \left(\exp\left(i\left(\tfrac12 n\pi - \tfrac14\pi\right)\right) + \exp\left(-i\left(\tfrac12 n\pi - \tfrac14\pi\right)\right)\right)\\ &= \tfrac12 \left(e^{in\pi/2} e^{-i\pi/4} + e^{-in\pi/2} e^{i\pi/4}\right)\\ &= \tfrac12 e^{i\pi/4} \left(e^{in\pi/2} e^{-i\pi/2} + e^{-in\pi/2}\right). \end{align}

Then, using the facts that $e^{i\pi/2}=i,$ $e^{-i\pi/2}=-i,$ and $e^{i\pi/4}=\tfrac{\sqrt2}{2}(1+i),$ \begin{align} \cos\left(\tfrac12 n\pi + \tfrac14\pi\right) &= \tfrac12\left(\tfrac{\sqrt2}{2}(1+i)\right)\left(i^n(-i)+(-i)^n\right)\\ &= \tfrac{\sqrt2}{4}(1+i) \left((-1)^n - i\right) i^n. \end{align}

It follows that $$ f(n) = \tfrac32 - \tfrac12(-1)^n - \tfrac12(1+i)\left((-1)^n - i\right)i^n. $$

And indeed the right-hand side is also equal to $\tfrac32-\tfrac12(-1)^n-\tfrac12(1+i)(-i)^n-\tfrac12(1-i)i^n,$ an expression that was given in a comment under another answer.

---

Frankly, I think any of the preceding examples is far clumsier than Ethan Bolker's formula $n - 4 \lfloor n/4 \rfloor,$ which is inspired by modular arithmetic but actually uses only ordinary integer arithmetic with the greatest-integer function. That answer gets my vote.

---

Example 4

I have added this example after seeing that the accepted answer uses a curly bracket with multiple cases ($n$ odd and $n$ even) on the right-hand side of the equation. If two cases are OK, why not four? That is, $$ f(n) = \begin{cases} 0 \quad & n = 4k, k \in \mathbb Z \\ 1 & n = 4k+1, k \in \mathbb Z \\ 2 & n = 4k+2, k \in \mathbb Z \\ 3 & n = 4k+3, k \in \mathbb Z \\ \end{cases} $$

Answer 4

For integer values of $x$ this: $J\left(x\right)=1-\left(\sin \left(\frac{\pi }{4}\cdot 2\cdot x\right)+\cos \left(\frac{\pi }{4}\cdot 2\cdot x\right)\right)+\frac{\left(1-\left(-1\right)^x\right)}{2}$ works.

Answer 5

Here is an answer involving only $+,-,\times,\div$ and exponentiation and using complex numbers. It is based upon the $r$-th roots of unity $\exp\left(\frac{2\pi ij}{r}\right), 0\leq j<r$.

Recall the following holds true for natural numbers $n,r>0$. \begin{align*} \frac{1}{r}\sum_{j=0}^{r-1}\exp\left(\frac{2\pi ij n}{r}\right)= \begin{cases} 1&\qquad r\mid n\\ 0& \qquad otherwise \end{cases} \end{align*}

Since the sequence \begin{align*} (0,1,2,3,0,1,2,3,0,1,2,\ldots)\tag{1} \end{align*} has period $4$ we set $r=4$ and consider the sequence \begin{align*} \left(\frac{1}{4}\sum_{j=0}^3\exp\left(\frac{2\pi ijn}{4}\right)\right)_{n\geq 0}=(1,0,0,0,1,0,0,0,1,0,0,\ldots) \end{align*} which has a $1$ at each $4$-th position and $0$ otherwise.

We use this sequence as basic building block to generate the wanted sequence (1).

We obtain \begin{align*} \color{blue}{(0,1,}&\color{blue}{2,3,0,1,2,3,0,1,2,0,1,2,3\ldots)}\\ &=(0,1,0,0,0,1,0,0,0,1,0,0,\ldots)\\ &\qquad+2(0,0,1,0,0,0,1,0,0,0,1,0,\ldots)\\ &\qquad+3(0,0,0,1,0,0,0,1,0,0,0,1,\ldots)\\ &=\left(\frac{1}{4}\sum_{j=0}^3\exp\left(\frac{2\pi ij(n-1)}{4}\right)\right)_{n\geq 0} +2\left(\frac{1}{4}\sum_{j=0}^3\exp\left(\frac{2\pi ij(n-2)}{4}\right)\right)_{n\geq 0}\\ &\qquad+3\left(\frac{1}{4}\sum_{j=0}^3\exp\left(\frac{2\pi ij(n-3)}{4}\right)\right)_{n\geq 0}\\ &=\left(\frac{1}{4}\left[1+\exp\left(\frac{2\pi i(n-1)}{4}\right)+\exp\left(\frac{4\pi i(n-1)}{4}\right)+\exp\left(\frac{6\pi i(n-1)}{4}\right)\right]\right.\\ &\quad+\frac{1}{2}\left[1+\exp\left(\frac{2\pi i(n-2)}{4}\right)+\exp\left(\frac{4\pi i(n-2)}{4}\right)+\exp\left(\frac{6\pi i(n-2)}{4}\right)\right]\\ &\quad+\left.\frac{3}{4}\left[1+\exp\left(\frac{2\pi i(n-3)}{4}\right)+\exp\left(\frac{4\pi i(n-3)}{4}\right)+\exp\left(\frac{6\pi i(n-3)}{4}\right)\right]\right)_{n\geq 0}\\ &=\left(\frac{1}{4}\left[1+i^n(-i)+(-1)^n(-1)+(-i)^n\cdot i\right]\right.\\ &\quad+\frac{1}{2}\left[1+i^n(-1)+(-1)^n\cdot 1+(-i)^n(-1)\right]\\ &\quad+\left.\frac{3}{4}\left[1+i^n\cdot i+(-1)^n(-1)+(-i)^n(-i)\right]\right)_{n\geq 0}\\ &=\left(\left(\frac{1}{4}+\frac{1}{2}+\frac{3}{4}\right)+i^n\left(-\frac{1}{4}i-\frac{1}{2}+\frac{3}{4}i\right)\right.\\ &\qquad\left.+(-1)^n\left(-\frac{1}{4}+\frac{1}{2}-\frac{3}{4}\right)+(-i)^n\left(\frac{1}{4}i-\frac{1}{2}-\frac{3}{4}i\right)\right)_{n\geq 0}\\ &\color{blue}{=\left(\frac{3-(-1)^n}{2}-i^n\cdot\frac{1+(-1)^n}{2}+i^{n+1}\cdot\frac{1-(-1)^n}{2}\right)_{n\geq 0}} \end{align*}

Note: Some instructive examples can be found in H.S. Wilf's book generatingfunctionology, (2.4.5) to (2.4.9).