if summation of $i$ is $(n(n+1))/2$ what happens when you change the range?

Question

I understand: $$\sum\limits^n_{i=1} i = \frac{n(n+1)}{2}$$ what happens when we restrict the range such that: $$\sum\limits^n_{i=n/2} i = ??$$

Originally I thought we might just have $\frac{n(n+1)}{2}/2$ but I know that's not correct since starting the summation at n/2 would be the larger values of the numbers between $1..n$

Answer 1

No matter what sequence you're adding up (i.e. no matter what $a_i$ is), so long as $m \lt n$ we know that $$\sum^{m-1}_{i = 1} a_i + \sum_{i = m}^n a_i = \sum_{i = 1}^n a_i$$

so we can bring the first term over to the right and side and get

$$\sum_{i = m}^n a_i = \sum_{i = 1}^n a_i - \sum^{m-1}_{i = 1} a_i$$

Can you figure out how to apply this to your situation?

Answer 2

If $n$ is even of the form $2p$, the sum is $$(p+0)+(p+1)+(p+2)+...+(p+n-p)=$$

$$p(n-p+1)+1+2+3+...(n-p)=$$

$$p(n-p+1)+\frac{(n-p)(n-p+1)}{2}=$$

$$\frac{(n-p+1)(n+p)}{2}$$

If $n$ is odd of the form $2p-1$, we get the same sum.

Answer 3

Asymptotic solution: the difference, let's call it $S_d = S_1 - S_2$ can be obtained by taking the largest term in each sum, i.e. $\frac{n(n+1)}{2}$ and $\frac{n(n+2)}{8}:$ $$ S_d = \frac{n(n+1)}{2} - \frac{n(n+2)}{8} = \frac{3 n^2}{8} + \frac{n}{4} = O(n^2) $$ so asymptotically the difference is of the same order as both sums.