patternMinor
Recurrence $T(n) = T(n-1) + (-1)^nn$, $T(0) = 1$
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?
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.
$$ -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.