2
$\begingroup$

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!

$\endgroup$
0
3
$\begingroup$

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}$$
$\endgroup$
0
$\begingroup$

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

$\endgroup$
2
  • $\begingroup$ You've got $n$ and $m$ backwards. $X_n=X_3=3$. $\endgroup$ Jul 31 '13 at 15:03
  • $\begingroup$ damn. Great, thanks! $\endgroup$
    – swiknaba
    Jul 31 '13 at 15:07

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.