Generating function of recurrence relation $T(n) = T(n-1) + (n-1)$
I've been trying to get the closed form for this recurrence by using generating function, and got to the following
$$ G(x) - xG(x) - \frac{x^2}{(1-x)^2} = 1 \\ G(x) = \frac{1}{1-x} + \frac{x^2}{(1-x)^3} $$
I don't know what to do from here, any suggestions?
The hybrid relation, part recurrence relation and part formula for term $n$ is, $$T_n=T_{n-1}+n-1$$ Interestingly, because of the hybrid nature, the initial terms, $T_0$ and $T_1$ are fixed and so are not specified at the outset by the question setter because they don't need to be. I'll deduce them at the end of this answer.
Rewrite this as, $$T_n-T_{n-1}=n-1$$ or, even better, as, $$T_n-T_{n-1}=(n+1)-2$$ This is so that we can jump into the bits of the associated generating function, $GF$, $$(1-x)GF=\frac{1}{(1-x)^2}-\frac{2}{1-x}$$ This last step is because, $$\sum_{k=0}^{\infty}(k+1)x^k=\frac{1}{(1-x)^2}$$ is the generating function associated with the positive integers, $$T_n=n+1,\;n\ge0$$ and, $$\sum_{k=0}^{\infty}x^k=\frac{1}{(1-x)}$$ is the generating function associated with the unity sequence, $$T_n=1, n\ge0$$ Moving on, $$GF=\frac{1}{(1-x)^3}-\frac{2}{(1-x)^2}$$ These are standard bits (the first bit is for the triangular numbers) which translate directly into a formula for term $n$, $$T_n=\frac{(n+1)(n+2)}{2}-2(n+1), \; n\ge0$$ A tidy up gives, $$T_n=\frac{n^2-n-2}{2}, \; n\ge0$$ The sequence associated with this is, $$-1, -1, 0,2,5,9, 14, 20, 27, 35, 44, 54,\dots$$ which also, of course, satisfies the original recurrence relation with $T_0=T_1=-1$
A nice question; thanks for that.
PS
For the triangular numbers, $$\sum_{k=0}^{\infty}\frac{(k+1)(k+2)}{2} x^k=\frac{1}{(1-x)^3}$$ $$T_n=\frac{(n+1)(n+2)}{2},\; n\ge0$$