# Defining and generalizing a recursive function applied $n$ times

First of all, I am not a mathematician so forgive me for the errors.

I am dealing with a processing pipeline that applies a reduction function, $$r(x)$$, $$n$$ times at its core, where:

$$r(x) = \lceil x/2 \rceil$$

If I am applying this function $$n = 3$$ times then, the processing pipeline function $$R_n(x)$$ would be:

$$R_3(x) = r(r(r(x)))$$

How could I generalize this expression for an arbitrary $$n$$ number of times? I am looking for:

$$R_n(x) = ¿?$$

I know this must be very simple, but I just can not generalize it. I have search over recursive functions like the Fibonacci which gave me some clues but still can not generalize it. Thanks in advance community!

• What is your goal? To obtain an explicit expression for $R_n(x)$ in terms of $x$? Commented Oct 14, 2020 at 11:43
• Yes! thank you for your interest
– JVGD
Commented Oct 14, 2020 at 14:19

The answer is simple: $$R_n(x) = \lceil \frac{x}{2^n} \rceil$$ Applying $$r$$ will halve the value, so applying it $$n$$ times will divide by $$2^n$$. The repeated roundings upwards turn out not to matter, and can just be done once at the end.
• Those upward roundings get halved by any subsequent applications of $r$, so all together the roundings never add up to more than one in the final answer, and can then be handled by just a single rounding in $R_n$. Commented Oct 14, 2020 at 14:47