I'm trying to solve this problem from Skiena book, "Algorithm design manual".
I don't know the answer but it seems like the entity on the R.H.S is the summation for series $1+2+3+..$. However the sequence on left hand side is squared series and seems to me of the form:
$-3-7-11-15\ldots $
I feel like its of the closed form:
$\sum(-4i+1)$
So how do I prove that the equality is right?
The following proof might be longer than necessary, but it illustrates a general method that is useful for many similar problems.
Let $$A(k) = 1^2 - 2^2 + 3^2 - 4^2 + \ldots + (-1)^{k-1} k^2$$ and $$B(k)=(-1)^{k-1} \cdot \frac{k(k+1)}2.$$ It suffices to prove that $A(0)=B(0)$ and $$A(k)-A(k-1)=B(k)-B(k-1)$$ for all $k\ge1$.
It is clear that $A(0)=B(0)=0$.
$$\begin{align*} A(k) - A(k-1) &= (-1)^{k-1} k^2 \\ B(k) - B(k-1) &= (-1)^{k-1} \cdot \frac{k(k+1)}2 - (-1)^{k-2} \cdot \frac{(k-1)k}2 \\ &= (-1)^{k-1} \left(\frac{k(k+1)}2 + \frac{(k-1)k}2 \right) \\ &= (-1)^{k-1} \left(\frac{k^2+k}2 + \frac{k^2-k}2 \right) \\ &= (-1)^{k-1} k^2 \end{align*} $$
To complete the proof, note that for all $k \ge 0$, $$ \begin{align*} A(k) &= A(0) + \sum_{i=1}^k (A(i) - A(i-1)) \\ &= B(0) + \sum_{i=1}^k (B(i) - B(i-1)) \\ &= B(k). \end{align*} $$
Proceed inductively. Verify that for $k=1$, $1 = 1$.
Now suppose the result holds for $n - 1$. Then
$$ 1^2 + \dots + (-1)^{n-1} n^2 = 1 + \dots + (-1)^{n-2} (n-1)^2 + (-1)^{n-1} n^2 = (-1)^n \frac{n(n-1)}{2} + (-1)^{n-1} n^2 = (-1)^n \left(\frac{n(n-1)-2n^2}{2} \right) = (-1)^n \left(\frac{-n^2-n}{2} \right) = (-1)^{n-1} \left(\frac{n(n+1)}{2}\right)$$
The induction hypothesis was applied at the second equality.
Hint: In order to show \begin{align*} \sum_{j=0}^k(-1)^{j-1}j^2=(-1)^{k-1}\frac{k(k+1)}{2}\qquad\qquad k\geq 0\tag{1} \end{align*} we consider sequences $(a_k)_{k\geq 0}$ and the corresponding generating functions $\sum_{k=0}^{\infty}a_kx^k$ as building blocks to generate the left hand sum in (1). This enables us to calculate the right hand side of (1). \begin{array}{crl} (a_k)_{k\geq 0}\qquad &\qquad A(x)=&\sum_{k=0}^{\infty}a_kx^k\\ \hline\\ ((-1)^{k-1})_{k\geq 0}\qquad&\qquad -\frac{1}{1+x}=&\sum_{k=0}^{\infty}(-1)^{k-1}x^k\\ ((-1)^{k-1} k)_{k\geq 0}\qquad&\qquad -\left(x\frac{d}{dx}\right)\frac{1}{1+x} =&\frac{x}{(1+x)^2}\\ &=&\sum_{k=0}^{\infty}(-1)^{k-1}kx^k\\ ((-1)^{k-1} k^2)_{k\geq 0}\qquad&\qquad -\left(x\frac{d}{dx}\right)^2\frac{1}{1+x} =&\frac{x(1-x)}{(1+x)^3}\\ &=&\sum_{k=0}^{\infty}(-1)^{k-1}k^2x^k\\ (\sum_{j=0}^{k}(-1)^{j-1} j^2)_{k\geq 0}\qquad&\qquad -\frac{1}{1-x}\left(x\frac{d}{dx}\right)^2\frac{1}{1+x} =&\frac{x}{(1+x)^3}\\ &=&\sum_{k=0}^{\infty}\left(\sum_{j=0}^{k}(-1)^{j-1}j^2\right)x^k\tag{2}\\ \end{array}
We can see in the small intro above the operator $x\frac{d}{dx}$ transforms $a_k$ to $ka_k$ and the multiplication with $\frac{1}{1-x}$ acts as summation operator.
It is also convenient to use the coefficient of operator $[x^n]$ to denote the coefficient of $x^n$ in a generating series.
We obtain from (2) for $k\geq 1$
\begin{align*} \sum_{j=0}^{k}(-1)^{j-1}j^2&=[x^k] \frac{-1}{1-x}\left(x\frac{d}{dx}\right)^2\frac{1}{1+x}\\ &=[x^k] \frac{x}{(1+x)^3}\\ &=[x^{k-1}]\sum_{n=0}^{\infty}\binom{-3}{n}x^{n}\tag{3}\\ &=\binom{-3}{k-1}\\ &=(-1)^{k-1}\binom{k+1}{2}\tag{4}\\ &=(-1)^{k-1}\frac{k(k+1)}{2} \end{align*}
Comment:
In (3) we use the binomial series representation.
In (4) we use the formula $\binom{-n}{k}=\binom{n+k-1}{k}(-1)^k$ for binomial coefficients.
Hint: Distinguish the cases where $n$ is odd or even and use that $-4i+1=(-2i)+(-2i+1)$
i) $k=2n$: \begin{align} \sum_{m=1}^{2n}(-1)^{m-1}m^2&=\sum_{m=1}^{2n}m^2-2\sum_{m=1}^{n}(2m)^2\\ &=\sum_{m=1}^{2n}m^2-8\sum_{m=1}^{n}m^2\\ &=\frac{2n(2n+1)(4n+1)}{6}-8\frac{n(n+1)(2n+1)}{6}\\ &=\frac{2n(2n+1)(4n+1-4n-4)}{6}\\ &=\frac{2n(2n+1)(-1)}{2}=-\frac{k(k+1)}{2}=(-1)^{k-1}\frac{k(k+1)}{2} \end{align} ii)$k=2n+1$: \begin{align} \sum_{m=1}^{2n+1}(-1)^{m-1}m^2&=(2n+1)^2+\sum_{m=1}^{2n}(-1)^{m-1}m^2\\ &=(2n+1)^2+\frac{2n(2n+1)(-1)}{2}\\ &=\frac{(2n+1)(4n+2-2n)}{2}=\frac{k(k+1)}{2}=(-1)^{k-1}\frac{k(k+1)}{2} \end{align}
It can be easily shown that the series on the left reduces to the sum of integers, multiplied by $-1$ if $k$ is even.
For even $k$: $$\begin{align} &1^2-2^2+3^3-4^2+\cdots+(k-1)^2-k^2\\ &=(1-2)(1+2)+(3-4)(3+4)+\cdots +(\overline{k-1}-k)(\overline{k-1}+k)\\ &=-(1+2+3+4+\cdots+\overline{k-1}+k)\\ &=-\frac {k(k+1)}2\end{align}$$
Similar, for odd $k$, $$\begin{align} &1^2-2^2+3^3-4^2+5^2+\cdots-(k-1)^2+k^2\\ &=1+(-2+3)(2+3)+(-4+5)(4+5)+\cdots +(-\overline{k-1}+k)(\overline{k-1}+k)\\ &=1+2+3+4+\cdots+\overline{k-1}+k\\ &=\frac {k(k+1)}2\end{align}$$
Hence, $$1^2-2^2+3^3-4^2+5^2+\cdots+(-1)^{k-1}k^2=(-1)^{k-1}\frac {k(k+1)}2\quad\blacksquare$$
No one's pointing out my favorite result that $n^2$ is the sum of the first odd numbers?
$(n + 1)^2 - n^2 = (n^2 + 2n + 1) - n^2 = 2n + 1$.
and the result follows...
Case 1: $k=2m$ is even.
$1 - 2^2 + 3^2 - 4^2 + .... + (k-1)^2 - (k)^2 = -(2^2 -1) - (4^2 - 3^2) - ...- (k^2 - (k-1)^2)=$
$-(3) - (-7)-....-(2k + 1) = \sum_{j = 1}^m-(4j + 1)=$
$-4(\sum_{j=1}^m j) + m(\sum_{j=1}^m j)=$
$-4(\frac{(m(m+1)}{2}) + (m) = -2m(m+1) + m = m(-2(m+1) + 1) = m(-2m - 1) =$
$ -m(2m + 1)= -\frac{k(k + 1)}{2}$
Case 2: $k = 2m + 1$ is odd.
$[1 - 2^2 + 3^2 - 4^2 + .... + (k-2^2 - (k-1)^2 ] + k^2 =$
$ -\frac{(k-1)k}{2} + (k^2) = k[-\frac{k-1}{2} + k] =$
$k[\frac{-(k-1)+2k}{2} ]=\frac{k(k + 1)}{2}$
So
sum = $(-1)^{k-1}\frac{k(k + 1)}{2}$
