Evaluate the sum using derivatives and generating functions

Question

Evaluate $\sum_{k=1}^{n-3}\frac{(k+3)!}{(k-1)!}$.

My strategy is defining a generating function, $$g(x) = \frac{1}{1-x} = 1 + x + x^2...$$ then shifting it so that we get, $$f(x)=x^4g(x) = \frac{x^4}{1-x}= x^4+x^5+...$$ and then taking the 4th derivative of f(x). Calculating the fourth derivative is going to be a little tedious but it won't be as bad compared to the partial fraction decomposition I will end up doing. What is a better way to evaluate the sum using generating functions?

Answer 1

When you differentiate $g(x)$ $4$ times all powers of $x$ initially less than $4$ disappear anyway.

Then:

$$g^{(4)}(x)=4!(1-x)^{-5}=\sum_{k\ge 0}\frac{(k+4)!}{k!}x^k$$

Operating with $(1-x)^{-1}=1+x+x^2+x^3+\cdots$ on both sides gives a new expansion with terms which are partial sums of the coefficients of $x^k$ in the previous expansion:

$$(1-x)^{-1}g^{(4)}(x)=\sum_{r\ge 0}\left(\sum_{k=0}^{r}\frac{(k+4)!}{k!}\right)x^r$$

so

$$4!(1-x)^{-6}=\sum_{r\ge 0}\left(\sum_{k=0}^{r}\frac{(k+4)!}{k!}\right)x^r$$

$$\implies [x^r]4!(1-x)^{-6}=4!\binom{r+5}{5}=\sum_{k=0}^{r}\frac{(k+4)!}{k!}$$

but $r=n-4$ to match up with $n$ in the question, so

$$\sum_{k=0}^{n-4}\frac{(k+4)!}{k!}=4!\binom{n+1}{5}\tag{Answer}$$

This summation is the same as the one in the question with only a shift in summation index.

Of course you may notice that this is just Pascal's hockey stick rule.

Answer 2

If you consider $U_4(k)= k(k+1)(k+2)(k+3)(k+4)$

Then $U_4(k)-U_4(k-1)=k(k+1)(k+2)(k+3)\bigg((k+4)-(k-1)\bigg)=5U_3(k)$

Thus you get a telescoping series and

$$\sum\limits_{k=1}^{n-3}k(k+1)(k+2)(k+3)=\dfrac 15\bigg(U_4(n-3)-U_4(0)\bigg)=\dfrac 15U_4(n-3)\\=\dfrac{(n-3)(n-2)(n-1)(n)(n+1)}5$$

Answer 3

Here is a variation using generating functions without differentiation. It is convenient to use the coefficient of operator $[x^n]$ to denote the coefficient of $x^n$ of a series. This way we can write for instance \begin{align*} [x^k](1+x)^n=\binom{n}{k}\tag{1} \end{align*}

We obtain for $n\geq 4$ \begin{align*} \color{blue}{\sum_{k=1}^{n-3}\frac{(k+3)!}{(k-1)!}} &=4!\sum_{k=1}^{n-3}\binom{k+3}{4}=4!\sum_{k=0}^{n-4}\binom{k+4}{4}\tag{2}\\ &=4!\sum_{k=0}^{n-4}[x^4](1+x)^{k+4}\tag{3}\\ &=4^4\sum_{k=0}^{n-4}(1+x)^k\tag{4}\\ &=4^4\frac{(1+x)^{n-3}-1}{(1+x)-1}\tag{5}\\ &=4^{n+1}\tag{6}\\ &\,\,\color{blue}{=4!\binom{n+1}{5}}\tag{7} \end{align*}

Comment:

• In (2) we write the fraction using binomial coefficients and shift the index by one to start with $k=0$.

• In (3) we use the coefficient of operator according to (1).

• In (4) we use the linearity of the coefficient of operator.

• In (5) we apply the finite geometric series formula.

• In (6) we do some simplifications, apply the rule $[x^{p+q}]A(x)=[x^p]x^{-q}A(x)$ and ignore $(1+x)^{4}$ since it does not contribute to $[x^5]$.

• In (7) we select the coefficient of $[x^5]$ accordingly.