Sum of Sequence of k x k!

From ProofWiki
Jump to navigation Jump to search

Theorem

Let $n \in \Z_{>0}$ be a (strictly) positive integer.


Then:

\(\ds \sum_{j \mathop = 1}^n j \times j!\) \(=\) \(\ds 1 \times 1! + 2 \times 2! + 3 \times 3! + \dotsb + n \times n!\)
\(\ds \) \(=\) \(\ds \paren {n + 1}! - 1\)


Proof 1

The proof proceeds by induction.


For all $n \in \Z_{\ge 1}$, let $\map P n$ be the proposition:

$\ds \sum_{j \mathop = 1}^n j \times j! = \paren {n + 1}! - 1$


Basis for the Induction

$\map P 1$ is the case:

\(\ds 1 \times 1!\) \(=\) \(\ds 1\)
\(\ds \) \(=\) \(\ds \paren {1 + 1}! - 1\)

Thus $\map P 1$ is seen to hold.


This is the basis for the induction.


Induction Hypothesis

Now it needs to be shown that if $\map P k$ is true, where $k \ge 1$, then it logically follows that $\map P {k + 1}$ is true.


So this is the induction hypothesis:

$\ds \sum_{j \mathop = 1}^k j \times j! = \paren {k + 1}! - 1$


from which it is to be shown that:

$\ds \sum_{j \mathop = 1}^{k + 1} j \times j! = \paren {k + 2}! - 1$


Induction Step

This is the induction step:

\(\ds \sum_{j \mathop = 1}^{k + 1} j \times j!\) \(=\) \(\ds \sum_{j \mathop = 1}^k j \times j! + \paren {k + 1} \times \paren {k + 1}!\)
\(\ds \) \(=\) \(\ds \paren {k + 1}! - 1 + \paren {k + 1} \times \paren {k + 1}!\) Induction Hypothesis
\(\ds \) \(=\) \(\ds \paren {k + 1}! \paren {1 + \paren {k + 1} } - 1\) factoring out $\paren {k + 1}!$
\(\ds \) \(=\) \(\ds \paren {k + 1}! \paren {k + 2} - 1\)
\(\ds \) \(=\) \(\ds \paren {k + 2}! - 1\)

So $\map P k \implies \map P {k + 1}$ and the result follows by the Principle of Mathematical Induction.


Therefore:

$\forall n \in \Z_{\ge 1}: \ds \sum_{j \mathop = 1}^n j \times j! = \paren {n + 1}! - 1$

$\blacksquare$


Proof 2

\(\ds \sum_{j \mathop = 1}^n j \times j!\) \(=\) \(\ds \sum_{j \mathop = 1}^n \paren {j + 1 - 1} \times j!\)
\(\ds \) \(=\) \(\ds \sum_{j \mathop = 1}^n \paren {\paren {j + 1} j! - j!}\)
\(\ds \) \(=\) \(\ds \sum_{j \mathop = 1}^n \paren {\paren {j + 1}! - j!}\)
\(\ds \) \(=\) \(\ds \paren {n + 1}! - 1!\) Telescoping Series: Example 1
\(\ds \) \(=\) \(\ds \paren {n + 1}! - 1\)

$\blacksquare$


Sources

Retrieved from "https://proofwiki.org/w/index.php?title=Sum_of_Sequence_of_k_x_k!&oldid=412173"