Direct Proof that $1 + 3 + 5 + \cdots+ (2n - 1) = n\cdot n$

Solution 1:

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.

Solution 2:

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