Closed form expression of $ \sum_{k=0}^n (3k^3 +2k^2 -3k +2) r^k {n \choose k} $

Question

Problem: Find an expression without summation for the following sum: $ \sum_{k=0}^n P(k) r^k {n \choose k} $ , where $ P(k) = 3k^3 +2k^2 -3k +2 $.

Attempt: I managed to show that $ \sum_{k=0}^n k(k-1) r^k {n \choose k} = n(n-1)(r+1)^{n-2}r^2 $ in a previous exercise ( by using derivatives ). Now I think I'm supposed to use this identity, so I tried in a similar fashion to get an useful expression when taking the derivative of $ \sum_{k=0}^n r^k {n \choose k} $ three times. But first I tried to get an useful expression from the coefficient that I'll get as a result, so I did as follows:
Note $ k(k-1)(k-2) = k(k^2 -2k-k+2)=k(k^2 - 3k +2 ) = k(2k^2 -3k+2 -k^2) = k(2k^2 -3k +2 ) -k^3 $
Also, $ P(k) -3k^2 = 2k^2 -3k +2 \iff k \cdot ( P(k) - 3k^2 ) -k^3 = k(2k^2 -3k +2 )-k^3 = k(k-1)(k-2) $. But I realized I've reached a dead-end since I got nothing useful.

Do you have any ideas? any help would be appreciated.

Note: I can't use generating functions ( if it's even needed here ).

Answer 1

Hint: $3k^3 +2k^2 -3k +2=k(3k^2+2k-3)+2=k(2k^2+(k+3)(k-1))+2.$ Now $2k^2=2k(k-1)+2k$ and so $$P(k)=k(2k(k-1)+2k+(k+3)(k-1))+2=k((k-1)(2k+k+3)+2k)=k(3(k-1)(k+1)+2k)+2,$$ this means that $P(k)=18\cdot \binom{k+1}{3}+2k(k-1)+2k+2=18\binom{k+1}{3}+4\binom{k}{2}+2\binom{k+1}{1}=18\binom{k}{3}+22\binom{k}{2}+2\binom{k}{1}+2.$

Now, split the sum in the four terms and show that $\binom{a}{b}\binom{b}{c}=\binom{a}{c}\binom{a-c}{b-c}.$ Use binomial theorem afterwards.

Note: This is a general technique, you can always express a polynomial in the monomial basis in terms of the falling factorial basis(binomials are particular polynomials there).

Answer 2

When you face a problem like $$S_n=\sum_{k=0}^n P_m(k) {n \choose k}r^k $$ is to consider that it involves the $m^{\text{th}}$ derivative of something and then to consider that is is a linear combination of terms like $k$, $k(k-1)$, $k(k-1)$,$k(k-1)(k-2)$ and so on.

So, use $$k^2=k(k-1)+k \qquad \text{and} \qquad k^3=k(k-1)(k-2)+3k(k-1)+k$$ So $$3k^3 +2k^2 -3k +2=3 \Big[k(k-1)(k-2)+3k(k-1)+k \Big]+2\Big[k(k-1)+k\Big]-3k+2$$ that is to say $$3k^3 +2k^2 -3k +2=3k(k-1)(k-2)+11k(k-1)+2k+2$$

So, we have $$S_n=3r^3\left(\sum_{k=0}^n {n \choose k}r^k\right)^{'''}+11r^2\left(\sum_{k=0}^n {n \choose k}r^k\right)^{''}+2r\left(\sum_{k=0}^n {n \choose k}r^k\right)^{'}+2\left(\sum_{k=0}^n {n \choose k}r^k\right)$$

What we could have also done is to write $$3k^3 +2k^2 -3k +2=a k(k-1)(k-2)+bk(k-1)+c k +d$$ $$3k^3 +2k^2 -3k +2=a k^3+ (b-3 a)k^2+ (2 a-b+c)k+d$$ and comparing coefficients $$a=3 \qquad b=11 \qquad c=2 \qquad d=2$$