# Recursive function activity

We had the following question on an activity for our students:

Let $f_0(x)=x+|x-100|-|x+100|$, and for $n\geq 1$, let $f_n(x)=|f_{n-1}(x)|-1$. For how many values of $x$ is $f_{100}(x)=0$?

When I got home, I tried what is probably a pretty silly attempt:

Subscript[f, 0][x_] = x + Abs[100 - x] - Abs[x + 100];
sol = Nest[Abs[#] - 1 &, Subscript[f, 0][x], 100];
Solve[sol==0,x,Reals]


But things just locked up and I had to quit the kernel.

Any suggestions on how to attack this problem? The correct answer is 301.

I would define your recursion as follows:

f[0] = x + Abs[x - 100] - Abs[x + 100];
f[n_] := Abs[f[n - 1]] - 1


You can then plot the value of f[100]; you will notice that it is bounded between $-300\le x\le 300$, but it grows linearly outside those boundaries:

Plot[f[100], {x, 250, 320}]
Plot[f[100], {x, -320, -250}]


The plot suggests that the $f(100) = 0$ for all even values of $-300\le x\le 300$, which leads to the 301 values you suggested, i.e. 150 values each for $x<0$ and $x>0$, plus $x=0$ itself.

• Nice. Very helpful, again a learn a lot thanks to your help. Oct 10 '15 at 19:32

I post this just for insight into this iterative map.

f[x_, n_] := Nest[Abs@# - 1 &, x, n]
func[n_] := Reduce[-n <= g[x, n] <= n, x]
g[x_, m_] := x + Abs[x - m] - Abs[x + m]
h[x_, n_] := f[g[x, n], n]


The insight into the behaviour can be obtained looking at f.

Manipulate[
Plot[{x, -x, g[x, r], f[x, r]}, {x, -3 r, 3 r},
PlotStyle -> {{Blue, Dashed}, {Blue, Dashed}, Red, Green},
Frame -> True, AspectRatio -> Automatic,
GridLines -> {{-r, r}, {-r, r}}, PlotLegends -> "Expressions"], {r,
Range[10]}]


This shows that for starting values $-r\le x_0\le r$ then $-1\le f[x_0,r]\le 0$

So,

Manipulate[
Column[{Plot[h[x, r], {x, -4 r, 4 r},
Epilog -> {Red, PointSize[0.02],
Point@Table[{j, 0}, {j, -3 r, 3 r, 2}]}],
Length[Range[-3 r, 3 r, 2]],
func[r]}
],
{r, {2, 3, 4, 5, 6, 7, 10, 20, 50, 100}}]


Hence, yielding 301 for r=100. Note for odd values of r, the zeros are odd integers between -3 r and 3 r (inclusive) and for even values of r (such 100) it is even integers between -3r and 3 r inclusive.