Summation

Problem 5.1.13

Prove that

$$ \begin{align*} \sum_{k=0}^n\left[\frac{n-2k}{n}{n \choose k}^2 \right] = \frac{2}{n}{2n-2 \choose n-1} \end{align*} $$

Solution

We have

$$ \begin{align} {n \choose 0}^2 + {n \choose 1}^2 + {n \choose 2}^2 + \cdots + {n \choose n}^2 \nonumber \\ = {2n \choose n} \label{eqbinid1} \\
{r \choose 0}{s \choose n} + {r \choose 1}{s \choose n+1}+ \cdots + {r \choose n}{s \choose n+n} \nonumber\\
= {r+s \choose s-n} \label{eqbinid2} \end{align} $$

Using $\ref{eqbinid1}$ and setting $r=n-1$, $s=n$ and $n=1$ in $\ref{eqbinid2}$, we have

$$ \begin{align*} \sum_{k=0}^n\left[\frac{n-2k}{n}{n \choose k} \right]^2 & = \sum_{k=0}^n \left( {n \choose k}^2 + \frac{4k^2}{n^2}{n \choose k}^2 - \frac{4k}{n}{n \choose k}^2 \right)\
&= {2n \choose n} + 4\sum_{k=1}^n {n-1 \choose k-1}^2 - 4\sum_{k=1}^n {n-1 \choose k-1}{n \choose k} \
&= {2n \choose n} + 4{2n-2 \choose n-1} - 4{2n-1 \choose n-1} \
&= \frac{(2n-2)!}{n!(n+1)!} \left(2n(2n-1)(n+1) \ + 4n^2(n+1) -4(2n-1)n(n+1) \right) \
&= \frac{(2n-2)!}{n!(n+1)!}2n(n+1) = \frac{2}{n}{2n-2 \choose n-1} \end{align*} $$

Problem 5.2.8

Sum the series $1+22+333+\cdots+n(\underbrace{11\dots1}_n)$.

Solution

We have

$$ \begin{align*} S &= 1+22+333+\dots+n(\underbrace{11\dots1}_n) \
&= \frac{1}{9}{9 + 2\cdot99 + \dots + n(\underbrace{99\dots9}_n) }\
&= \frac{1}{9}{10 - 1 + 2(10^2-1) + \dots + n(10^n-1)} \
&= \frac{1}{9}\left(\frac{n10^{n+2}-(n+1)10^{n+1}+10}{81} - \frac{n(n+1)}{2}\right) \end{align*} $$

Problem 5.4.12

Let $p$ and $q$ be real numbers with $1/p - 1/q=1, 0<p\leq \frac{1}{2}$. Show that

$$ \begin{align*} p + \frac{1}{2}p^2 + \frac{1}{3}p^3 + \cdots = q - \frac{1}{2}q^2 - \frac{1}{3}q^3 + \cdots. \end{align*} $$

Solution

We have

$$ \begin{align*} \frac{1}{p} - \frac{1}{q} = 1 \implies p = \frac{q}{1+q} \end{align*} $$

Differentiating the above, we have

$$ \begin{align*} -\frac{dp}{p^2} + \frac{dq}{q^2} = 0 \implies dp = \frac{1}{(1+q)^2}dq \end{align*} $$

We also have

$$ \begin{align*} \int \frac{1}{1-p} dp = \int \frac{1}{1-\frac{q}{1+q}} \frac{1}{(1+q)^2}dq = \int \frac{1}{1+q}dq \end{align*} $$

Integrating the series expansions on both sides, we have

$$ \begin{align*} \int 1+p+p^2+\cdots dp &= \int 1-q+q^2-q^3+\cdots dq\
\implies p + \frac{1}{2}p^2 + \frac{1}{3}p^3 + \cdots &= q - \frac{1}{2}q^2 - \frac{1}{3}q^3 + \cdots
\end{align*} $$