# Recursive to non recursive function

$$f(x) = \begin{cases} 0 & x=1 \\ f(x-1)+1 & \frac{f(x-1)}{x-1} < p \\ f(x-1) & \text{otherwise} \\ \end{cases}$$ Where $p$ is a constant less that or equal to 1. And x is a whole number greater than 0.

How do I get a non recursive solution for $f(x)$?

• Have you tried picking a value of $p$, calculating $f$ for $x$ in some range, then looking for a pattern in the result, trying to generalize, trying to prove the pattern persists? – Gerry Myerson Jun 14 '16 at 9:23
• I know that the patters approaches to $$f(x)=x*p$$ for p<=1 – Nithin Mohan Jun 14 '16 at 9:26
• sorry for that. I redefined the function. – Nithin Mohan Jun 14 '16 at 9:30
• Well, if you know that, then you have the answer to your question, don't you? You have a non-recursive formula for $f$. – Gerry Myerson Jun 14 '16 at 9:32
• I needed an exact one. I need to find in which case an x takes of the three. Should I reformulate the question? – Nithin Mohan Jun 14 '16 at 9:37

To make Nithin's answer more precise, we have $$f(x) = \begin{cases} \left\lceil (x-1) p \right\rceil & \text{ if } p \leq 1 \\ x - 1 & \text{ if } p > 1 \end{cases}$$
You can easily prove that by induction on $x$:
• If $x = 1$, then $f(x) = 0 = x-1 = \left\lceil (x-1)p \right\rceil$.
• If $p > 1$ and $f(x-1) = x - 2$, then we have $\frac{f(x-1)}{x-1} < p$, so we have $f(x) = x-2 + 1 = x-1$.
• If $p \leq 1$ and $f(x-1) = \left\lceil(x-2)p\right\rceil$, then there are two cases:
• If $\frac{f(x-1)}{x-1} < p$, then we have $\left\lceil(x-2)p\right\rceil < (x-1)p$. Thus we have $f(x) = f(x-1)+1 = \left\lceil(x-1)p\right\rceil$.
• Otherwise, we have $\left\lceil(x-2)p\right\rceil < (x-1)p$. So we have $f(x) = f(x-1) = \left\lceil(x-1)p\right\rceil$.