I want to know how to compute $H(n) = H(n-5) + \frac{n}5$

I know how to solve the recurrence relations whose difference between LFS and RFS is 1 (ex. $H(n) = H(n-1) + n$) but I have no idea how to solve the relation above.

Can anyone please help me?

Thanks in advance

  • 2
    $\begingroup$ What are the first $5$ values of the sequence? $\endgroup$ – rubik Feb 3 '15 at 9:59
  • $\begingroup$ The only thing given is H(1)=1 $\endgroup$ – Mansumen Feb 3 '15 at 10:04

It should be obvious that $H(5n)=H(0)+\dfrac{n(n+1)}{2}$.

Other cases are similar: $H(5n+k)=H(k)+\dfrac{n(n+1)}{2}+\dfrac{nk}{5}$ and all you need are the starting values


What you have here are 5 independent versions of the $H(n) = H(n-1) + n$ that you know how to solve. You will need 5 'initial conditions' e.g. H(0), H(1), H(2), H(3), H(4), to fully determine the solution.

e.g. If you know $H(0)$, then $H(5) = H(0) +1, H(10) = H(5) +2, \dots$

This looks just like: $H(1) = H(0) +1, H(2) = H(1) +2, \dots$

And you know how to solve $H(n) = H(n-1) +n$.


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.