AoPSWiki

Visit the AoPS Book Store.

Personal tools

Search

Toolbox

User:Temperal/The Problem Solver's Resource3

From AoPSWiki

< User:Temperal

Introduction \| Other Tips and Tricks \| Methods of Proof \| You are currently viewing page 3.

Summations and Products

Definitions

Rules of Summation

$\sum_{i=a}^{b}f_1(i)+f_2(i)+\ldots f_n(i)=\sum_{i=a}^{b}f(i)+\sum_{i=a}^{b}f_2(i)+\ldots+\sum_{i=a}^{b}f_n(i)$

$\sum_{i=a}^{b}c\cdot f(i)=c\cdot \sum_{i=a}^{b}f(i)$

$\sum_{i=1}^{n} i= \frac{n(n+1)}{2}$ , and in general $\sum_{i=a}^{b} i= \frac{(b-a+1)(a+b)}{2}$

The above should all be self-evident and provable by the reader within seconds.

$\sum_{i=1}^{n} i^2 = \frac{n(n+1)(2n+1)}{6}$

Derivation: We write $n^2$ as $a_1\binom{n}{1}+a_2\binom{n}{2}$ . Substituting n=1 gives $a_1=1$ while substituting n=2 gives $a_2=2$ . Hence, $n^2=\binom{n}{1}+2\binom{n}{2}$ .

Now, $\sum_{i=1}^{n} i^2=\sum_{i=1}^n (\binom{i}{1}+2\binom{i}{2})=\sum_{i=1}^n \binom{i}{1}+2\sum_{i=1}^n \binom{i}2=\binom{n+1}{2...$ , where we use the Hockey-Stick Identity. After some algebra, this comes out to $\frac{(n)(n+1)(2n+1)}{6}$ .

This method can be generalized nicely; $i^n=\sum_{k=1}^n a_k\binom{i}{k}$ .

Particularly notable is the case $n=3$ ; we get $\sum_{i=1}^{n} i^3 = \left(\sum_{i=1}^{n} i\right)^2 = \left(\frac{n(n+1)}{2}\right)^2$ . The reader can figure this out themselves.

Rules of Products

$\prod_{i=a}^{b}x=x^{(b-a+1)}$

$\prod_{i=a}^{b}x\cdot y=x^{(b-a+1)}y^{(b-a+1)}$

These should be self-evident, as above.

Back to page 2 | Continue to page 4

Retrieved from "http://www.artofproblemsolving.com/Wiki/index.php/User:Temperal/The_Problem_Solver%27s_Resource3"

Try our innovative online adaptive learning system, Alcumus.
Over 1100 problems and 60+ video lessons. FREE!

© Copyright 2008 AoPS Incorporated. All Rights Reserved. • Foundation • Privacy • Contact Us