# A question related to Hofstadter-Conway \$10000 sequence Hofstadter-Conway \$10000 sequence is defined by nested recurrence relation $$c(n) = c(c(n-1)) + c(n-c(n-1))$$ with $$c(1) = c(2) = 1$$. This sequence is https://oeis.org/A004001 and it is well-known that this sequence has many amazing properties: https://www.sciencedirect.com/science/article/pii/0012365X9400303Z

A related curious sequence can be defined by similar recurrence relation as below $$c^*(n) = n - c^*(c^*(n-1)) - c^*(n-c^*(n-1))$$ with $$c^*(1) = c^*(2) = 1$$. I introduced this sequence in https://oeis.org/A287422 and recurrence is also investigated in terms of sensitivity of initial conditions selections: https://link.springer.com/chapter/10.1007%2F978-3-030-35441-1_14

Question. Can someone show that $$c(n) - \frac{n}2$$ $$\ge$$ $$\left\lvert c^*(n) - \frac{n}2 \right\rvert$$ for all $$n \ge 1$$ ? (It is checked up to $$2^{30}$$.)

(I share below graph in order to display behaviours of both sequences for $$n \le 2^{10}$$.
Red: $$c(n) - \frac{n}2$$, Black: $$c^*(n) - \frac{n}2$$)