An exercise from Knuth's book - Proving a formula by induction I would like to find a formula for this sum:
$$
    \frac{1^3}{1^4+4} - \frac{3^3}{3^4+4} + \frac{5^3}{5^4+4} - ... + \frac{(-1)^n(2n+1)^3}{(2n+1)^4+4}
$$
The answer given (Knuth's book, The Art of Computer Programming Volume 1, Third Edition, Section 1.2.1, Exercise 11) is $$ \frac{(-1^n)(n+1)}{4(n+1)^2+1}$$
Please give me an approach or a solution to get this sum.
I tried to solve by pairing the consecutive terms. The last and the second last terms will correspond to $(2n+1)$ and $(2n-1)$ respectively. But this approach couldn't yield much.
The second part is to prove this sum by induction, i.e we've to prove this equation:
$$
    \frac{1^3}{1^4+4} - \frac{3^3}{3^4+4} + \frac{5^3}{5^4+4} - ... + \frac{(-1)^n(2n+1)^3}{(2n+1)^4+4} = \frac{(-1^n)(n+1)}{4(n+1)^2+1}
$$
I approached it like this:
The sum is correct for $k=1$( and $k=0$). (k is a non-negative integer)
Assuming that the sum is correct for $k = 0,1,..,n$
we'll prove that its correct for $k=n+1$.
The sum for $k=n+1$ will be equal to: the sum for k=n + the last term, i.e. $$ \frac{(-1)^n(n+1)}{4(n+1)^2+1} + \frac{(-1)^{n+1}(2(n+1)+1)^3}{(2(n+1)+1)^4+4}$$
This should then be proved equal to $$\frac{(-1)^{n+1}((n+1)+1)}{4((n+1)+1)^2+1}$$
which again I'm not able to do. So, please help in proving this also.

P.S.: Someone please create a 'knuth' or 'taocp' tag for mathematical questions of this book.

First you have$$ \begin{align} (2n+1)^4+4&= A^4+B^2\\\\ &=(A^4+2A^2B+B^2)-2A^2B\\\\
   &=(A^2+B)^2-2A^2B\\\\
   &=\left((2n+1)^2+2\right)^2-4\left(2n+1\right)^2\\\\
   &=\left((2n+1)^2+2-2(2n+1)\right)\left((2n+1)^2+2+2(2n+1)\right)\\\\
   &=\left(4n^2+1\right)\left(4(n+1)^2+1\right) \end{align}$$
Second you have$$ \begin{align} \frac{n}{4n^2+1}+\frac{n+1}{4(n+1)^2+1}&= \frac{n\left(4(n+1)^2+1\right)+(n+1)\left(4n^2+1\right)}{\left(4n^2+1\right)\left(4(n+1)^2+1\right)}\\\\ &=\frac{8n^3+12n^2+6n+1}{(2n+1)^4+4}\\\\
  &=\frac{(2n+1)^3}{(2n+1)^4+4}\\\\
  \end{align} $$
Now, setting $\displaystyle u_n:=\frac{(-1)^n n}{4n^2+1}$, you see from the preceding lines that $$\begin{align} u_n- u_{n+1}&=\frac{(-1)^n n}{4n^2+1}-\frac{(-1)^{n+1} (n+1)}{4(n+1)^2+1}\\\\&=(-1)^n \left(\frac{n}{4n^2+1}+\frac{n+1}{4(n+1)^2+1}\right)\\\\
&=\frac{(-1)^n(2n+1)^3}{(2n+1)^4+4}\end{align} $$
and by telescoping, you obtain what you want.
