<s>[INST] 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.
 [/INST] You are very close.
Take two consecutive sums and subtract them (actually you will be adding as the signs alternate):
$$\frac{n+1}{4(n+1)^2+1}+\frac{n+2}{4(n+2)^2+1}=\frac{8n^3+36n^2+54n+27}{16n^4+96n^3+216n^2+216n+85}.$$
The numerator is $(2n+3)^3$, and the denominator is $(2n+3)^4+4$.

To make this derivation more symmetric and manageable, you can use a half-integer index, $m=n+3/2$:
$$\frac{2m-1}{(2m-1)^2+1}+\frac{2m+1}{(2m+1)^2+1}=
\frac{2m-1}{(4m^2+2)-4m}+\frac{2m+1}{(4m^2+2)+4m}=
\frac{16m^3}{16m^4+4}.$$
</s>