Big-O for $\Sigma_{i = 1}^{N} i \times \binom{N}{i}$

Question

How to solve Big-O for $\Sigma_{i = 1}^{N} i \times \binom{N}{i}$? Can I simply say it is in $O(N!)$?

Answer 1

Yes it is true, but we can get a better upper bound by observing that $$ \sum_{i=1}^N\binom{N}{i}\binom{i}{1}=\sum_{i=1}^N N\binom{N-1}{i-1}=N\sum_{u=0}^{N-1}\binom{N-1}{u}=N2^{N-1} $$ where we have used the identity $$ \binom{n}{k}\binom{k}{r}=\binom{n}{r}\binom{n-r}{k-r}\quad (n\ge k\geq r\geq 0) $$ as well as the fact that $$ 2^n=(1+1)^n =\sum_{k=0}^n \binom{n}{k} $$ by the binomial theorem.