How do I solve the following recurrence? 
Solve the recurrence
  $$X_n =\begin{cases} n & 0 \leq n < m\\
X_{n-m} + 1 & n \geq m.\end{cases}$$

So I've started with several base cases, but since the answer depends on $n$'s relation to $m$, doesn't that mean my base cases have to propose both an $n$ value and an $m$ value?
I know the answer is $$\left\lfloor\frac{n}{m}\right\rfloor+(n\bmod m),$$
But I don't know how to get to the answer.
I'm having a really hard time marrying the recurrence material to the floor/ceiling material to the modular arithmetic material.
Sorry about the formatting, but if anyone can help, I would really appreciate it!
 A: Hint: Check, that your answer is equivalent to:
$$n+\left\lfloor\frac{n}{m}\right\rfloor(1-m)$$

Then use induction:


*

*If $n<m$, then $X_n=n$ and 
$$n+\left\lfloor\frac{n}{m}\right\rfloor(1-m)=n+0(1-m)=n$$

*If $n\geq m$, then apply the induction hypothesis:
$$\begin{align}X_n
&=X_{n-m}+1 \\
&=\left(n-m+\left\lfloor\frac{n-m}{m}\right\rfloor(1-m)\right)+1 \\
&=n-m+\left(\left\lfloor\frac{n}{m}\right\rfloor-1\right)(1-m)+1 \\
&=n-m+\left\lfloor\frac{n}{m}\right\rfloor(1-m)-(1-m)+1 \\
&=n+\left\lfloor\frac{n}{m}\right\rfloor(1-m)
\end{align}$$

A: let n = 3. Let m = 10.
$X_{n} = X_{10-3} + 1 = X_{7-3} + 1 + 1 = X_{5-3} + 1 + 2 = X_{2} + 3 = 2+3 = 5$
$\left\lfloor\frac{10}{3}\right\rfloor+(10\mod 3) = 3 + 1 = 4 \neq 5$ ?
Are you sure, that you don't mean $\left\lceil\frac{n}{m}\right\rceil$?
Get there just by proving your formula for $n<m$ then $n≥m$. The second part might be more difficult, try to calculate like in my example but with using your variables. Maybe there is no close formula for your recursion.
--edit
ah cool, the answer before me did all the calculus work, looks good :)
