Use generating functions to calculate the sum $\sum_{k=0}^n (k+1)(n-k+1)$

Question

Use generating functions to calculate the sum $\sum_{k=0}^n (k+1)(n-k+1)$

And Prove it by induction.

Attempt:

$$A(x)= \sum_{k=0}^n (k+1)(n-k+1)$$

$$\sum_{n=0}^\infty(\sum_{k=0}^n (k+1)(n-k+1))x^n$$

The series of differences is :$\{(n+1),2(n),3(n-1),4(n-2)…,1,…\}$

The generating functions of this series is : $(1-x)A(x)$

The series of differences is :$\{(n+1),(n-1),(n-3),(n-5),…,2-n,…\}$

The generating functions of this series is : $(1-x)^2A(x)$

The series of differences is :$\{(n+1),-2,-2,-2,…,-2,…\}$

The generating functions of this series is : $(1-x)A^3(x)$

The series of differences is :$\{(n+1),-(n+3),0,0,…,0,…\}$

The generating functions of this series is : $(1-x)^4A(x)$

On the other hand, the generating functions $(n+1)+(-n-3)x$,

Therefore: $(1-x)^4A(x)=(n+1)+(-n-3)x$

$$A( x) =\frac{( n+1) +( -n-3) x}{( 1-x)^{4}} =(( n+1) +( -n-3) x) \cdot \sum _{n=0}^{\infty }\binom{n+4-1}{4-1} x^{n}$$

$$\displaystyle \sum _{k=0}^{n}( k+1)( n-k+1) =\sum _{n=0}^{\infty }( n+1) \cdot \binom{n+4-1}{4-1} x^{n} +\sum _{n=0}^{\infty }( -n-3) \cdot \binom{n+4-1}{4-1} x^{n+1}$$

Prove in with induction :

\begin{aligned} ( n+1) \cdot \binom{n+3}{3} +( -n-3)\binom{n+2}{3} & =\frac{( n+3)( n+2)( n+1)^{2} n}{3!} +\frac{( n+2)( n+1)( n-1) n( -n-3)}{3!}\\ & =\frac{( n+3)( n+2)( n+1)^{2} -( n+2)( n+1)( n+3) n}{6}\\ & =\frac{( n+3)( n+2)( n+1)}{6}\\ & =\frac{1}{6}\left( n^{3} +6n^{2} +11n+6\right) \end{aligned}

$$\displaystyle \sum _{k=0}^{n}( k+1)( n-k+1) =\frac{1}{6}\left( n^{3} +6n^{2} +11n+6\right)$$

induction basis: $n=0$

$$\displaystyle \sum _{k=0}^{n}( 0+1)( 0-0+1) =1=\frac{1}{6}\left( 0^{3} +6\cdotp 0^{2} +11\cdotp 0+6\right)$$

For $n+1$:

\begin{aligned} \sum _{k=0}^{n+1}( k+1)( n-k+1) & =\sum _{k=0}^{n}( k+1)( n-k+1) +( n+2)(( n+1) -( n+1) +1)\\ & =\frac{1}{6}\left( n^{3} +6n^{2} +11n+6\right) +( n+2)\\ \end{aligned}

If anyone can enlighten me, and find my mistakes I appreciate that.

Unfortunately, I did not succeed.

Answer 1

Note that \begin{align} \sum_{n \ge 0} \sum_{k=0}^n a_k a_{n-k} x^n &=\sum_{k \ge 0} a_k x^k \sum_{n\ge k} a_{n-k} x^{n-k} \tag1\\ &=\sum_{k \ge 0} a_k x^k \sum_{n\ge 0} a_n x^n \tag2\\ &=\left(\sum_{n \ge 0} a_n x^n\right)^2 \end{align} Equality $(1)$ arises from interchanging the order of summation. Equality $(2)$ arises from the change of index $n\mapsto n+k$. Taking $a_k = k+1$ yields \begin{align} \sum_{n \ge 0} \sum_{k=0}^n (k+1)(n-k+1) x^n &=\left(\sum_{n \ge 0} (n+1) x^n\right)^2 \\ &=\left(\sum_{n \ge 0} \binom{n+1}{1} x^n\right)^2 \\ &=\left(\frac{1}{(1-x)^2}\right)^2 \\ &=\frac{1}{(1-x)^4} \\ &=\sum_{n\ge 0} \binom{n+3}{3} x^n \\ \end{align} So $$\sum_{k=0}^n (k+1)(n-k+1) = \binom{n+3}{3}$$ for $n \ge 0$.

---

Alternatively, you can prove the equivalent identity $$\sum_{k=2}^{n+2} \binom{k-1}{1}\binom{n-k+3}{1}=\binom{n+3}{3}$$ combinatorially by counting $3$-subsets of $\{1,\dots,n+3\}$ in two different ways. The RHS is clear. For the LHS, condition on the middle element $k$. You then have $k-1$ choices for the smallest element and $n-k+3$ choices for the largest element.

Answer 2

I have no idea what you are doing, but the generating function of $(k+1)(n-k+1)$ is the derivative of the generating function of $(n-k+1).$ In other words,

if $$A_n(x) = \sum_{i=1}^{n+1} (n-k+1) x^k,$$ then

$$A^\prime_n = \sum_{i=0}^n (k+1)(n-k+1),$$ and your sum is just equal to $A_n^\prime(1).$

Now, $$A_n(x) = n \sum_{i=1}^{n+1} x^k - \sum_{i=1}^{n+1}(k+1)x^k.$$

The geometric series you (hopefully) know how to sum, while the second term is the derivative of a geometric series.

Answer 3

Unclear if this is off-topic. The OP specifically requires that generating functions be used. Other responses have covered this constraint, so I'll show an alternative approach.

Known (or routinely proven by induction) that

• $\displaystyle \sum_{i = 1}^n i = \left(\frac{1}{2}\right)(n+1)(n).$

• $\displaystyle \sum_{i = 1}^n i^2 = \left(\frac{1}{6}\right) (n+1)(2n+1)(n).$

Since $(n - k + 1) = (n + 2) - (k + 1)$
$\displaystyle \sum_{k = 0}^n (k+1) (n - k + 1)$ can be re-expressed as

$$\sum_{k = 0}^n (k + 1) (n + 2) - \sum_{k = 0}^n [(k + 1) (k + 1)]. \tag{1}$$

The first summation from expression (1) above is $$ (n+2) \sum_{k=1}^{n+1} k = (n+2) \left(\frac{1}{2}\right) (n+1)(n+2). \tag{2}$$

The second summation from expression (1) above is $$\sum_{k=1}^{n+1} k^2 = \left(\frac{1}{6}\right) (n+2)(2n+3)(n+1). \tag{3}$$

Taking common factors between expressions (2) and (3) above, you have that the overall computation is $$\left(\frac{1}{6}\right)(n+1)(n+2) ~~[3(n+2) - (2n + 3)] $$

$$= ~~ \left(\frac{1}{6}\right)(n+1)(n+2)(n+3) = \binom{n+3}{3}.$$