Recurrence relation!

Question

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

Answer 1

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

Answer 2

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