1

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.

kyle newton
  • 15

2 Answers2

0

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

Siong Thye Goh
  • 149,520
  • 20
  • 88
  • 149
  • I'm not quite sure where you happened to get the $2\left( \frac{N(N+1)}{2}\right)$ because I'm not sure how we can convert between the sigma notation and the fraction you gave. – kyle newton Sep 04 '18 at 01:36
  • hmm... have you learn arithmetic progression? – Siong Thye Goh Sep 04 '18 at 01:38
  • Not explicitly. I am currently taking first semester calculus and Discrete Mathematics, but also a data structure class, which this problem is from. I've been looking at arithmetic progression in the time since you answered my question, but I do not quite have a grasp on it yet. – kyle newton Sep 04 '18 at 01:42
  • some warm up reading – Siong Thye Goh Sep 04 '18 at 01:46
  • Thank you for the help and clarification. I believe that this should be able to help me finish solving this problem. – kyle newton Sep 04 '18 at 01:49
0

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.

user24142
  • 3,732