# Finding combinatorial sum

How to compute $$\sum_{k=0}^{n} \left( k^2 \cdot \binom{n}{k} \cdot 3^{2k}\right)?$$

I have no idea other than guessing the answer and proving it by induction.

#### Solutions Collecting From Web of "Finding combinatorial sum"

Note that you can rewrite it as

$$\sum_{k=0}^nk^2\binom{n}k9^k\;.$$

Let

$$f(x)=\sum_{k=0}^nk^2\binom{n}kx^k\;.$$

Then

\begin{align*} f(x)&=\sum_{k=0}^nk^2\binom{n}kx^k\\ &=n\sum_{k=0}^nk\binom{n-1}kx^k\\ &=n\sum_{k=1}^{n-1}k\binom{n-1}kx^k\\ &=nx\sum_{k=1}^{n-1}k\binom{n-1}kx^{k-1}\\ &=nx\frac{d}{dx}\left(\sum_{k=1}^{n-1}\binom{n-1}kx^k\right)\\ &=nx\frac{d}{dx}\left(\sum_{k=0}^{n-1}\binom{n-1}kx^k-1\right)\;. \end{align*}

Use the binomial theorem to evaluate that last summation, take the indicated derivative, and find $f(9)$.

Start out with
\begin{align*}
(1+x)^n & =\sum_{k=0}^n \binom{n}{k}x^k\\
\frac{d}{dx}(1+x)^n & =\sum_{k=0}^n k\binom{n}{k}x^{k-1}\\
n(1+x)^{n-1}\color{red}{x} & = \sum_{k=0}^n k\binom{n}{k}x^{\color{red}{k}}\\
\frac{d}{dx}\left(n(1+x)^{n-1}\color{red}{x}\right) & = \sum_{k=0}^n k^2\binom{n}{k}x^{k-1}\\
\color{blue}{x}\frac{d}{dx}\left(n(1+x)^{n-1}\color{red}{x}\right) & = \sum_{k=0}^n k^2\binom{n}{k}x^{\color{blue}{k}}\\
nx(1+x)^{n-2}(nx+1) & = \sum_{k=0}^n k^2\binom{n}{k}x^{k}\\
\end{align*}
Plug in $x=9$ to get
$$9n(10)^{n-2}(9n+1)= \sum_{k=0}^n k^2\binom{n}{k}9^{k}$$