A question about asymptotic notations with sums. I need to prove that $$ \sum_{k=0}^{n-2017} \binom{n}{k} \binom{2k}{k} \frac{ \sqrt{k}}{2^{k}} = \Theta(3^{n})$$
I'm pretty sure it's straightforward to prove that it's $\Omega(3^{n})$ but I'm not sure how to prove the $O(3^{n})$ part. Maybe with using square root and derivative.
 A: *

*For the upper bound,, note that
$$\begin{align}
\sum_{k=0}^{n-2017} \binom{n}{k} \binom{2k}{k} \frac{ \sqrt{k}}{2^{k}}
&\leq \sum_{k=0}^{n} \binom{n}{k} \binom{2k}{k} \frac{ \sqrt{k}}{2^{k}}
\leq \sum_{k=0}^{n} \binom{n}{k} \frac{2^{2k}}{\sqrt{k}} \frac{ \sqrt{k}}{2^{k}}
\\&= \sum_{k=0}^{n} \binom{n}{k} 2^k
= (1+2)^n = 3^n
\end{align}$$
giving the upper bound. We used at the beginning the fact that 
$$
\binom{2k}{k} \leq \frac{2^{2k}}{\sqrt{3k+1}}\leq \frac{2^{2k}}{\sqrt{k}}.
$$

*For the lower bound, we have that
$$\begin{align}
\sum_{k=0}^{n-2017} \binom{n}{k} \binom{2k}{k} \frac{ \sqrt{k}}{2^{k}}
&
\geq \sum_{k=0}^{n-2017} \binom{n}{k} \frac{2^{2k}}{2\sqrt{k}} \frac{ \sqrt{k}}{2^{k}}
\\&= \frac{1}{2}\sum_{k=0}^{n-2017} \binom{n}{k} 2^k
\geq \frac{1}{2}\sum_{k=0}^{n} \binom{n}{k} 2^k - \frac{2017}{2}\binom{n}{n-2017} 2^n\\
&= \frac{1}{2}(1+2)^n - \frac{2017}{2} \binom{n}{2017}2^n
= \frac{3^n}{2} - \Theta(n^{2017}2^n) = \Theta(3^n)
\end{align}$$
giving the lower bound. There, we used the basic result for any constant $k$, $\binom{n}{k} = \Theta(n^k)$ when $n\to \infty$.
