Proving that $1\cdot3+3\cdot5+5\cdot7+\cdots+(2n-1)(2n+1)={n(4n^2+6n-1) \over 3}$ by induction for $n\geq 1$

Prove using mathematical induction that

$$1\cdot3+3\cdot5+5\cdot7+\cdots+(2n-1)(2n+1)= {n(4n^2+6n-1) \over 3}.$$

Step 1: If we assume that the equation is true for a natural number, $$n=k$$, then we get

$$1\cdot3+3\cdot5+5\cdot7+\cdots+(2k-1)(2k+1)= {k(4k^2+6k-1) \over 3}$$

Step 2: When a statement is true for a natural number $$n = k$$, then it will also be true for its successor, $$n=k+1$$. Hence, we have to prove that it is also true for $$n=k+1$$.

$$1\cdot3+3\cdot5+5\cdot7+\cdots+(2k-1)(2k+1)+(2k+1-1)(2k+1+1) = {k(4k+1^2+6k+1-1) \over 3}$$

I replace the LHS by step 1.

$${k(4k^2+6k-1) \over 3} + 2(k+1-1)(2k+1+1)={k(4k+1^2+6k+1-1) \over 3}$$

Now I need to make LHS equal to RHS.

• Are you able to show that the above is true for $n=1$? Jul 26, 2015 at 18:15
• For $n=2$ LHS gives $18$ while RHS gives $36$. Did you mean $n^2$ instead $4^2$? Jul 26, 2015 at 18:17
• Have you tried anything? What are your thoughts? I am somewhat tempted to write up an answer, but I am not sure which part it is you are struggling with exactly. The base case? Using the inductive hypothesis effectively? Algebraic manipulations? What exactly is giving you a problem here? Jul 26, 2015 at 19:03
• This description of Step 2, "When a statement is true for a natural number $n=k$, then it will also be true for its successor, $n=k+1$" is not correct. You have to start with the statement from Step 1 and deduce, using regular algebra steps, that a similar statement is true where each "$k$" has been replaced with "$(k+1)$". Your description sounds like you want to just swap out the "$k$" for the "$(k+1)$" right away. Jul 27, 2015 at 8:04

From the formula for the sum of the square of the first $n$ natural numbers we have \begin{align*} \sum_{k=1}^n(2k-1)(2k+1)&=\sum_{k=1}^n(4k^2-1)\\ &=4\sum_{k=1}^nk^2-\sum_{k=1}^n1\\ &=\frac{4n(n+1)(2n+1)}{6}-n\\ &=\frac{n\left[4(n+1)(2n+1)-6\right]}{6}\\ &=\frac{n(4n^2+6n-1)}{3} \end{align*}

For what it's worth, I think Mario's answer is definitely the most elegant, but I know you are trying to prove the relation by induction. Thus, I will outline a proof by induction.

Proof. For $n\geq 1$, let $S(n)$ denote the statement $$S(n) : \sum_{i=1}^n(2i-1)(2i+1)=\frac{n(4n^2+6n-1)}{3}.$$ Base step ($n=1$): $S(1)$ says that $(2-1)(2+1)=3=\frac{4+6-1}{3}$, and this is true.

Induction step ($S(k)\to S(k+1)$): Fix some $k\geq 1$ and assume that $$S(k) : \sum_{i=1}^k(2i-1)(2i+1)=\frac{k(4k^2+6k-1)}{3}$$ holds. To be shown is that $$S(k+1) : \sum_{i=1}^{k+1}(2i-1)(2i+1)=\frac{(k+1)[4(k+1)^2+6(k+1)-1]}{3}$$ follows.

Note: Later in the proof, it may help to first observe the following: $$(k+1)[4(k+1)^2+6(k+1)-1]=(k+1)(4k^2+14k+9)=4k^3+18k^2+23k+9\tag{\dagger}$$

Beginning with the left-hand side of $S(k+1)$, \begin{align} \sum_{i=1}^{k+1}(2i-1)(2i+1)&= \sum_{i=1}^k(2i-1)(2i+1)+\bigl(2(k+1)-1\bigr)\bigl(2(k+1)+1\bigr)\\[1em] &= \frac{4(k^2+6k-1)}{3}+(2k+1)(2k+3)\tag{by $S(k)$}\\[1em] &= \frac{k(4k^2+6k-1)+(12k^2+24k+9)}{3}\\[1em] &= \frac{4k^3+18k^2+23k+9}{3}\tag{simplify}\\[1em] &= \frac{(k+1)[4(k+1)^2+6(k+1)-1]}{3},\tag{by $(\dagger)$} \end{align} one arrives at the right-hand side of $S(k+1)$, completing the inductive proof.

By mathematical induction, the statement $S(n)$ is true for all $n\geq 1$. $\blacksquare$

You have this line: $$1\cdot3+3\cdot5+5\cdot7+\cdots+(2k-1)(2k+1)+(2k+1-1)(2k+1+1)$$$${}= {k(4k+1^2+6k+1-1) \over 3}$$

That should be: $$1\cdot3+3\cdot5+5\cdot7+\cdots+(2k-1)(2k+1)+(2(k+1)-1)(2(k+1)+1)$$$${} = {k(4k^2+6k-1) \over 3}+(2(k+1)-1)(2(k+1)+1)$$

First of all, I'm just doing literally the same thing to both sides of an already-assumed-to-be-true equation. I'm adding $(2(k+1)-1)(2(k+1)+1)$.

Second, the reason I've added this is because it is what the next term would look like. Not $(2k+1-1)(2k+1+1)$, which just inserted some "${}+1$" in some places.

From here, you need to give a common denominator to the right side and see that it works out to be ${(k+1)(4(k+1)^2+6(k+1)-1) \over 3}$.

The general idea is the following:

Step 1 Check that your identity holds true for $n=n_0$ (e.g 1)

Step 2 Assume that your identity holds true for $n=k>n_0$ and save the result.

Step 3 Explore if the identity holds true for $k+1$ using the result in step 2.

If step 1 holds true and by using step 2 you come up with a result that also holds true in step 3 then by induction your identity holds true for $n\geq n_0$