# Calculate sum $\sum\limits_{k=0}k^2{{n}\choose{k}}3^{2k}$.

I need to find calculate the sum Calculate sum $\sum\limits_{k=0}k^2{{n}\choose{k}}3^{2k}$.

Simple algebra lead to this $\sum\limits_{k=0}k^2{{n}\choose{k}}3^{2k}=n\sum\limits_{k=0}k{{n-1}\choose{k-1}}3^{2k}$. But that's still not very helpful. This binomial screws everything up for me, I would like a nice recurrence relation, but don't know what to do with it.

• I suppose the sum goes up to $n$? – punctured dusk Feb 9 '14 at 14:06
• Well yes, since the binomial for $k \ge n+1$ is $0$ – Arek Krawczyk Feb 9 '14 at 14:07
• – lab bhattacharjee Feb 9 '14 at 14:36

We have

$$\sum_{k=0}^n \binom{n}{k} x^k = (1+x)^n.$$

Differentiating that (twice) yields

\begin{align} \sum_{k=0}^n k\binom{n}{k}x^{k-1} &= n(1+x)^{n-1}\\ \sum_{k=0}^n k(k-1)\binom{n}{k}x^{k-2} &= n(n-1)(1+x)^{n-2}. \end{align}

Now set $x = 3^2$ and write

$$\sum_{k=0}^n k^2 \binom{n}{k} x^k = x^2 \sum_{k=0}^n k(k-1)\binom{n}{k}x^{k-2} + x\sum_{k=0}^n k\binom{n}{k}x^{k-1}.$$

You get

$$\sum_{k=0}^n k^2\binom{n}{k}3^{2k} = 3^4n(n-1)10^{n-2} + 3^2 n 10^{n-1}.$$

• Very cool, thanks :) – Arek Krawczyk Feb 9 '14 at 14:21

Let $$f(x)=(1+x)^n=\sum_{k=0}^n{n\choose k}x^k.$$ Then $$f'(x)=\sum_{k=1}^nk{n\choose k}x^{k-1}$$ $$xf'(x)=\sum_{k=0}^nk{n\choose k}x^{k}$$ $$xf'(x)+x^2f''(x)=x\frac d{dx}xf'(x)=\sum_{k=0}^nk^2{n\choose k}x^{k}.$$ You are looking for the last expression at $x=9$.

We have $\displaystyle k^2=k(k-1)+k$

So, $\displaystyle k^2 \binom nk=k(k-1)\binom nk+k\binom nk$

Now $\displaystyle k\cdot\binom nk=k\frac{n!}{(n-k)!k!}=kn\frac{(n-1)!}{[n-1-(k-1)]!(k-1)!\cdot k}=n\binom{n-1}{k-1}$

and $\displaystyle k(k-1)\cdot\binom nk=k(k-1)\frac{n!}{(n-k)!k!}=k(k-1)n(n-1)\frac{(n-2)!}{[n-2-(k-2)]! (k-2)!\cdot k(k-1)}=n(n-1)\binom{n-2}{k-2}$

$\displaystyle\implies\sum_{k=0}^n k^2 \binom nk3^{2k}=\sum_{k=0}^n k^2 \binom nk9^k$ $\displaystyle=9n \sum_{k=0}^n\binom{n-1}{k-1}9^{k-1}+n(n-1)9^2\sum_{k=0}^n\binom{n-2}{k-2}9^{k-2}$

Utilize $\binom mr=0$ for $r<0$ or $r>m$

More generally, $\displaystyle \sum_{r=0}^ma_rk^r=b_0+b_1\cdot k+b_2\cdot k(k-1)+\cdots+b_{m-1}\prod_{r=0}^{m-2}(k-r)+b_m\prod_{r=0}^{m-1}(k-r)$ where $b_r$s are arbitrary constants

Let $$f(x):=\sum_{k=0}^n k^2\binom nkx^k=nx\sum_{k=0}^n\binom{n-1}{k-1}kx^{k-1} =nx\,g(x)\,,$$ where we set $g(x):=\sum_{k=0}^n\binom{n-1}{k-1}kx^{k-1}$. Then integrate $g$: $$\int g(x)\,dx=\sum_{k=1}^n\binom{n-1}{k-1}x^k=x\,\sum_{k=0}^{n-1}\binom{n-1}kx^k\ =\ x\,(1+x)^{n-1}\,.$$ Now differentiate this to get $g(x)$, and then you get $f(x)=nx\,g(x)$.