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! :)

  • $\begingroup$ Why do you think there is one? $\endgroup$ – DonAntonio Jun 14 '14 at 21:40
  • 2
    $\begingroup$ Factor $2^n$. Now you have this: math.stackexchange.com/questions/833480/… $\endgroup$ – chubakueno Jun 14 '14 at 21:42
  • $\begingroup$ @DonAntonio, wolfram yields a closed form. $\endgroup$ – recursive recursion Jun 14 '14 at 21:43
  • $\begingroup$ @recursiverecursion, your link sent me to the sum of the first $\;n\;$ natural numbers, nothing to do with the present case... $\endgroup$ – DonAntonio Jun 14 '14 at 21:44
  • $\begingroup$ @DonAntonio, are you sure? Click it again. $\endgroup$ – recursive recursion Jun 14 '14 at 21:45

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*}


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.


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.