Prove that $1 + 4 + 7 + · · · + 3n − 2 = \frac {n(3n − 1)}{2}$

Prove that $$1 + 4 + 7 + · · · + 3n − 2 = \frac{n(3n − 1)} 2$$

for all positive integers $n$.

Proof: $$1+4+7+\ldots +3(k+1)-2= \frac{(k + 1)[3(k+1)+1]}2$$
$$\frac{(k + 1)[3(k+1)+1]}2 + 3(k+1)-2$$

Along my proof I am stuck at the above section where it would be shown that:

$\dfrac{(k + 1)[3(k+1)+1]}2 + 3(k+1)-2$ is equivalent to $\dfrac{(k + 1)[3(k+1)+1]}2$

Any assistance would be appreciated.

Solution 1:

Non-inductive derivation:

\begin{align} \sum_{k=1}^n(3k-2) &= \sum_{k=1}^n3k -\sum_{k=1}^n2\\ &= 3\left(\sum_{k=1}^n k\right) -2n\\ &= \frac{3(n)(n+1)}{2} - \frac{4n}{2}\\ &=\frac{3n^2-n}{2}\\ &= \frac{n(3n-1)}{2}\\ \end{align}

This, of course, relies on one knowing the sum of the first $n$ natural numbers, but that's a well-known identity.

Solution 2:

Sum of the first and last terms = $1 + (3n-2) = 3n-1$

Sum of 2nd and (n-1)th terms = $4 + (3n-5) = 3n-1$

Sum of 3rd and (n-2)th terms = $7 + (3n-8) = 3n-1$

$...$

Sum of (n-1)th and 2nd terms = $(3n-5) + 4 = 3n-1$

Sum of n-th (last) and 1st terms = $(3n-2) + 1 = 3n-1$

Add both sides up .
$(1+4+...+(3n-2)) + (1+4+...+(3n-2)) = n(3n-1)$

which means:
$2(1+4+...+(3n-2)) = n(3n-1)$
or

$1+4+...+(3n-2) = n(3n-1)/2$

Solution 3:

The base case is trivial, now we follow to the inductive step by asuming the induction hypothesis and proving for $n + 1$. So:

\begin{align*} 1 + 4 + 7 + ... + 3n-2 + 3(n+1)-2 & = \frac{n(3n-1)}{2} + 3(n+1)-2\\ & = \frac{n(3n-1)}{2} + \frac{2(3(n+1)-2)}{2}\\ & = \frac{3n^{2}-n+6n+6-4}{2}\\ & = \frac{3n^{2}+5n+2}{2}\\ & = \frac{(n+1)(3n+2)}{2}\\ & = \frac{(n+1)(3(n+1)-1)}{2} \end{align*} And we are done. The important thing is to know when to apply the induction.

Solution 4:

Call $S = 1 + 4 + \ldots + [3n-2]$.

Add the numbers in reverse direction: $S = [3n-2] + [3n-5] + \ldots + 1$.

Add the two equations term by term: $2S = (1 + [3n-2]) + (4 + [3n - 5]) + \ldots + ([3n-2]+1) = n (3n-1)$.

Solution 5:

The formula must be a quadratic polynomial (because its first order difference is a linear polynomial) and has three independent coefficients. It suffices to identify for three different values of $n$:

$$\begin{align}1=\frac{1(3\cdot1-1)}2 \\1+4=\frac{2(3\cdot2-1)}2 \\1+4+7=\frac{3(3\cdot3-1)}2\end{align}$$ This completes the proof for any $n$ !