help deriving a closed formula for this "magic function" I'm having trouble coming up with a closed formula for $n$ from the sequence of numbers generated by this function:
The following mystery function $M : N \times N \rightarrow N $ is defined by:
$$
M(m,n) = 
\begin{cases}
m & n < 2m +1 \\
M(m+1, n-2m-1) &n \ge 2m + 1
\end{cases}
$$
If that looks confusing here's an  algorithm representing the logic:
int M(int m, int n)
{
    if (n < 2*m + 1)
        return m;
    else
        M(m + 1, n - 2*m - 1);
}

Here's what I have to do:


*

*Evaluate $M(0,n)$ for $n \in \{0,...,10\}$.


*

*$n = 0$ : $M(0,0) = 0$

*$n = 1$ : $M(0,1) = 2$

*...

*I evaluated each $n$ from $0$ to $10$ on paper, and the sequence I got is: $0,1,1,1,2,2,2,2,2,3,3$  I verified this output by running my algorithm in C.


*Provide a closed formula for $M(0,n)$


*

*This is where I'm lost.  I know what a closed formula is.  It's a formula to find the value of $M(0,n)$ with $n$ in the formula... I ran my program again, but this time from n = 0 to 100, and see a pattern of 0, three 1's, five 2's, seven 3's, nine 4's... and so on...  But I don't see how to tie this to n.  I think I've been up too late.  Any help/insight is appreciated!


 A: Take a look at what happens when you apply this procedure to $M(0,n)$. Then see whether you can identify a pattern.
To simplify things, let's first assume that $n$ is large enough so that we are always in the case that $n \geq m$. That gives us the following:
$$
M(0,n)=M(1,n-1)=M(2,n-4)=M(3,n-9)=M(4,n-16)=M(5,n-25)
$$
Do these numbers $1,4,9,16,25,\dots$ satisfy a pattern? 
Looking at the above, for which values of $n$ do we get the answers $0,1,2,3,4,\dots$? For example, we stop at the stage $M(3,n-9)$ if 


*

*We did not stop at the previous stage, so $n-4 \geq 2(2)+1=5$ or $n \geq 9$

*We do stop at this stage, so $n-9< 2(3)+1=7$ or $n<16$.


So we stop at this stage if $9 \leq n < 16$, and in this case we output $3$.
This approach yields the following:
$$
\begin{array}{c|c}
M(0,n) & n \\ \hline
0 & 0\leq n <1 \\
1 & 1 \leq n <4 \\
2 & 4 \leq n <9\\
3 & 9 \leq n< 16\\
4 & 16 \leq n<25\\
\end{array}
$$
Do you see a way to express this a function of $n$?
(Why do the numbers $1,4,9,16,25, \dots$ appear? Take a look at this question here.)
