# Series prove using combinational argument

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

• That's a nice proof! – joriki Jan 25 at 2:55
• @DXT what joriki said. I (also) thought that you nailed it. – 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 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.