Convert Summation into Formula

Question

I have the formula for finding the average time of an linear search algorithm as below

\begin{equation*} AT\ =\frac{\ \sum ^{n+1}_{i\ =\ 1} \ \theta ( i)}{n+1}. \end{equation*}

The above formula was simplified to become the one below, I am not sure how it was moved from that to this. Any help? \begin{equation*} AT\ =\ \frac{\theta (( n\ +\ 1) \ \times \ ( n\ +\ 2) \div 2)}{n\ +\ 1}. \end{equation*}

Answer 1

A linear operator satisfies the following property:

$$\theta(a)+\theta(b) = \theta(a+b)$$

This means that:

$$\sum_{i=1}^{n+1}\theta(i) = \theta\left( \sum_{i=1}^{n+1} i \right)$$

caverac answered about that summation yielding $\dfrac{(n+1)(n+2)}{2} = \dbinom{n+2}{2}$.

Answer 2

You can follow this link for a detailed explanation, but in short

$$ 1 + 2 + \cdots + k = \frac{k(k + 1)}{2} $$

In your case $k = n + 1$

---

EIDT

Proof:

Call $S = 1 + 2 + \cdots + (k - 1) + k $, note that you can also write it in reverse order $S = k + (k - 1) + \cdots + 2 + 1 $, so that

\begin{array}{} S &=& 1 &+& 2 &+\cdots+& (k-1) &+& k\\ S &=& k &+& (k-1) &+\cdots+& 2 &+& 1\\ \hline 2S &=& (k+1) &+& (k+1) &+\cdots+& (k+1) &+& (k+1) \end{array}

So you have

$$ 2S = k (k + 1) $$