# 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).$$

-
Can you please show us what steps you have taken so we can try and help you more? –  ridecar2 Feb 19 '12 at 22:49
$\displaystyle \sum_{i=1}^{n+1} (3i - 1)^2 = \sum_{i=1}^n (3i-1)^2 + (3(n+1)-1)^2$. You can now use the inductive step. –  Matt Feb 19 '12 at 22:50
Yes Matt, that's what I've done. I think I am having a problem with simplifying –  AkshaiShah Feb 19 '12 at 22:50

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$

-
Thanks a lot Arturo. I owe you for this –  AkshaiShah Feb 19 '12 at 23:02
@user1148677: The algebraic manipulations may seem unnatural. The key is that we know what the answer "should" be, so we manipulate towards that aim. We know it should be an expression "in $(k+1)$", so it is natural to try to write it as one; hence the sixth and following lines of the equality sequence. –  Arturo Magidin Feb 19 '12 at 23:04

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.

-
Thanks very much :) –  adil Feb 20 '12 at 21:56
Glad to help, Adil. Downvoter, care to explain? –  Zev Chonoles Feb 20 '12 at 22:12
@chessmath: You're incorrect. $$9\sum_{i=1}^n i^2 = 3n^3+\frac{9}{2}n^2+\frac{3}{2}n$$ $$-6\sum_{i=1}^n i = -3n^2-3n$$ $$\sum_{i=1}^n 1 = n$$ Add them up and you get $$3n^2+\frac{3}{2}n^2-\frac{1}{2}n = \left(\frac{1}{2}n\right)(6n^2+3n^2-1)$$ as I (and the original problem, and all the other answers here) claim. –  Zev Chonoles Feb 20 '12 at 22:43
$$\sum_{i=1}^n i^2=\frac{1}{6}(n(n+1)(2n+1))=\frac{1}{3}n^3+\frac{1}{2}n^2+\frac{1}{6}n$$ Multiplying by 9, we get $$3n^3+\frac{9}{2}n^2+\frac{3}{2}n$$ –  Zev Chonoles Feb 20 '12 at 22:53
That is right Chonoles do you know any work about the sums $\sum i^p$? –  checkmath Feb 20 '12 at 23:41

\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*}

-