Recurrence relation!

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

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

2 Answers

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