Series prove using combinational argument

Question

Evaluation of $\displaystyle \sum^{n}_{r=1}(r^2+1)\cdot r!$ using combinational argument

Although i have solved it without combinational argument

$\displaystyle \sum^{n}_{r=1}\bigg[(r+1)^2-2r\bigg]r!=\sum^{n}_{r=1}(r+1)(r+1)!-r(r!)-\sum^{n}_{r=1}\bigg[(r+1-1)r!\bigg]$

$\displaystyle \sum^{n}_{r=1}\bigg[(r+1)(r+1)!-r(r!)\bigg]-\sum^{n}_{r=1}\bigg[(r+1)!-r!\bigg]$

$\displaystyle (n+1)(n+1)!-1-(n+1)!+1=n(n+1)!$

But did not know using combinational argument

If anyone have an idea please explain me .Thanks

Answer 1

Both sides of the identity $$\sum_{r=1}^n (r^2+1)r!=n (n+1)!$$ count the number of permutations of $\{1,\dots,n+2\}$ such that $n+1$ and $n+2$ are not adjacent. The RHS first permutes $\{1,\dots,n+1\}$ in $(n+1)!$ ways and then inserts $n+2$ into any of the $n$ positions that are not adjacent to $n+1$. For the LHS, first reverse the sum to $$\sum_{k=0}^{n-1} ((n-k)^2+1)(n-k)!.$$ We show that this sum counts the permutations $\pi$ according to the largest $k$ for which $\pi(1)=1,\dots,\pi(k)=k$. Note that $k<n$ because otherwise $n+1$ and $n+2$ would be adjacent. Now consider the three mutually exclusive cases:

• $\pi(k+1)=n+1$ and $\pi(k+2)\not=n+2$
• $\pi(k+1)=n+2$ and $\pi(k+2)\not=n+1$
• $\pi(k+1)\not\in\{k+1,n+1,n+2\}$

These cases yield $(n-k)(n-k)!$, $(n-k)(n-k)!$, and $(n-k-1) (n-k)! (n-k-1)$ permutations, respectively, with total $$(2 (n-k) + (n-k-1)^2) (n-k)!=((n-k)^2+1)(n-k)!,$$ as desired.

Answer 2

Extension of my comment: I think that the OP's proof is more of a (polished) answer than a solution. If I was trying to solve it, my first step would not be to attempt such a polished proof.

Instead, I would experiment with $n=1, n=2, n=3, n=4,$ and $n=5.$ After computing each of the 5 cases, I would compare the results with each other and try to look for a pattern. Once I found what seemed to be a viable pattern, then I would formulate a hypothesis.

Only after I had a hypothesis would I attempt to algebraically manipulate the summation to verify the hypothesis. In fact, I might well consider forgoing any attempt at an elegant algebraic manipulation, and instead consider a much more pedestrian (i.e. simpler but much less elegant) approach based on induction.