2
$\begingroup$

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

  • 0
    Yes Matt, that's what I've done. I think I am having a problem with simplifying2012-02-19

4 Answers 4

11

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$

  • 0
    @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.2012-02-19
4

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.

4

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.

  • 0
    That is right Chonoles do you know any work about the sums $\sum i^p$?2012-02-20
4

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