15
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ Such an easy question $15$ upvotes??? $\endgroup$ – Archis Welankar Apr 1 '16 at 9:29

11 Answers 11

34
$\begingroup$

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.

$\endgroup$
  • 1
    $\begingroup$ Like it... Simple and direct. That brings the direct generalizaion that if we consider the sum of terms like $ak+b$ you would get the result as $n/2(an+a+2b)$ if I have not done a mistake calculating mentally the sum ;-) $\endgroup$ – Umberto Dec 5 '14 at 13:47
22
$\begingroup$

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$

$\endgroup$
  • 6
    $\begingroup$ This is a 'schoolboy Gauss' proof, nice. $\endgroup$ – PatrickT Dec 4 '14 at 8:45
12
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ I see the pattern its brilliant , any tips on how you can familiarize yourself with this use of application. $\endgroup$ – IT ken Dec 4 '14 at 2:41
  • $\begingroup$ Mmmm, well, most of the times you should use the induction hypothesis, also when you are stuck do it backwards. May sound weird, but what I mean is: Try to unravel(???) the thing that you want to get to and break into something easier to get. For example in this case it requires certain factorization, so expand the last terms. It's easier to reach there that way, and then simplify. I think those are the most useful tips. Ah! Also, a lot of practice. $\endgroup$ – Diego Robayo Dec 4 '14 at 2:44
  • $\begingroup$ "Also a lot of practice" lol, indeed. Thanks alot $\endgroup$ – IT ken Dec 4 '14 at 2:49
  • $\begingroup$ A lot of it is just keeping really good account of what is assumed in the inductive step and what is to be proved. Here you can see that we can assume the sum of the numbers up through $3n-2$ is $\frac{n(3n-1)}{2}$, and this fact is used in the very first equation. The rest of the work is to show that when you add the next term ($3(n+1) - 2$) to this, are able to show the fact that is to be proved, which is that the sum of terms through $3(n+1) - 2$ is equal to that expression on the last line. $\endgroup$ – David K Dec 4 '14 at 3:23
8
$\begingroup$

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

$\endgroup$
4
$\begingroup$

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

$\endgroup$
  • $\begingroup$ Actually, as the formula is obviously true for $n=0$, it suffices to check for $1$ and $2$ ! $\endgroup$ – Yves Daoust Dec 5 '14 at 16:10
3
$\begingroup$

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

$\endgroup$
3
$\begingroup$

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?

$\endgroup$
2
$\begingroup$

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

$\endgroup$
2
$\begingroup$
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
$\endgroup$
  • $\begingroup$ I did this one using only basic algebraic principles, like factoring, adding and subtracting the same value to one side, or adding the same value to both sides, etc. $\endgroup$ – Dan Henderson Dec 5 '14 at 15:54
2
$\begingroup$

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

$\endgroup$
2
$\begingroup$

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

$\endgroup$

Not the answer you're looking for? Browse other questions tagged or ask your own question.