How do I solve the following recurrence?

Question

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!

Answer 1

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}$$

Answer 2

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 :)