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

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

score 3 · Answer 1 · answered Feb 03 '15 at 10:04

3

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

answered Feb 03 '15 at 10:04

Henry

157,058

score 2 · Answer 2 · edited Sep 05 '19 at 00:11

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

Recurrence relation!

2 Answers2