# Proofs using Mathematical Induction

I have two problems that I am trying to solve using mathematical Induction but am confused on how to know when process to use.

1) Prove by mathematical induction that $$2+5+8+\dotsb+(3n-1)=\frac{n(3n-1)}{2}$$ for $n\geq 1$

2) Prove that $3\mid n^3-n$ whenever $n$ is a positive integer.

NOT SURE HOW TO EDIT CORRECTLY BUT FOR NUMBER ONE THE EQUATION IS NOT CORRECT IS IT SUPPOSED TO BE $2+5+8+...+(3n-1)=(\frac 12 \cdot n)(3n+1)$ for $n$ greater than or equal to $1$.

• You do not need induction for part 2). Factorization of the RHS should make things obvious. – David H Mar 14 '14 at 1:47

## 5 Answers

How to know? I think the only answer, unfortunately, is experience.

The first one is simply a 'classic' induction problem.

The second one could also be done by induction, but seeing it's a question of divisibility, the first stop is usually to look at it from a 'modulo' perspective.

To prove by induction there are 2 steps:

1) basis of induction. Just prove the result for $n=1$, it is very straightforward

2) inductive step. Assume the result hold until $n-1$. Knowing this, prove the result for $n$.

• Wait, does it hold for $n=1$? Is there a typo? – Stefano Mar 14 '14 at 2:30
• which part are you talking about? – rick Mar 14 '14 at 4:18
• first part of your question. The formula should hold for $n\geq 1$, but if you plug $1$ in, it is not true. – Stefano Mar 14 '14 at 17:08
• Ok, I just saw you edited the question. – Stefano Mar 14 '14 at 17:11
• could you verify my answers that I posted to let me know if they were correct? – rick Mar 14 '14 at 20:07

So I found my answers just wondering if anyone can verify them for me please for the first problem it was Prove by mathematical inductino that $2+5+8+...+ (3n-1)=(1/2\cdot n)(3n>1)$. My solution I came up with is $[(k+1)/2][(3(k+1)+1]$. Then for the second problem which was prove that $3$ divides $n^3-n$ whenever $n$ is a positive integer. My solution I came up with was $3k^2+(k^3-k)+3k$. Can someone verify please?

• The solution should be a proof, not a formula. Try to be more precise. For example: step 1) basis of induction: for $n=1$ we have that ... therefore... step 2) inductive step: I assume ... I prove that ... – Stefano Mar 14 '14 at 20:33
• @stefano Not quite following you – rick Mar 15 '14 at 0:15
• @stafano at least on what steps i am supposed to take or am doing wrong – rick Mar 15 '14 at 2:38
• I suggest you to look at some examples to see how it works: purplemath.com/modules/inductn3.htm math.uiuc.edu/~hildebr/213/inductionsampler.pdf or Google 'proof by induction examples' – Stefano Mar 16 '14 at 2:18

Mathematical Induction has $2$ (or $3$) steps:

1) Prove true for $n=1$.

The first term is $2$ (by given information). $n(3n-1)/2 = (1)[3(1)-1]/2 = 2/2 = 1$. This does not prove true for the sum equation you provided. Are you sure you didn't mean $\frac{n(3n+1)}{2}$? This would hold true for all of the given terms.

• there is no term of 2, I was referring to the question the problem is just 3 divides n^3-n. – rick Mar 14 '14 at 3:39
• I was referring to the first part of your question. – BillyK Mar 14 '14 at 13:33
• I edited it and I posted my answers would you be able to verify for me please – rick Mar 14 '14 at 20:07

1) Are you familiar with the inductive proof that $\sum_{i=1}^{n} i = \frac{n(n+1)}{2}$? The proof here is the same. Notice the transformation: $\sum_{i=1}^{n} (3i-1) = 3\sum_{i=1}^{n}i - \sum_{i=1}^{n} 1$. It's really not that different from what you've already seen.

2) Divisibility proofs are usually straight-forward. Here's a good hint, though- expand out $(n+1)^{3} - n - 1$, then try and get $(n^{3} + n)$ by itself. You may have to subtract out an $n$ term, but that will be a good thing, based on how you account for it.