Recursive Formula to Closed Form

Question

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

Answer 1

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

Answer 2

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

Answer 3

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.