# Solution

Prove the following statement holds for every positive integer $n$:

$$\displaystyle{\sum_{i=1}^{n} (2i-1)^2 = \frac{4n^3-n}{3}}$$

One Solution:

Let us argue by induction...

Starting with the basis step, we must show that the statement holds for the smallest value of $n$ that we wish to consider.

Since we seek to prove the statement holds for every positive integer, then the smallest value we wish to consider would be $n=1$.

When $n=1$, the left side collapses to a "sum" containing only a single term: $$\sum_{i=1}^n (2i-1)^2 = (2\cdot1-1)^2 = 1^2 = 1$$

While on the right side, if $n=1$, $$\frac{4n^3-n}{3} = \frac{4 \cdot 1^3 - 1}{3} = \frac{3}{3} = 1$$

Since the left and right sides agree in value, the statement is true when $n=1$

Now we proceed with the inductive step, where we must show that if we know the statement holds for some particular value of $n$, say $n=k$, then the statement must also hold when $n=k+1$.

Equivalently for this problem, we need to show if the following "inductive hypothesis" is true $$\sum_{i=1}^k (2i-1)^2 = \frac{4k^3-k}{3}$$ then it must also be true that $$\sum_{i=1}^{k+1} (2i-1)^2 = \frac{4(k+1)^3-(k+1)}{3}$$

To this end, we will attempt to manipulate independently the left and right sides of the above equation until they appear identical. We can use the inductive hypothesis to provide a transition from an expression involving $\sum$ to a simpler algebraic expression.

First we work with the left side...

$$\begin{array}{rcl} \sum_{i=1}^{k+1} (2i-1)^2 &=& \left( \sum_{i=1}^{k} (2i-1)^2 \right) + (2(k+1)-1)^2\\\\ &=& \frac{4k^3-k}{3} + (2(k+1)-1)^2\\\\ &=& \frac{4k^3-k}{3} + (2k+1)^2\\\\ &=& \frac{1}{3} [4k^3 - k + 3(2k+1)^2]\\\\ &=& \frac{1}{3} [4k^3 - k + 3(4k^2 + 4k + 1)]\\\\ &=& \frac{1}{3} (4k^3 + 12k^2 + 11k + 3)\\\\ \end{array}$$

Now we work with the right side...

$$\begin{array}{rcl} \frac{4(k+1)^3-(k+1)}{3} &=& \frac{1}{3}[4(k+1)^3 - (k+1)]\\\\ &=& \frac{1}{3} [4(k^3 + 3k^2 + 3k + 1) - (k+1)]\\\\ &=& \frac{1}{3} (4k^3 + 12k^2 + 11k + 3)\\\\ \end{array}$$

Finding these two expressions equal to the same expression, they must be equal to each other. In other words, $$\sum_{i=1}^{k+1} (2i-1)^2 = \frac{4(k+1)^3-(k+1)}{3}$$ which is what we needed to show.

Having met with success in both the basis and inductive steps, we are free to conclude by the principle of mathematical induction, that the following is true for every positive integer $n$: $$\sum_{i=1}^{n} (2i-1)^2 = \frac{4n^3-n}{3}$$

QED.

A Second Solution:

If we are allowed to appeal to the following facts: $$\sum_{i=1}^{n} i = \frac{n(n+1)}{2} \quad \textrm{and} \quad \sum_{i=1}^{n} i^2 = \frac{n(n+1)(2n+1)}{6}$$ then we can argue the result directly with the following: $$\begin{array}{rcl} \sum_{i=1}^{n} (2i-1)^2 &=& \sum_{i=1}^{n} (4i^2 - 4i + 1)\\\\ &=& \left[\sum_{i=1}^{n} 4i^2 \right] - \left[\sum_{i=1}^{n} 4i \right] + \left[\sum_{i=1}^{n} 1 \right]\\\\ &=& 4 \left[\sum_{i=1}^{n} i^2 \right] - 4 \left[ \sum_{i=1}^{n} i \right] + n\\\\ &=& 4 \left[\frac{n(n+1)(2n+1)}{6} \right] - 4 \left[ \frac{n(n+1)}{2} \right] + n\\\\ &=& \frac{2n(n+1)(2n+1)}{3} - \frac{6n(n+1)}{3} + \frac{3n}{3}\\\\ &=& \frac{4n^3+6n^2+2n-6n^2-6n+3n}{3}\\\\ &=& \frac{4n^3-n}{3}\\\\ \end{array}$$ QED.