Recurrence $T(n) = T(n-1) + (-1)^nn$, $T(0) = 1$

Question

I am trying to solve the recurrence $$T(n) = T(n-1) + (-1)^nn, \quad T(0) = 1.$$

I'm stuck in the summation: \begin{align} T(n) &= T(n-1) + (-1)^n n \\ &= T(n-2) + (-1)^{n-1}(n-1) + (-1)^nn \\ &= T(n-3) + (-1)^{n-2}(n-2) + (-1)^{n-1}(n-1) + (-1)^nn \\ &= \\ &\cdots \\ &= T(n-k) + (-1)^{n-(k-1)} (n-(k-1)) + (-1)^{(n-(k-2))} (n-(k-2)) + \cdots + (-1)^nn \\ &= T(0) + \sum_{k=1}^n (-1)^k k. \end{align} How do I evaluate the sum?

Answer 1

Here are the first few values of the expression $\sum_{k=1}^n (-1)^k k$, starting with $n = 1$: $$ -1, 1, -2, 2, -3, 3, -4, 4, -5, 5,\ldots$$ Hopefully you can spot the pattern.