# Convert Summation into Formula

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*}

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)$$

• Thanks for this, I am still reading the wiki page, but just to verify, if that is a formula that is always through, how do I prove to someone that doing that summation will always give k(k+1)/2 – James Okpe George Jun 25 '18 at 13:34
• @JamesOkpeGeorge See the edit, it always holds – caverac Jun 25 '18 at 13:40

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}$.

• Thanks so much @InterstellarProbe, that was good – James Okpe George Jun 25 '18 at 13:57
• Sadly I could not pick two response as answer – James Okpe George Jun 25 '18 at 14:05