# Prove by induction (formula for $\sum^n(3i-1)^2$)

Anyone knows how to do this? The answer I’m getting is not correct.

Prove by induction that, for all integers $n\ge1$, $$\sum_{i=1}^n (3i-1)^2 = \frac12 n(6n^2 + 3n – 1).$$

Thanks

This Is what I have managed to get. After this I think I’m doing something wrong:
$$\frac12 n(6n^2 + 3n – 1 + 6n + 4) (3n +2).$$

#### Solutions Collecting From Web of "Prove by induction (formula for $\sum^n(3i-1)^2$)"

You prove it the usual way:

Base. Establish the result for $n=1$.

If $n=1$, then the left hand side is
$$\sum_{i=1}^1(3i-1)^2 = (3(1)-1)^2 = 4,$$
and the right hand side is
$$\frac{1}{2}(1)\left(6(1)^2 + 3(1) – 1\right) = \frac{1}{2}(8) = 4.$$
So we have equality.

Inductive Step.

Induction Hypothesis. The result holds for $k$; that is,
$$\sum_{i=1}^k(3i-1)^2 = \frac{1}{2}k(6k^2 + 3k – 1).$$

To prove. The result holds for $k+1$.
\begin{align*} \sum_{i=1}^{k+1}(3i-1)^2 &= \left(\sum_{i=1}^k(3i-1)^2\right) + (3(k+1)-1)^2\\ &= \frac{1}{2}k(6k^2+3k-1) + (3(k+1)-1)^2 &\text{(by the Induction Hypothesis)}\\ &=\frac{1}{2}k(6k^2+3k-1) + (3k+2)^2\\ &=\frac{1}{2}k(6k^2+3k-1) + (9k^2 + 12k+4)\\ &= \frac{1}{2}\left(6k^3 + 3k^2 – k + 18k^2 + 24k + 8\right)\\ &= \frac{1}{2}\left(6k^3 + 21k^2 + 23k + 8\right)\\ &=\frac{1}{2}\left(6(k^3 + 3k^2 + 3k + 1) + 3k^2 + 5k + 2\right)\\ &=\frac{1}{2}\left(6(k+1)^3 + 3(k^2 + 2k + 1) -k – 1\right)\\ &=\frac{1}{2}\left(6(k+1)^3 + 3(k+1)^2 – (k+1)\right)\\ &=\frac{1}{2}(k+1)\left(6(k+1)^2 + 3(k+1) – 1\right). \end{align*}
As this is exactly what we needed to show for $k+1$, this proves the inductive step.

Conclusion. The given formula holds for $n=1$; and if it holds for $k$, then it also holds for $k+1$. By mathematical induction, the given formula holds for all positive integers $n$. $\Box$

Hint: use telescopy, i.e. a very simple telescopic induction proof yields

$$\rm\ f(n)\ =\ \sum_{i\: =\: 1}^n\:\ (3i-1)^2\ \ \iff\ \ \ f(n) – f(n-1)\ =\ (3n-1)^2,\quad\ f(0) = 0$$

So the proof reduces to showing that $\rm\:f(n) = n(6n^2 + 3n – 1)/2\:$ satisfies the RHS equations. Clearly $\rm\:f(0) = 0$. The other equality is between two quadratics, so to prove it we need only show they are equal at $3$ points, say $\rm\:n = 0,1,2.\:$ Since $\rm\:f(-1)=-1,\:f(0)=0,\:f(1)=4,\:f(2)=29$

$\rm\qquad\qquad n=0:\quad f(0)-f(-1)= 0-(-1) =\: (3\cdot 0-1)^2$

$\rm\qquad\qquad n=1:\quad f(1)\ -\ f(0)\:= 4\ \ -\ \ 0\ =\:\ (3\cdot 1 -1)^2$

$\rm\qquad\qquad n=2:\quad f(2)\ -\ f(1)\:= 29\ -\ 4\: =\:\ (3\cdot 2 -1)^2\quad$ QED

Note that the above method yields a simple mechanical algorithm for constructing such proofs.

Check the statement for $n=1$ (this is the base case):

$$\sum_{i=1}^1(3i-1)^2=(3\cdot1-1)^2=2^2=\fbox{4}$$
$$\left(\frac{1}{2}(1)\right)(6\cdot1^2+3\cdot1-1)=\frac{1}{2}\cdot 8=\fbox{4}$$
So the statement is true for $n=1$!

Now we want to show that, any time the statement is true when $n=k$ (for some $k$), it will also necessarily be true when $n=k+1$.

So, let’s suppose the statement is true when $n=k$ (this is the induction hypothesis). That is, suppose
$$\sum_{i=1}^k(3i-1)^2=\left(\frac{1}{2}(k)\right)(6k^2+3k-1).\qquad(*)$$
Our goal is to show, using this hypothesis, that the statement is true when $n=k+1$; that is,
$$\sum_{i=1}^{k+1}(3i-1)^2=\left(\frac{1}{2}(k+1)\right)(6(k+1)^2+3(k+1)-1).\qquad (**)$$
Observe that the difference between the left sides of equations $(*)$ and $(**)$ is
$$\left(\sum_{i=1}^{k+1}(3i-1)^2\right)-\left(\sum_{i=1}^k(3i-1)^2\right)=(3(k+1)-1)^2.$$
We are assuming that equation $(*)$ is valid; so $(**)$ can only be true if the difference on the right sides is also equal to this quantity. That is, in order to conclude that the statement is true for $n=k+1$, we must show that
$$\left(\frac{1}{2}(k+1)\right)(6(k+1)^2+3(k+1)-1)=\left(\frac{1}{2}(k)\right)(6k^2+3k-1)+(3(k+1)-1)^2$$
Expanding out, this is clear. Thus, we have proved the base case (true for $n=1$), and the induction step (true for $n=k$ implies true for $n=k+1$), so the statement is true by induction.

\begin{align*} \sum_{i=1}^n (3i-1)^2 &= \sum_{i=1}^n \left( (9i)^2 -6i +1 \right)\\ &= 9 \frac{n(n+1)(2n+1)}{6} – 6\frac{n(n+1)}{2} + n\\ &= 3n(n+1) \left( \frac{2n+1}{2} -1 \right) +n \\ &= 3n(n+1) \left( \frac{2n-1}{2} \right) +n \\ &= \frac{3n(n+1)(2n-1)+2n}{2}\\ &= n \left(\frac{6n^2+3n-1}{2} \right)\\ &= 3n^3+\frac{3n^2}{2}-\frac{n}{2}\\ \end{align*}