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). $$
 A: 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.
A: 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.
A: $$
\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*}
$$
A: 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$
