Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

I'm starting to understand how induction works (with the whole $k \to k+1$ thing), but I'm not exactly sure how summations play a role. I'm a bit confused by this question specifically:

$$ \sum_{i=1}^n 3i-2 = \frac{n(3n-1)}{2} $$

Any hints would be greatly appreciate

share|cite|improve this question
up vote 5 down vote accepted

Base case:

  • Let $n=1$ and test: $$\sum_{i=1}^1(3i-2)=3-2=1=\frac{1(3\cdot 1-1)}{2}$$

  • True for $n = 1$

Induction Hypothesis:

  • Assume that it is true for $k$: assume that $$\sum_{i=1}^k(3i-2)=\frac{k(3k-1)}{2}.$$

Inductive Step:

  • Prove, using the Inductive Hypothesis as a premise, that $$\sum_{i=1}^{k+1}(3i-2)=\left(\sum_{i = 1}^k(3i - 2)\right) + (3(k+1)-2) = \frac{(k+1)(3(k+1)-1)}{2}.$$
share|cite|improve this answer
So do I just manipulate the right side of the equation to try to get it to look like the original k(3k-1)/2 ? – K. Barresi Jan 25 '13 at 1:58
No, manipulate the inner third (in the equality chain of last line) to get the right hand side. You know, from the inductive hypothesis, what that the sum $$\left(\sum_{i = 1}^k(3i - 2)\right) = \frac{k(3k - 1)}{2}.$$ Add that to the term $3(k+1)- 2$ to obtain the right hand side. The right hand side is precisely the form you want to exhibit to show that the given sum holds for $k+1$ if it holds for $k$, hence, you will have proven, by induction, that for all $n$, $$ \sum_{i=1}^n 3i-2 = \frac{n(3n-1)}{2} $$ – amWhy Jan 25 '13 at 2:01
Ahh ok I think I understand now. Thank you for your help. – K. Barresi Jan 25 '13 at 2:19
Sorry to bug you again, but I appear to be stuck. I've reached: $$ (3k-2)+(3[k+1]-2)=\frac{k+1(3[k+1]-1)}{2} $$ which I simplified to $$ 12k-2=3k^2+5k+2 $$ – K. Barresi Jan 25 '13 at 4:05
That's exactly what you want: you want (k+1) in every spot where k occurs in the inductive hypothesis: i.e. you want the right hand side of my last line. That shows that what holds for k, holds when every k is replaced by (k+1): you want the same "form" as on the right hand side. – amWhy Jan 25 '13 at 4:12

For $n=1$ you have $\sum_{i=1}^1(3i-2)=3-2=1=\frac{1(3\cdot 1-1)}{2}$.

Suppose that $$\sum_{i=1}^n(3i-2)=\frac{n(3n-1)}{2}$$ and prove that $$\sum_{i=1}^{n+1}(3i-2)=\frac{(n+1)(3(n+1)-1)}{2}.$$

share|cite|improve this answer

I will prove it in two way for you:

1- Mathematical Induction:

If $n=1$ then the left side is $1$ and also the right side is $1$ too.

Now think that we have $\sum_{i=1}^{n}(3i-2)=\frac{n(3n-1)}{2}$, we should show $\sum_{i=1}^{n+1}(3i-2)=\frac{(n+1)(3(n+1)-1)}{2}$ that is $\sum_{i=1}^{n+1}(3i-2)=\frac{(n+1)(3n+2)}{2}$. But we can write; $$\sum_{i=1}^{n+1}(3i-2)=(\sum_{i=1}^{n}(3i-2))+(3(n+1)-2)=\frac{n(3n-1)}{2}+(3n+1)=\frac{3n^{2}-n+6n+2}{2}=\frac{3n^{2}+5n+2}{2}=\frac{3n^{2}+3n+2n+2}{2}=\frac{3n(n+1)+2(n+1)}{2}=\frac{(n+1)(3n+2)}{2}$$. And it finished our work.

2- Without Mathematical Induction:

We know $\sum_{i=1}^{k}i=\frac{k(k+1)}{2}$ and $\sum_{i=1}^{k}c=kc$ for a constant number "c".

Now $$\sum_{i=1}^{n}(3i-2)=3\sum_{i=1}^{n}i-\sum_{i=1}^{n}2=3\frac{n(n+1)}{2}-2n=\frac{n(3n+3-4)}{2}=\frac{n(3n-1)}{2}$$.

share|cite|improve this answer

If we mimic amWhy's proof for a general summation we obtain a powerful result.

$$ \sum_{i=1}^n f(i) = g(n)$$

Base case:

  • Let $n=1$ and test: $$\sum_{i=1}^1 f(i) = f(1) \color{#c00}{=?}\ g(1)$$

  • The $ $ Base Case $\ \,n = 1\ $ holds true $\iff \color{#C00}{f(1) = g(1)}$

Induction Hypothesis:

  • Assume that it is true for $\, n = k$: assume that $$\sum_{i=1}^k f(i) = g(k).$$

Inductive Step:

  • Prove, using the Induction Hypothesis as a premise, that $$\sum_{i=1}^{k+1}f(i)=\left(\sum_{i=1}^k f(i)\right) + f(k\!+\!1) = g(k) + f(k\!+\!1) \color{#0a0}{=?}\ g(k\!+\!1).$$

  • The Inductive Step from $k$ to $k+1$ is true $\iff \color{#0a0}{ g(k\!+\!1) - g(k) = f(k\!+\!1)}$

Therefore we have proved by induction the following generic summation criterion

$\displaystyle\quad\sum_{i=1}^n f(i) = g(n)\iff \color{#c00}{g(1) = f(1)}\,\ {\rm and}\,\ \color{#0a0}{g(n\!+\!1)-g(n) = f(n\!+\!1)}\ $ for $\,n \ge 1$

Indeed, our induction proved the direction $(\Leftarrow),\,$ and $(\Rightarrow)$ is clear.

This theorem reduces the inductive proof to simply verifying the $\rm\color{#c00}{RHS}$ $\rm\color{#0a0}{equalities}$, which is trivial polynomial arithmetic when $f(n),g(n)$ are polynomials in $n,\,$ so trivial it can be done purely mechanically by a high-school student (or computer). No insight (magic) is required - no rabbits need be pulled from a hat.

The above theorem is an example of telescopy, also known as the Fundamental Theorem of Difference Calculus, depending on context. You can find many more examples of telescopy and related results in other answers here.

share|cite|improve this answer

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

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