How to determine the general formula for a summation?

Question

What are some strategies for trying to determine the general formula for a summation?

For example, let's say I'm trying to determine the general formula for

$\sum_{i=1}^n \frac{i}{n}$

I was not sure how to approach this question, so I plugged and tested several values of $n$ in order to determine a pattern, and determined that:

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

However, I feel that there are probably more efficient and reliable ways to solve these types of questions other than inserting values and finding patterns. If anyone has any guidance, it would be greatly appreciated!

Thanks.

Answer 1

Let $X$ be a uniform random variable on $\{1,\dotsc, n\}$. Then $$ EX=\sum_{i=1}^n\frac{i}{n}\tag{0} $$ But it is clear that $n+1-X$ and $X$ have the same distribution whence $$ EX=E(n+1-X)=n+1-EX $$ whence $$ EX=\frac{n+1}{2}. $$ Note that we immediately see that $$ \sum_{i=1}^ni=\frac{n(n+1)}{2} $$ from $(0)$.

Answer 2

In this particular example, note that:

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

So,

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

You can prove $(1)$ quite simply:

$$S_n = \color{blue}{0}\color{green}{+1}\color{purple}{+2}+…+n$$

$$S_n = (n\color{blue}{-0})+(n\color{green}{-1})+(n\color{purple}{-3})+…+1$$

Adding these two equivalent equations, you can see the simplifications which will occur (shown in color for emphasis), leaving just $n$’s. Notice that this occurs from $0$ to $n$, so there will be $(n+1)$ $n$’s added after addition. This immediately leads to the formula:

$$2S_n = (n+1)(n) \iff S_n = \frac{n(n+1)}{2}$$

Answer 3

A solution is to use binomial coefficient properties: $$\sum_{i=1}^n i = \sum_{i=1}^n {i \choose 1} = {n+1 \choose 2} = \frac{n(n+1)}{2}$$ The same method can be used to calculate the sum for higher order terms