Difference between revisions of "1969 Canadian MO Problems/Problem 6"

 
 
(11 intermediate revisions by 6 users not shown)
Line 1: Line 1:
 
== Problem ==
 
== Problem ==
Find the sum of <math>\displaystyle 1\cdot 1!+2\cdot 2!+3\cdot 3!+\cdots+(n-1)(n-1)!+n\cdot n!</math>, where <math>\displaystyle  n!=n(n-1)(n-2)\cdots2\cdot1</math>.
+
Find the sum of <math>1\cdot 1!+2\cdot 2!+3\cdot 3!+\cdots+(n-1)(n-1)!+n\cdot n!</math>, where <math> n!=n(n-1)(n-2)\cdots2\cdot1</math>.
  
== Solution ==
+
== Solution 1==
Note that for any positive integer <math>\displaystyle  n,</math> <math>\displaystyle  n\cdot n!+(n-1)\cdot(n-1)!=(n^2+n-1)(n-1)!=(n+1)!-(n-1)!.</math>
+
Note that for any [[positive integer]] <math> n,</math> <math> n\cdot n!+(n-1)\cdot(n-1)!=(n^2+n-1)(n-1)!=(n+1)!-(n-1)!.</math>
 
Hence, pairing terms in the series will telescope most of the terms.
 
Hence, pairing terms in the series will telescope most of the terms.
  
If <math>\displaystyle  n</math> is odd, <math>\displaystyle  (n+1)!-(n-1)!+(n-1)!-(n-3)!\cdots -2!+2!-0!.</math>
+
If <math> n</math> is [[odd integer | odd]], <math> (n+1)!-(n-1)!+(n-1)!-(n-3)!\cdots -2!+2!-0!.</math>
  
If <math>\displaystyle  n</math> is even, <math>\displaystyle  (n+1)!-(n-1)!+(n-1)!-(n-3)!\cdots -3!+3!-1!.</math>
+
If <math> n</math> is [[even integer | even]], <math> (n+1)!-(n-1)!+(n-1)!-(n-3)!\cdots -3!+3!-1!.</math>
In both cases, the expression telescopes into <math>\displaystyle  (n+1)!-1.</math>
+
In both cases, the expression telescopes into <math> (n+1)!-1.</math>
  
----
+
== Solution  2==
* [[1969 Canadian MO Problems/Problem 5|Previous Problem]]
+
 
* [[1969 Canadian MO Problems/Problem 7|Next Problem]]
+
We need to evaluate:
* [[1969 Canadian MO Problems|Back to Exam]]
+
<cmath>1\cdot 1!+2\cdot 2!+\cdots+(n-1)(n-1)!+n\cdot n!</cmath>
 +
We replace <math>k\cdot k!</math> with <math>((k+1)-1)\cdot k!</math>
 +
<cmath>(2-1)\cdot 1!+(3-1)\cdot 2!+\cdots+((n)-1)(n-1)!+((n+1)-1)\cdot n!</cmath>
 +
Distribution yields
 +
<cmath>(2\cdot 1!-1\cdot1!+3\cdot2!-1\cdot2!+\cdots+n(n-1)!-1(n-1)!+(n+1)n!-1\cdot n!</cmath>
 +
Simplifying,
 +
<cmath>2!-1!+3!-2!+\cdots+n!-(n-1)!+(n+1)!-n!</cmath>
 +
Which telescopes to
 +
<cmath>(n+1)!-1!=(n+1)!-1</cmath>
 +
So <math>(n+1)!-1</math> is the solution.
 +
 
 +
== Solution  3==
 +
 
 +
<math>S=\sum_{k=1}^{n}k\cdot k!=\sum_{k=1}^{n}(k\cdot k!+k!-k!)=\sum_{k=1}^{n}\left( (k+1)\cdot k!-k! \right)=\sum_{k=1}^{n}(k+1)\cdot k!-\sum_{k=1}^{n}k!\\
 +
=\sum_{k=2}^{n+1}k!-\sum_{k=1}^{n}k!=(n+1)!+\sum_{k=2}^{n}k!-\sum_{k=2}^{n}k!-1!=\boxed{(n+1)!-1}</math>
 +
 
 +
~Tomas Diaz. orders@tomasdiaz.com
 +
 
 +
{{alternate solutions}}
 +
 
 +
{{Old CanadaMO box|num-b=5|num-a=7|year=1969}}

Latest revision as of 20:33, 27 November 2023

Problem

Find the sum of $1\cdot 1!+2\cdot 2!+3\cdot 3!+\cdots+(n-1)(n-1)!+n\cdot n!$, where $n!=n(n-1)(n-2)\cdots2\cdot1$.

Solution 1

Note that for any positive integer $n,$ $n\cdot n!+(n-1)\cdot(n-1)!=(n^2+n-1)(n-1)!=(n+1)!-(n-1)!.$ Hence, pairing terms in the series will telescope most of the terms.

If $n$ is odd, $(n+1)!-(n-1)!+(n-1)!-(n-3)!\cdots -2!+2!-0!.$

If $n$ is even, $(n+1)!-(n-1)!+(n-1)!-(n-3)!\cdots -3!+3!-1!.$ In both cases, the expression telescopes into $(n+1)!-1.$

Solution 2

We need to evaluate: \[1\cdot 1!+2\cdot 2!+\cdots+(n-1)(n-1)!+n\cdot n!\] We replace $k\cdot k!$ with $((k+1)-1)\cdot k!$ \[(2-1)\cdot 1!+(3-1)\cdot 2!+\cdots+((n)-1)(n-1)!+((n+1)-1)\cdot n!\] Distribution yields \[(2\cdot 1!-1\cdot1!+3\cdot2!-1\cdot2!+\cdots+n(n-1)!-1(n-1)!+(n+1)n!-1\cdot n!\] Simplifying, \[2!-1!+3!-2!+\cdots+n!-(n-1)!+(n+1)!-n!\] Which telescopes to \[(n+1)!-1!=(n+1)!-1\] So $(n+1)!-1$ is the solution.

Solution 3

$S=\sum_{k=1}^{n}k\cdot k!=\sum_{k=1}^{n}(k\cdot k!+k!-k!)=\sum_{k=1}^{n}\left( (k+1)\cdot k!-k! \right)=\sum_{k=1}^{n}(k+1)\cdot k!-\sum_{k=1}^{n}k!\\ =\sum_{k=2}^{n+1}k!-\sum_{k=1}^{n}k!=(n+1)!+\sum_{k=2}^{n}k!-\sum_{k=2}^{n}k!-1!=\boxed{(n+1)!-1}$

~Tomas Diaz. orders@tomasdiaz.com

Alternate solutions are always welcome. If you have a different, elegant solution to this problem, please add it to this page.

1969 Canadian MO (Problems)
Preceded by
Problem 5
1 2 3 4 5 6 7 8 Followed by
Problem 7