Let $\beta >4$. Prove that if $$a_n = \sum_{k=1}^{n}k{n\choose k}{n\choose {k-1}}$$ then $$\lim_{n=0}\frac{a_n}{\beta^n} = 0$$ My attempt to solve it:
I tried to show that $a_n \leq 4^n = \sum_{k = 1}^{n}k{n\choose k}3^k$ (by derivating the binomial identity) so what I actually need to show is that ${n\choose {k-1}} \leq 3^k$ for every $k\in \mathbb{N}$, and here I got stuck.
Any help in showing this or a completely different solution will be appreciated.
$$\begin{eqnarray}a_n &=&\sum_{k=0}^{n}k{n\choose k}{n\choose {k-1}}\\&=&n\sum_{k=0}^{n}{n-1\choose k-1}{n\choose {k-1}}\\ &=&n\sum_{k=0}^{n}{n-1\choose n-k}{n\choose {k-1}}\\ &=&n\binom{2n-1}{n-1}=\frac{n}{2}\binom{2n}{n}. \end{eqnarray}$$ Since it holds by binomial theorem that $$ \sum_{k=0}^n \binom{2n}{k}kx^{k-1}=2n(1+x)^{2n-1}, $$we have (by letting $x=1$) $$ 0\le 2a_n = n\binom{2n}{n}\le 2n\cdot 2^{2n-1}=n\cdot 4^n. $$ For $\beta>4$, we have $$ \lim_{n\to\infty} \frac{a_n}{\beta^n}\le \lim_{n\to\infty} \frac{n}{2}\left(\frac{4}{\beta}\right)^n = 0. $$