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