1
$\begingroup$

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.

$\endgroup$
4
$\begingroup$

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}.$$

$\endgroup$
  • $\begingroup$ Very cool, thanks :) $\endgroup$ – Arek Krawczyk Feb 9 '14 at 14:21
4
$\begingroup$

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$.

$\endgroup$
1
$\begingroup$

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

$\endgroup$
1
$\begingroup$

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)$.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.