Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It only takes a minute to sign up.
Sign up to join this community
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.
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.
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$
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.
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)$.
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$ !
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
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?
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.)
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
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$$
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.$$
