Binomial sum

General Mathematics
Post Reply
User avatar
Tolaso J Kos
Administrator
Administrator
Posts: 867
Joined: Sat Nov 07, 2015 6:12 pm
Location: Larisa
Contact:

Binomial sum

#1

Post by Tolaso J Kos »

Let $n \in \mathbb{N}$. Evaluate (in a closed form) the following sums:

$$\begin{matrix}
{\text (a)} \; \displaystyle \sum_{k=0}^{n}\binom{2n}{2k}&&&&&&& \text{(b)} \; \displaystyle \sum_{k=0}^{n}\binom{3n}{3k}

\end{matrix}$$
Imagination is much more important than knowledge.
User avatar
Riemann
Posts: 176
Joined: Sat Nov 14, 2015 6:32 am
Location: Melbourne, Australia

Re: Binomial sum

#2

Post by Riemann »

For the second sum let $\omega=e^{2\pi i /3}$ be a third root of unity. The binomial expansion tells us

$$\left ( 1+x \right )^n = \sum_{k=0}^{n}\binom{n}{k}x^n$$

Subbing $x$ with $1, \omega, \omega^2$ respectively at the binomial expansion we get:

$$\begin{matrix}
\displaystyle \sum_{k=0}^{n}\binom{n}{k}=2^n & , &\displaystyle \left ( 1+\omega \right )^n =\sum_{k=0}^{n}\binom{n}{k}\omega^n &, &\displaystyle \left ( 1+\omega^2 \right )^n = \sum_{k=0}^{n} \binom{n}{k}\omega^{2k}
\end{matrix}$$

Adding the above three equations together we get that:

$$\sum_{k=0}^{n}\binom{n}{k}\left [ 1+\omega^k +\omega^{2k} \right ]=2^n + \left ( 1+\omega \right )^n + \left ( 1+\omega^2 \right )^n $$

We note that $1+\omega^k +\omega^{2k}=3$ when $k$ is divisible by $3$ and $0$ othewise. Hence:

$$\sum_{m=0}^{\left \lfloor n/3 \right \rfloor}\binom{n}{3m}= \frac{1}{3}\left [ 2^n + \left ( 1+\omega \right )^n+ \left ( 1+\omega^2 \right )^n \right ]$$

Subbing $n$ with $3n$ and doing the calculations we finally get that:

$$\sum_{k=0}^{n}\binom{3n}{3k}= \frac{1}{3}\left [ 8^n + 2(-1)^n \right ]$$

The first sum is much easier and I leave it to someone else. :)
$\displaystyle \sum_{n=1}^{\infty}\frac{1}{n^s}= \prod_{p \; \text{prime}}\frac{1}{1-p^{-s}}$
Post Reply

Create an account or sign in to join the discussion

You need to be a member in order to post a reply

Create an account

Not a member? register to join our community
Members can start their own topics & subscribe to topics
It’s free and only takes a minute

Register

Sign in

Who is online

Users browsing this forum: No registered users and 10 guests