# Recursive Formula to Closed Form

I am doing some research into the movement of robots executing a given algorithm, and I came up with a recursive formula to describe the coefficient of the movement for each step. Is it even possible to convert the recursive formula to a closed-form version? As far as I've tried, I haven't been able to find a solution, though I'm not a mathematician.

where 0 < M(0) $\le$ 1

• You to know the starting value. – hamam_Abdallah Jul 12 '18 at 20:34
• You can remove the third condition, I believe. If $\exists n$ such that $M(n)=0.5$, then the sequence becomes $0.5,1,0,0,0,...$. – MalayTheDynamo Jul 12 '18 at 20:35
• Are you looking for a formula that will be valid for $0<=M(0)=x<=1?$ – saulspatz Jul 12 '18 at 20:43
• @saulspatz yes, I'm wondering if its possible. – RoryHector Jul 12 '18 at 20:48
• @saulspatz Use $\le$ for $\le$. – Shaun Jul 12 '18 at 21:32

Define the function $f: \Bbb R \to [0, 1]$ as the distance of $x$ to the nearest integer, multiplied with $2$: $$f(x) = 2 \min \{ x - \lfloor x \rfloor, \lfloor x +1\rfloor - x \} \, .$$ The function is periodic with period $1$, and on the interval $[0, 1]$ it looks like this:

This are the graphs of the iterates $f(f(x))$ and $f(f(f(x)))$:

One “sees” that $f(f(x)) = f(2x)$, $f(f(f(x))) = f(4x)$, and generally for the $n$-th iterate: $$f^{(n)} (x) = f(2^{n-1}x)$$

Therefore $$M(n) = f^{(n)}(M(0)) = f(2^{n-1}M(0)) \\ = 2 \min \{ 2^{n-1}M(0) - \lfloor 2^{n-1}M(0) \rfloor, \lfloor 2^{n-1}M(0) + 1\rfloor - 2^{n-1}M(0) \}$$ is the distance of $M(0)$ to the nearest integral multiple of $\frac{1}{2^{n-1}}$, multiplied with $2^n$.

I really doubt that this is possible. It starts to oscillate madly. I wrote a python script to test this.

Here's the script if you want to test it yourself

import matplotlib.pyplot as plt

n = 20
def M(x):
return 2*(1-x) if x > .5 else 2*x

xs = [.01*n for n in range(100)]
ys = map(M, xs)
for _ in range(n):
ys = map(M, ys)
plt.plot(xs, list(ys))
plt.show()

• It oscillates, but not madly :) With n = 6 and xs = [n/128 for n in range(128)] you'll get a better picture. – Martin R Jul 13 '18 at 5:32
• What you see is a fundamental (triangle wave) modulated by an envelope which is also a (shifted) triangle wave. But in fact, the envelope is a sampling artifact, i.e. a form of aliasing. With a correct sampling frequency, you get a pure triangular wave (See Martin R.'s answer). – Yves Daoust Jul 13 '18 at 9:07
• @MartinR Well, I'm surprised. I purposely didn't use a power of $1/2$ as the sampling interval, because I thought the function was likely to behave nicely there and badly elsewhere. I thought the experiment confirmed my mistaken intuition, and didn't look any deeper. – saulspatz Jul 13 '18 at 12:20

The transformation can be seen as a "folding". It linearly stretches $[0,\frac12]$ to $[0,1]$, then $[\frac12,1]$ to $[1,0]$. You can represent this effect by drawing a diagonal on a rectangular sheet and folding it along the horizontal median. You repeat this as many times as you want.

You can stretch vertically by a factor $2^n$ to restore the initial height.