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 ).
Best Answer
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).