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

  • 1
    $\begingroup$ That's a nice proof! $\endgroup$ – joriki Jan 25 at 2:55
  • 1
    $\begingroup$ @DXT what joriki said. I (also) thought that you nailed it. $\endgroup$ – user2661923 Jan 25 at 3:23

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.


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.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.