Sigma notation in regards to computer science time complexities

Question

I have been attempting to solve this problem for a while now, but I am not sure how to truly start it.

$\sum\limits_{i=1}^N (2i-1) = N^2 $

So far I have found that $\sum\limits_{i=1}^N (2i-1) = (2(1)-1) + (2(2)-1) .... (2(N)-1) $

But this does not lead me any closer to finding the $N^2$ that I'm in the process of attempting to find.

Answer 1

\begin{align}\sum_{i=1}^N (2i-1)&= 2\sum_{i=1}^Ni-\sum_{i=1}^N1\\ &= 2\left( \frac{N(N+1)}{2}\right)-\sum_{i=1}^N1\end{align}

Alternatively, view the sum as an arithmetic progression with difference $2$.

Answer 2

I think the best approach here is to learn a thing called induction.

First, notice that the statement is true for $n=1$: $1 = 1^2$

Then you assume the inductive hypothesis ie that the statement is true for $n$. Now, prove that its true for $n+1$, using that assumption.

So, the statement for $n$ is $\sum\limits_{i=1}^n (2i-1) = n^2$, and we're going to assume this.

Now,

$$ \sum\limits_{i=1}^{n+1} (2i-1) = 2(n+1) -1 +\sum\limits_{i=1}^{n} (2i-1) = 2n + 1 + n^2 = (n+1)^2$$

The first step is just how addition and the sigma notation works, we used our assumption in the second step, and tidied the algebra up in the third and final step, which gave us our result, that if its true for $n$ its true for $n+1$.

So, we know its true for $1$, and if its true for $n$ its true for $n+1$, and you can sort of see how this implies its true for 2, or 20 or 2 million, or any number.

This is mathematical induction, and it proves your result quite nicely.