Good idea to look at differences. So you found:

,

assuming the first term is .

If you sum the above equalities for ranging from 1 to , you get a telescoping sum on the left, and a geometric sum on the right, which leads to:

,

hence

.

Summing again this latter equality we have again a telescoping sum on the left and a geometric sum (minus constant terms) on the right, and we get:

,

hence (change of variable)

and finally . Same method works in many situations.