Summation closed form.

Question

I have tried to figure out how to get the close form of:

$$\sum_{k=0}^n k^22^{n-k}.$$

I tried to write down each number of the summation but couldn't find any thing to do with that..

can please someone explain to me how to do it? thanks a lot! :)

Answer 1

We can solve it by convolution of generating functions:

\begin{align*} A(x) &= \sum_{k\ge 0} k^2\, x^k = \frac{x+x^2}{(1-x)^3} \\ B(x) &= \sum_{k\ge 0} 2^k\, x^k = \frac{1}{1-2\, x} \\ A(x)\cdot B(x) &= \sum_{n\ge 0} \left(\sum_{k= 0}^n k^2\, 2^{n-k} \right) x^n = \frac{x+x^2}{(1-x)^3(1-2\, x)} \end{align*} Then we can extract $[x^n]$ by doing partial fractions: \begin{align*} A(x)\cdot B(x) &= \frac{6}{1-2 \, x } - \frac{2}{{\left(1-x\right)}^{3}} - \frac{1}{{\left( 1-x\right)}^{2}} -\frac{3}{1-x} \end{align*}

Hence, \begin{align*} \sum_{k= 0}^n k^2\, 2^{n-k} &= 6\cdot 2^n - 2\, \binom{n+2}{2} - \binom{n+1}{1} - 3 \\ &= 6\cdot 2^n - n^2 - 4\, n - 6 \end{align*}

Answer 2

Okay, it took a while, but I've been able to derive the formula. Let us define $f(n)$ to be the sum in question. Now we have that $f(n+1) = 2f(n) + (n+1)^2$, the $(n+1)^2$ coming from the last term, and the doubling of $f(n)$ being a result of raising the exponent on the $2$ by a factor of $1$ for each term. Now we have a recurrence relation, which is $f(0) = 0, f(n+1) = 2f(n) + (n+1)^2$.

Substituting $n$ for $n+1$ yields $f(n) = 2f(n-1) + n^2$, and dividing both sides by $2^n$ gives us $$\frac{f(n)}{2^n} = \frac{f(n-1)}{2^{n-1}} + \frac{n^2}{2^n}.$$

Now we define another function $g(n)$ to be $f(n)/2^n$, so we have $$g(n) = g(n-1) + \frac{n^2}{2^n}$$ $$\implies g(n) = \sum_{k = 0}^{n} \frac{k^2}{2^k}.$$

It is not hard to work out the closed form of $g(n)$, which is $2^{-n}[6(2^n)-n^2-4n-6]$. Now we recall that $g(n) := f(n)/2^n$, and of course multiplying $g(n)$ by $2^n$ yields $6(2^n)-n^2-4n-6$, which is indeed the closed form of your summation. Many thanks to Ayman Hourieh, who responded to this question.