Sum of Sequence of n by 2 to the Power of n
Jump to navigation
Jump to search
Theorem
- $\ds \sum_{j \mathop = 0}^n j \, 2^j = n \, 2^{n + 2} - \paren {n + 1} 2^{n + 1} + 2$
Proof 1
From Sum of Arithmetic-Geometric Sequence:
- $\ds \sum_{j \mathop = 0}^n \paren {a + j d} r^j = \frac {a \paren {1 - r^{n + 1} } } {1 - r} + \frac {r d \paren {1 - \paren {n + 1} r^n + n r^{n + 1} } } {\paren {1 - r}^2}$
Hence:
\(\ds \sum_{j \mathop = 0}^n j \, 2^j\) | \(=\) | \(\ds \frac {0 \paren {1 - 2^{n + 1} } } {1 - 2} + \frac {2 \times 1 \paren {1 - \paren {n + 1} 2^n + n 2^{n + 1} } } {\paren {1 - 2}^2}\) | putting $a = 0, d = 1, r = 2$ | |||||||||||
\(\ds \) | \(=\) | \(\ds 2 \paren {1 - \paren {n + 1} 2^n + n 2^{n + 1} }\) | initial simplification | |||||||||||
\(\ds \) | \(=\) | \(\ds 2 - \paren {n + 1} 2^{n + 1} + n 2^{n + 2}\) | further simplification |
Hence the result.
$\blacksquare$
Proof 2
From Sum of Sequence of Power by Index:
- $\ds \sum_{j \mathop = 0}^n j x^j = \frac {n x^{n + 2} - \paren {n + 1} x^{n + 1} + x} {\paren {x - 1}^2}$
Hence:
\(\ds \ds \sum_{j \mathop = 0}^n j \, 2^j\) | \(=\) | \(\ds \frac {n 2^{n + 2} - \paren {n + 1} 2^{n + 1} + 2} {\paren {2 - 1}^2}\) | putting $x = 2$ | |||||||||||
\(\ds \) | \(=\) | \(\ds n 2^{n + 2} - \paren {n + 1} 2^{n + 1} + 2\) | simplification |
Hence the result.
$\blacksquare$
Sources
- 1997: Donald E. Knuth: The Art of Computer Programming: Volume 1: Fundamental Algorithms (3rd ed.) ... (previous) ... (next): $\S 1.2.3$: Sums and Products: Exercise $15$