34
$\begingroup$

Prove that for all integers $n$, $n \geq 1$, $$1 + 3 + 5 + \cdots + (2n - 1) = n\cdot n$$

How would I go about proving this?

  • 6
    Normally, just use induction. Alternatively, show that $1 + (2n-1) + 3 + (2n-3) + 5 + (2n-5) + \cdots + (2n-3) + 3 + (2n-1) + 1 = 2n \cdot n$.2012-04-24
  • 1
    @Johannes's second proposal is of course the well-known trick (allegedly) due to Gauss...2012-04-24
  • 4
    @J.M. I don't think Gauss invented that trick, there's just a famous story (possibly apocryphal) about Gauss as a child finding that method.2012-04-24
  • 3
    **Hint** $\ $ By [telescopy](http://math.stackexchange.com/a/134925/242) it's equivalent to $\rm (n+1)^2 - n^2 = 2\:n+1.\:$ See Eric's answer for a geometric view.2012-04-24
  • 0
    @JamieB What do you mean by direct? What would an indirect proof use?2012-04-24
  • 0
    Slightly tangential (rather, "secantial"): You can use this fact to plot parabolas. Given the equation $y=x^2$, you can start at the vertex (the origin, $(0,0)$) and plot points by going "over $1$, up $1$; over $1$, up $3$; over $1$, up $5$; over $1$, up $7$; etc" --effectively, following the slopes of chained secant lines-- to get points of the form $(n,n^2)$. More generally, for $y-k =a (x-h)^2$, start at vertex $(h,k)$, and plot points as "over $1$, up $1a$; over $1$, up $3a$; over $1$, up $5a$; over $1$, up $7a$; etc".2012-04-24
  • 21
    Sometimes unmotivated questions without any work shown by the OP get all the love...2012-04-24
  • 2
    Yeah, why is this question so popular?2012-04-24
  • 3
    cuz its easy and people get to name-drop Gauss? who knows.2012-04-24

10 Answers 10

1

you can see this link in generally solution :

http://en.wikipedia.org/wiki/Arithmetic_progression

This section is about Finite arithmetic series. For Infinite arithmetic series, see Infinite arithmetic series.

The sum of the members of a finite arithmetic progression is called an arithmetic series.

Expressing the arithmetic series in two different ways:

$ S_n=a_1+(a_1+d)+(a_1+2d)+\cdots+(a_1+(n-2)d)+(a_1+(n-1)d)\\ S_n=(a_n-(n-1)d)+(a_n-(n-2)d)+\cdots+(a_n-2d)+(a_n-d)+a_n.$

Adding both sides of the two equations, all terms involving d cancel:

$ \ 2S_n=n(a_1+a_n).$

Dividing both sides by 2 produces a common form of the equation:

$ S_n=\frac{n}{2}( a_1 + a_n).$

An alternate form results from re-inserting the substitution:$ a_n = a_1 + (n-1)d:$

$ S_n=\frac{n}{2}(2a_1 + (n-1)d). $

124

Hint: When $n=5$, $$\boldsymbol{1+{\color{red}3}+{\color{green}5}+{\color{purple}7}+{\color{blue}9}=} $$ $$\begin{array}{ccccc} \blacksquare & {\color{red}\blacksquare} & {\color{green}\blacksquare} & {\color{purple}\blacksquare} & {\color{blue}\blacksquare}\\ {\color{red}\blacksquare} & {\color{red}\blacksquare} & {\color{green}\blacksquare} & {\color{purple}\blacksquare} & {\color{blue}\blacksquare}\\ {\color{green}\blacksquare} & {\color{green}\blacksquare} & {\color{green}\blacksquare} & {\color{purple}\blacksquare} & {\color{blue}\blacksquare}\\ {\color{purple}\blacksquare} & {\color{purple}\blacksquare} & {\color{purple}\blacksquare} & {\color{purple}\blacksquare} & {\color{blue}\blacksquare}\\ {\color{blue}\blacksquare} & {\color{blue}\blacksquare} & {\color{blue}\blacksquare} & {\color{blue}\blacksquare} & {\color{blue}\blacksquare} \end{array} $$

$$\boldsymbol{=5^2}.$$

Turn this into a general proof.

  • 10
    I'm pretty sure the associated diagram has already been posted somewhere in this site...2012-04-24
  • 5
    @J.M. I made my own in TeX with matrices and colors. How does it look? (I don't know where to find the original image)2012-04-24
  • 0
    @EricNaslund +1; Can you please also post the code?2012-04-24
  • 0
    @KannappanSampath: If you click edit, you can copy the code, and then just click cancel so that you don't actually edit anything. The matrix is about 700 characters, so i can't post its code in a single comment.2012-04-24
  • 1
    One doesn't have to click edit, just right click on the formula and choose "Show math as TeX commands".2012-04-24
  • 3
    By the way, interesting idea to use the "blacksquare" command for all those colored boxes. ;-)2012-04-24
  • 0
    @Eric My mistake--I thought it was an image. Sorry. And, thank you for letting me know.2012-04-24
  • 1
    @J.M. It has, but not with colors.2012-04-24
  • 2
    I am going to teach this to my young school students ! :)2013-01-11
79

(1) Proof using the "method of gauss":

$$\begin{eqnarray*} 2(1 + 3+ 5 + \ldots (2n-1)) &=&\big[ 1 + (2n-1)\big] + \big[3 + (2n-3)\big] + \ldots + \big[ (2n-1) + 1\big] \\ &=& \underbrace{2n + 2n + \ldots + 2n}_{\text{$n$ times}} \\ &= &2n(n). \end{eqnarray*}$$ Therefore it follows that $(1 + 3 + \ldots (2n-1)) = n\times n.$

(2) Proof by induction: Let $P(n)$ be the statement:

"For all positive integers $n$, $1 + 3 + \ldots + (2n-1) = n^2$."

For $n=1$ clearly $(2 \cdot 1) - 1 = 1\cdot 1$ so that $P(1)$ is true. So suppose the result holds for $n=k$, i.e. $P(k)$ is true. Since $P(k)$ is true, this means that we have the following equality when $n=k$:

$$1+ 3 + \ldots + (2k-1) = k^2.$$

If you add $2k+1$ to both sides of this equation, you get that

$$ \begin{eqnarray*} 1+ 3 + \ldots +(2k-1) + (2k+1) &=& k\cdot k + (2k+1) \\ &=& k^2 + 2k + 1 \\ &=& (k+1)(k+1) \end{eqnarray*}$$

showing that the result holds for $n=k+1$, i.e. $P(k+1)$ is true. Therefore by the Principle of Mathematical Induction, $1 + 3 + \ldots + (2n-1) = n\cdot n$ for all positive integers $n$.

(3) Suppose you only knew that the sum of $n$ consecutive integers is $n(n+1)/2$. Then

$$\begin{eqnarray*}1 +2 + \ldots + 2n &=& \frac{2n(2n+1)}{2}\\ \implies 1 + 3 + \ldots + (2n-1) &=& n(2n+1) - 2(1 + \ldots + n) \\ &=& 2n^2 + n - 2\left(\frac{n(n+1)}{2}\right) \\ &=& 2n^2 + n - n^2 - n \\ &=& n^2. \end{eqnarray*}$$

(4) Proof using telescoping sums (idea by Bill Dubuque):

$$\begin{eqnarray*} \sum_{k=1}^n 2k-1 &=& \sum_{k=1}^n k^2 - (k-1)^2 \\ &=& (1 - 0) + (2^2 -1 ) + \ldots + n^2 - (n-1)^ 2\\ &=& 1 + (-1 + 2^2) + (-2^2 + 3^2) + \ldots + (-(n-2)^2 + (n-1)^2) + (-(n-1)^2 + n^2)) \\ &=& n^2. \end{eqnarray*}$$

(5) Proof by method of differences (brute force): Let $a_n = \sum_{k=1}^n 2k-1$. Then we see that $a_1 =1 $, $a_2 = 4$, $a_3 = 9$, etc.

Now we look at the first differences $4 - 1 = 3$, $9- 4 = 5$, $16 - 9 = 7$, etc. Then when we look at the second difference, notice that it is constant: $5-3 = 2$, $7- 5= 2$, etc so we conjecture that

$$\sum_{k=1}^n 2k - 1 = an^2 + bn + c$$

where $a,b,c$ are constants to be determined. Plugging in $n = 1,2,3$ gives us a $3 \times 3$ linear system to solve, namely the linear system

$$\left[\begin{array}{ccc} 1 & 1 & 1 \\ 4 & 2 & 1 \\ 9 & 3 & 1 \end{array}\right]\left[\begin{array}{c} a \\ b \\ c \end{array}\right] = \left[\begin{array}{c} 1 \\ 4 \\ 9 \end{array}\right].$$

The determinant of the coefficient matrix is

$$\begin{eqnarray*} 1(2-3) - 1(4-9) + 1(12 - 81) &=& -1 + 5 - 69 \\ &\neq& 0 \end{eqnarray*}$$ so we have a unique solution. It is easy to see that $a = 1, b= 0, c=0$ is a solution to the linear system above. By the previous line, it is the only solution so we are done.

(6) Proof by a direct bash: Suppose you only knew that the sum of the first $n$ integers is $n(n+1)/2$. Then

$$\begin{eqnarray*} \sum_{k=1}^n 2k - 1 &=& \bigg(2\sum_{k=1}^n k \bigg) - \sum_{k=1}^n 1 \\ &=& 2\left(\frac{n(n+1)}{2}\right) - n\\ &=& n^2 + n -n\\ &=& n^2 \end{eqnarray*}.$$

  • 0
    Could someone say more about the construction of the coefficient matrix in (5)?2012-05-07
  • 0
    @Tony You plug in $n=1,2,3$ into the formula I gave above and you get the equations $a + b + c = 1$, $4a + 2b + c = 4$, and $9a +3b + c = 9$. I just put these simultaneous equations into matrix form.2012-05-07
  • 0
    While only #2 is labeled "by induction," it really should be said that all of these proofs use induction at some level. Far too many students are going around thinking that they hate induction and that they need to find ways to avoid it (even if avoiding it is futile.)2013-06-05
  • 0
    I'm curious as to where induction is applied in (5)?2013-10-19
  • 0
    Is Bill Dubuque, you mentioned in your post, is the one who is the member of Math.SE?2015-05-14
  • 0
    @SufyanNaeem Yes, he suggests it in a comment to the question.2017-08-27
22

The method of Gauss, graphically:

enter image description here

BTW: this corresponds to proof 1 in Benjamin's answer; and the graphic of Eric's answer corresponds to proof 4 (telescoping squares).

7

Proof that $n^2=1+3+5+\ldots+(2n-1)$ by subdividing the square of side $2n+1$ in two different ways:

<span class=$n^2=1+3+5+\ldots+(2n-1)$ using squares of side $(2n+1)^2$">

5

$$\begin{eqnarray*} (1 + 3 + 5 + ... + (2n - 1)) &=& (1 + 2 + 3 + ... + 2n) - (2 + 4 + ... + 2n)\\ &=& \sum_{i=1}^{2n}{i} - 2\sum_{i=1}^{n}{i}\\ &=& \frac{(2n)(2n+1)}{2} - 2\left(\frac{n(n+1)}{2}\right)\\ &=& n(2n+1) - n(n+1)\\ &=& n(2n + 1 - n - 1) = n^{2}\end{eqnarray*}$$

3

By inspection note that $1 = 1 \cdot 1$, that $1 + 3 = 2 \cdot 2$, and that $1 + 3 + 5 = 3 \cdot 3$.

Next, witness that the difference between any two successive perfect squares $(n - 1)^2$ and $n^2$ is a particular odd integer:

$n^2 - (n - 1)^2 \implies n^2 - (n^2 - 2n + 1) \implies 2n - 1$

Note that this is the very formula which you are summing to generate your series.

So for instance the difference between $3 \cdot 3$ and $2 \cdot 2$ is $2 \cdot 3 - 1 = 5$, corresponding to the $5$ in $3\cdot3 = 1 + 3 + 5$.

If the sum of the series generated so far is a square (shown by inspection), and the next term is from the series generated by $2n - 1$, then after this term is added, the sum must be the next square because the each term obeys the formula for the difference between two successive squares.

2

Consider this as the sum of a finite recursive series. Each element in the series is calculated from a fixed point a1=1 by adding 2 to the previous element. So, the equation for any arbitrary an is

$$a_{n} = [a_{n-1} + 2, a_{1} = 1] = 1 + 2(n-1)$$

The sum of n terms of this recursive series breaks down to:

$$\sum_{x=1}^{n}[ a_{x-1}+2, a_{1}=1] = 1 + (1 + 2) + ((1 + 2) + 2) + (((1 + 2) + 2) + 2) + \cdot\cdot\cdot + (1 + 2(n-1))$$

By inspection, we see that 1 occurs n times, once per term, and 2 occurs in a triangular fashion (each term contains one more 2 than the previous term). So, this condenses to the quantity of n plus double the (n-1)th triangular number (as the first term has zero 2s):

$$ \sum_{x=1}^{n}( a_{x-1}+2, a_{1}=1) = n + 2\frac{n(n-1)}{2} $$ $$ = n(n-1) + n $$ $$ = n^2 - n + n $$ $$ = n^2$$

QED.

2

Note that $(n+1)^2=n^2+2n+1$. This defines a recursive relationship between $n+1$ and $n$. This means that we can write the function $f(x)=x^2$ recursively as: $f(x)=f(x-1)+2x-1$ with $f(1)=1$. Now, simply expand out $f(x)$ to obtain $f(n)=\sum_{k=1}^{n}2x-1=n^2$.

2

A nice version of the inductive step is the following:

Using induction, the problem comes down to establishing the result that

$$ n^2=(n-1)^2+(2n-1) $$

Now it is easy to establish this by multiplying out the brackets, but I want to show you another way that I thought of one day. As an example, let $n-1=5$. Then:

\begin{align} 5^2+5 &= 5\times5+5=6\times5\\ 6\times5+6&=6\times6 \end{align}

So $6^2=5^2+5+6$. In general:

\begin{align} (n-1)^2+(n-1)&=(n-1+1)(n-1)=n(n-1)\\ n(n-1)+n&=n(n-1+1)=n^2 \end{align}

So $n^2=(n-1)^2+(n-1)+n=(n-1)^2+(2n-1)$.

Note: This answer is not intended to be particularly useful or even mathematically revealing. It is certainly not the most beautiful way of establishing the identity (the use of induction disqualifies it immediately), but I thought it was a nice way of showing the inductive step, without having to multiply out the brackets.