How Do You Solve the Series with Binomial Coefficients from POTW #106?

[anemone]

This week's problem was submitted by Pranav and we truly appreciate his taking the time to propose a quality problem for us to use as our Secondary School/High School POTW.:)

Evaluate the following sum:

$$ \frac{\binom{40}{2}}{3}+ \frac{\binom{40}{5}}{6}+ \frac{\binom{40}{8}}{9}+\cdots + \frac{\binom{40}{38}}{39}$$

--------------------
Remember to read the http://www.mathhelpboards.com/showthread.php?772-Problem-of-the-Week-%28POTW%29-Procedure-and-Guidelines to find out how to http://www.mathhelpboards.com/forms.php?do=form&fid=2!

 

[anemone]

Re: Problem of the week #106 -April 7th, 2014

Congratulations to magneto for his correct solution!

Solution from magneto:

Spoiler

$(i)$: $\binom{n}{k} = \frac{n}{k}\binom{n-1}{k-1}$.

$(ii)$: For $n \geq 0$, $\sum_{k\geq 0} \binom{n}{3k} = \frac{2^n + m}{3}$, where
$m = 2,1,-1,-2,-1,1$ when $n$ is congruent to $0,1,2,3,4,5 \pmod{6}$ respectively.
$41 \equiv 5 \pmod{6}$.

Then:
\begin{align*}
\sum_k \frac{1}{3k} \binom{40}{3k-1} &= \frac{1}{41} \sum_k \frac{41}{3k} \binom{40}{3k-1} \\
&= \frac{1}{41} \sum_{k > 0} \binom{41}{3k} \\
&= \frac{1}{41} \left(\frac{2^{41} + 1}{3} - 1 \right) \\
&= 17,878,237,850.
\end{align*}

Since last week's problem was submitted by Pranav, I would also include his suggested solution here and thank you again Pranav for your suggested problem:

Spoiler

Consider the following expansion:
$$(1+x)^{40}=\binom{40}{0}+\binom{40}{1}x+\binom{40}{2}x^2+\binom{40}{3}x^3+\cdots +\binom{40}{40}x^{41}\,\,\,\,\, (*)$$

Integrate both the sides of $(*)$ wrt $x$ under the limits $0$ to $1$ to obtain:

$$\frac{2^{41}-1}{41}=\binom{40}{0}+\frac{\binom{40}{1}}{2}+ \frac {\binom{40}{2}}{3}+\frac{\binom{40}{3}}{4}+\cdots +\frac{\binom{40}{40}}{41}\,\,\,\,\,\, (**)$$

Similarly, integrate both sides of $(*)$ wrt $x$ under the limits $0$ to $\omega$ and from $0$ to $\omega^2$ where $\omega$ and $\omega^2$ are non-real cube roots of unity, to obtain the following two sums:

$$\frac{(1+\omega)^{41}-1}{41}=\binom{40}{0}\omega+\frac{\binom{40}{1}}{2}\omega^2+ \frac {\binom{40}{2}}{3}+\frac{\binom{40}{3}}{4}\omega+ \cdots +\frac{\binom{40}{40}}{41}\omega^2 \,\,\,\,\,\, (***)$$

$$\frac{(1+\omega^2)^{41}-1}{41}=\binom{40}{0}\omega^2+\frac{\binom{40}{1}}{2}\omega+ \frac {\binom{40}{2}}{3}+\frac{\binom{40}{3}}{4}\omega^2+ \cdots +\frac{\binom{40}{40}}{41}\omega \,\,\,\,\,\, (****)$$

Let the sum asked in the problem statement be $S$, then adding $(**),(***)$ and $(****)$, we get:

$$\frac{2^{41}-1}{41}+\frac{(1+\omega)^{41}-1}{41}+\frac{(1+\omega^2)^{41}-1}{41}=3S\,\,\,\,\,\,\,(\because 1+\omega+\omega^2=0)$$
$$\Rightarrow S=\frac{2^{41}-3+(1+\omega)^{41}+(1+\omega^2)^{41}}{123}$$
Use the fact that $1+\omega=-\omega^2$ and $1+\omega^2=-\omega$ to get the following:
$$S=\frac{2^{41}-3-\omega^{41}-\omega^{82}}{123}=\frac{2^{41}-3-\omega-\omega^{2}}{123}$$
$$\Rightarrow \boxed{S=\dfrac{2(2^{40}-1)}{123}}$$