Sum of sequence of $\binom{n}{r}$ How can we find the sum of $ \binom{21}{1}+ 5\binom{21}{5}+ 9\binom{21}{9}....+17\binom{21}{17}+ 21\binom{21}{21}$?
I have no clue how to begin. I guess complex numbers might help. 
EDIT: Actually the real question was that the sum above was k and we had to find its prime factors. And the answer according to the key involves complex numbers. They have directly written that:
$k=\frac{21( 2^{20} + 0^{20} + (1+i)^{20} + (1-i)^{20})}{4} = 21(2^{18}-2^9)$
I didn't get the above.
 A: As the OP is asking for a complex number approach, another method :
$(1+x)^{21}=\sum\limits_{k=0}^{21} \binom{21}{k}x^{k}$
Differentiate to get : $21(1+x)^{20}=\sum\limits_{k=0}^{21}k \binom{21}{k}x^{k-1}$
Now plug in $x=1,-1,i,-i $
$\text{ where } i =\sqrt{-1}$
and add the four equations to arrive at your required sum.
A: For any $k$:
$$k {n \choose k}=k\frac{n!}{k!(n-k)!}=\frac{n!}{(k-1)!(n-k)!}=n {n-1 \choose k-1}$$
So $$\sum_{k=1}^{n}k{n \choose k}=n\sum_{k=1}^{n}{n-1 \choose k-1}=n2^{n-1}$$
EDIT: undeleted as refered, this answer is however not relevant.
A: You have $\sum_{k=0}^{5}{21 \choose 4k+1}\cdot (4k+1)=21\sum_{k=0}^{5}{20 \choose 4k}$.
From here it's easier...
A: Your sum is $$S=\sum_{k=0}^m(4k+1)\binom{n}{1+4k}$$ with $n=21, m=5$. To find this sum we proceed as below $$(1+x)^n=\sum_{k=0}^n \binom{n}{k}x^k\\ \implies n(1+x)^{n-1}=\sum_{k=0}^n k\binom{n}{k}x^{k-1}$$ Let $\alpha=e^{j2\pi/r}$ be the $r$th root of unity. Then,  $$n(1+\alpha^s)^{n-1}=\sum_{k=0}^n k\binom{n}{k}\alpha^{s(k-1)},\quad\ s=0,1,\cdots,\ r-1$$ Adding these $r$ equations we will get $$n\sum_{s=0}^{r-1}(1+\alpha^s)^{n-1}=r\sum_{0\le k\le n: r|k}k\binom{n}{k}\\ \implies =\sum_{0\le k\le n: r|k}k\binom{n}{k}=\frac{n}{r}\sum_{s=0}^{r-1}2^{n-1}e^{j(n-1)\pi s/r}\cos^{n-1} \left(\frac{\pi s}{r}\right)$$ I think you can proceed from here...
A: An addenudm to ILUA's answer. General methods for this kind of identities are treated in the gorgeous generatingfunctionology by Herbert S. Wilf. For this particular method, see Example 4 at page 51, especially the remark at the end.
A: I suggest the more general question: how to evaluate $\sum_{k\equiv r\pmod4}k\binom nk$ as a function of $n$ and the class$~r$ modulo$~4$.
There are two issues: the factor $k$ and the fact that you only want to sum over $k\equiv1\pmod n$.
The factor $k$ can be handled in two ways: absorb it into the binomial coefficient using $k\binom nk=n\binom{n-1}{k-1}$, as was done in the (now deleted) answer by servabat, or replace the factor $k$ by $X^k$, so that one can recover it later by formal differentiation. I will take the second path here, though the first is quite as easy.
Now we are down to evaluating a sum $\sum_{k\equiv r\pmod4}\binom nkX^k$. Without the condition on $k$ is would just be the binomial formula for $(1+X)^n$. The standard trick now is to write the indicator function $\chi_r(k)=[k\equiv r\pmod4]$ (those are Iverson brackets) as a linear combination of the functions $\omega^k$ four the four $4$-th roots of unity $\def\ii{\mathbf i}\omega\in\{1,\ii,-1,-\ii\}$ (this is related to the discrete Fourier transform). Indeed one easily sees that$\sum_{\omega\in\{1,\ii,-1,-\ii\}}\omega^k=4[4\mid k]=4\chi_0(k)$, from which it follows that $\chi_r(k)=\frac14\sum_{\omega\in\{1,\ii,-1,-\ii\}}c_\omega\omega^k$ for the set of coefficients $c_\omega=\omega^{-r}$. So we can compute
$$
  \sum_{k\equiv r\pmod4}\binom nkX^k = \sum_k\chi_r(k)\binom nkX^k
 =\frac14\sum_k\Biggl(\sum_{\omega\in\{1,\ii,-1,-\ii\}}c_\omega\omega^k\Biggr)\binom nkX^k =\\
\frac14\sum_{\omega\in\{1,\ii,-1,-\ii\}}\omega^{-r}\sum_k\binom nk(\omega X)^k
=\frac14\sum_{\omega\in\{1,\ii,-1,-\ii\}}\omega^{-r}(1+\omega X)^n =\\
\frac{(1+X)^n+\ii^{-r}(1+\ii X)^n+(-1)^r(1-X)^n+(-\ii)^{-r}(1-\ii X)^n}4
$$
Now differentiating with respect to$~X$ and then setting $X=1$ gives our answer
$$
  \sum_{k\equiv r\pmod4}k\binom nk 
= \frac n4\Bigl(2^{n-1}+\ii^{1-r}(1+\ii)^{n-1}+(-1)^{1-r}0^{n-1}
                +(-\ii)^{1-r}(1-\ii)^{n-1}\Bigr) =\\
  \frac n4\Bigl(2^{n-1}+(-1)^{1-r}0^{n-1}+2^\frac{n+1}2\cos\bigl(\frac\pi4(n+1-2r)\bigr)\Bigr).
$$
As a check, set $n=21$ and $r=1$ to obtain
$$
  \sum_{k\equiv1\pmod4}k\binom{21}k 
=
  \frac{21}4\Bigl(2^{20}+2^{11}\cos\bigl(5\pi\bigr)\Bigr)
=21\times(2^{18}-2^9)=5494272,
$$
in agreement with the brute force answer.
A: Too long for a comment: We are basically asked to evaluate $~\displaystyle\sum_{k=0}^n{an+1\choose ak+1}(ak+1),~$ which 
can be rewritten as $(an+1)\cdot\displaystyle\sum_{k=0}^n{an\choose ak}~=~(an+1)\cdot S(a).~$ The values of $S(a)$ for $0\le a\le6$: 
$S(0)=n+1,~$ $S(1)=2^n,~$ $S(2)=\dfrac{4^n}2,~$ $S(3)=\dfrac{8^n+2~(-1)^n}3,~$ $S(4)=\dfrac{16^n+2~(-4)^n}4,~$ 
$S(5)=\dfrac{32^n+2~(\omega_1^n+\omega_2^n)}5,~$ $S(6)=\dfrac{64^n+2~(-27)^n+2}6,~$ where $\omega_{1,2}=\dfrac{-11\pm5\sqrt5}2$.
