Recursive function activity

Question

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.

Answer 1

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.

Answer 2

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.