1
$\begingroup$

$$1\cdot1!+2\cdot2!+\cdots+x\cdot x! = (x+1)!−1$$

I don't understand what's happening here. The given sum of factorials is generalized into a single term. Could somebody please help me finding the logic behind this series.

Thanks in advance!!

$\endgroup$
  • 10
    $\begingroup$ hint: $$n\cdot n!=(n+1)!-n!$$ $\endgroup$ – ArtW Jun 20 '16 at 16:39
  • 3
    $\begingroup$ To emphasize the hint, the phrase telescoping series should come to mind. $\endgroup$ – JMoravitz Jun 20 '16 at 16:41
4
$\begingroup$

$$ n!\cdot n \quad = \quad n!\Big((n+1) - 1\Big) \quad = \quad \big(n!(n+1) \big) - \big( n!\cdot1 \big) \quad = \quad (n+1)! - n!. $$ Therefore \begin{align} & 1!1+2!2 + 3!3 + 4!4 + 5!5 \\[10pt] = {} & \Big(2!-1!\Big) + \big( 3!-2!\Big) + \Big(4!-3!\Big) + \Big(5!-4!\Big) + \big(6!-5!\Big) \end{align} Now notice that all terms cancel except the biggest one and the smallest one.

$\endgroup$
4
$\begingroup$

Michael Hardy’s computational proof is the simplest, but there is also a reasonably straightforward combinatorial argument.

There are $(n+1)!-1$ permutations of the set $[n+1]=\{1,2,\ldots,n+1\}$ other than the increasing permutation $\langle 1,2,\ldots,n+1\rangle$. Let $P$ be the set of all such permutations; we’ll now calculate $|P|$ in another way.

For $k=1,\ldots,n$ let $P_k$ be the set of permutations $\langle p_1,p_2,\ldots,p_{n+1}\rangle\in P$ such that $p_k\ne k$, and $p_\ell=\ell$ for $1\le\ell<k$. If $\langle p_1,\ldots,p_{n+1}\rangle\in P_k$, $p_k$ cannot be any of the positive integers less than or equal to $k$, so there are $(n+1)-k$ possible choices for $p_k$. Once $p_k$ has been set, $\langle p_{k+1},\ldots,p_{n+1}\rangle$ can be any permutation of the remaining $(n+1)-k$ members of $[n+1]$, so

$$|P_k|=(n+1-k)(n+1-k)!\;.$$

Thus,

$$(n+1)!-1=\sum_{k=1}^n|P_k|=\sum_{k=1}^n(n+1-k)(n+1-k)!=\sum_{\ell=1}^n\ell\cdot\ell!\;,$$

where in the last step I just set $\ell=n+1-k$.

$\endgroup$

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.