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

Question

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.

Answer 1

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.

Answer 2

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.

Answer 3

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$

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

Answer 5

Here is @Shooter's answer shown a different way. Let's take the example of n = 8:

1 + 4 + 7 + 10 + 13 + 16 + 19 + 22 = 92

Let's rearrange this and group:

(1 + 22) + (4 + 19) + (7 + 16) + (10 + 13) = 92

Now let's add the groups and look for a pattern:

23 + 23 + 23 + 23 = 92

That's it. The n = 8 example is just what happens when you add 23 four times. What is 23? It's 3n - 1. What is four? It's n / 2.

That makes the formula (3n - 1)(n / 2). This is how I would derive this when n is even. It's a little more work when n is odd.

---

Here's another simple solution that only uses this formula:

1 + 2 + 3 + ... + n = n * (n + 1) / 2

We'll call this f(n) for now. I'll decompose the original series:

(a)   1 + 2 + 3 + 4 ...
(b) + 0 + 1 + 2 + 3 ...
(c) + 0 + 1 + 2 + 3 ...
-------------------
(d) = 1 + 4 + 7 + 10 ...

It should be clear from the above how to make a closed form equation:

(a) = f(n)
(b) = f(n - 1)
(c) = f(n - 1)

Therefore

(d) = f(n) + 2 * f(n - 1)

The formula (d) can be rewritten to what you posted in your question

Answer 6

On a square lattice (the integer points on a Cartesian grid), draw the triangle with vertices at:

(1,1) (n,1) (n, 3n-2)

Observe that the number of points on or in the triangle is, counting columns from the left, 1 + 4 + ... + 3n-2.

Make a rotated copy of this triangle exactly 1 unit above it, i.e.

(1,2) (1, 3n-1) (n, 3n-1)

Observe that the two congruent triangles cover the rectangle of points from (1,1) to (n, 3n-1), which includes n(3n-1) points. The number of points in the original triangle is therefore:

$$ \frac{n(3n-1)}{2} $$

(Reality check: if n odd, 3n-1 is even, so division is OK.)

Answer 7

Isn't this a super-standard arithmetic progression? https://en.wikipedia.org/wiki/Arithmetic_progression

In your case:

first = element(1) = 1

element(N) = 3N-2

Sum of N first elements of arithmetic progression is N(first+element(N))/2 which is... N(1+ 3N-2)/2

What's to prove here? Or are you trying to prove the general equation for a sum of first N elements of arithmetic progression?

Answer 8

let f(n)=3n-2
let s(n)=[f(1)+f(2)+f(3)+...+f(n-1)+f(n)]

s(n)    =(3(1)-2)+(3(2)-2)+(3(3)-2)+...+(3(n-1)-2)+(3(n)-2)
s(n)    =(3(1)   + 3(2)   + 3(3)   +...+ 3(n-1)   + 3(n)  )-2n
s(n)    = 3(1    +   2    +   3    +...+  (n-1)   +   n   )-2n
s(n)    =3(sum of all #s from 1 to n)       -2n
s(n)    =3(sum of all #s from 1 to n-1)+3(n)-2n
s(n)    =3(sum of all #s from 1 to n-1)+n

Now we reverse the order:

s(n)    =3((n-1)+(n-2)+...3+2+1+(n-n))+n
s(n)    =3(n^2)-3(sum of all #s from 1 to n)+n
s(n)    =3(n^2)-3(sum of all #s from 1 to n)+n+n-n
s(n)    =3(n^2)-3(sum of all #s from 1 to n)+2n-n
s(n)    =3(n^2)-3(sum of all #s from 1 to n)-(-2n)-n
s(n)    =3(n^2)-[3(sum of all #s from 1 to n)-2n]-n

We've got another value for s(n) on the right side now.

s(n)    =3(n^2)-[s(n)]-n
2[s(n)] =3(n^2)-n
2[s(n)] =n(3n)-n(1)
2[s(n)] =n(3n-1)
s(n)    =n(3n-1)/2

Answer 9

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$ !

Answer 10

The solution must be a quadratic polynomial (because its first order difference is a linear polynomial) so it is obtained with the Lagrangian formula on three points. Taking $(0,0),(1,1),(2,5)$,

$$0\frac{(n-1)(n-2)}{(0-1)(0-2)}+1\frac{(n-0)(n-2)}{(1-0)(1-2)}+5\frac{(n-0)(n-1)}{(2-0)(2-1)}=\frac{n(3n-1)}2.$$

Answer 11

Put:

$$f(x) = \sum_{k=0}^{n-1}\exp\left[(3 k +1)x\right]=\exp(x)\frac{\exp(3 n x)-1}{\exp(3 x)-1}$$

If we expand $f(x)$ in a series expansion around $x=0$, then the coefficient of $x$ will give us the desired summation. We can do this as follows, we put:

$$g(x) = \log\left[f(x)\right] = x + \log\left[\exp(3 n x)-1\right]-\log\left[\exp(3x)-1\right]$$

Series expansion around $x = 0$ to order $x$ yields:

$$g(x) = x + \log\left(3 n x + \frac{9 n^2x^2}{2}+\cdots\right) -\log\left(3 x + \frac{9 x^2}{2}+\cdots\right)$$

$$=x + \log(n) + \log\left(1+\frac{3nx}{2}+\cdots\right)- \log\left(1+\frac{3x}{2}+\cdots\right)$$

$$=\log(n) + \frac{3 n -1}{2} x+\cdots$$

Therefore:

$$f(x) = \exp\left[g(x)\right] = n\exp\left(\frac{3 n -1}{2} x+\cdots\right)=n + \frac{n(3 n -1)}{2} x+\cdots$$