An exercise from Knuth's book - Proving a formula by induction

Question

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.

Answer 1

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.

Answer 2

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}.$$