$h_n=h_{n-1} -n+3, \ (n\geq 1); \ h_0=2$

Question

Solve the following recurrence relation by examining the first few values for a formula and then prove your conjectured formula by induction

$h_n=h_{n-1} -n+3, \ (n\geq 1); \ h_0=2$

---

Here I've gone all the way to $n=8$ and the only pattern I've noticed is in the differences. By that I mean,

---

$h_0=2$

$h_1=2-1+3=4;$ $\ \ \ \ $from $h_1$ to $h_0$ there's a difference of $+2$

$h_2=4-2+3=5;$$\ \ \ \ $from $h_2$ to $h_1$ there's a difference of $+1$

$h_3=5-3+3=5;$$\ \ \ \ $from $h_3$ to $h_2$ there's a difference of $+0$

$h_4=5-4+3=4;$$\ \ \ \ $from $h_4$ to $h_3$ there's a difference of $-1$

$h_5=4-5+3=2;$$\ \ \ \ $from $h_5$ to $h_4$ there's a difference of $-2$

$h_6=2-6+3=-1;$$\ \ \ \ $from $h_6$ to $h_5$ there's a difference of $-3$

$h_7=-1-7+3=-5;$$\ \ \ \ $from $h_7$ to $h_6$ there's a difference of $-4$

$h_8=-5-8+3=-10;$$\ \ \ \ $from $h_8$ to $h_7$ there's a difference of $-5$

---

I'm not really sure what this means as far as the formula goes though

Note: I'm only struggling with coming up with the formula. I can handle the induction.

Answer 1

You noticed the pattern examining the first few values and noticed that the difference between successive terms varies as a linear function of $n$.

If you make an analogy with derivatives, this seesm to mean that the terms vary as a quadratic function of $n$.

Answer 2

You have: $h_n = (h_n - h_{n-1}) + (h_{n-1} - h_{n-2})+ ...+ (h_2 - h_1) + (h_1-h_0) + h_0 = -n+3 - (n-1) + 3 - (n-2) + 3 + ... + (-1 + 3) + 2 = -(1+2++\cdots + n) + 3n + 2 = $? Can you finish it off?

Answer 3

**Hint: **Write it in terms of $n$.$$h_n = h_{n-1}-n+3,$$ but $$h_{n-1}=h_{n-2}-(n-1)+3,$$ so $$h_n = h_{n-2}-n-(n-1)+2*3,$$ replace it now using $h_{n-2}=h_{n-3}-(n-2)+3,$ you will get $$h_n=h_{n-3}-(n-2)-(n-1)-n+3*3,$$ Do it again and again and the pattern will pop out.
So what is $h_{n-k}?$ what happens when $k=n?$