HiveBrain v1.2.0
Get Started
← Back to all entries
patternMinor

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

Submitted by: @import:stackexchange-cs··
0
Viewed 0 times
recurrencestackoverflowprogramming

Problem

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?

Solution

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.

Context

StackExchange Computer Science Q#144346, answer score: 3

Revisions (0)

No revisions yet.