0
$\begingroup$

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

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

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.

$\endgroup$
0
$\begingroup$

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

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

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?

$\endgroup$
  • $\begingroup$ 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 ... $\endgroup$ – Stefano Mar 14 '14 at 20:33
  • $\begingroup$ @stefano Not quite following you $\endgroup$ – rick Mar 15 '14 at 0:15
  • $\begingroup$ @stafano at least on what steps i am supposed to take or am doing wrong $\endgroup$ – rick Mar 15 '14 at 2:38
  • $\begingroup$ 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' $\endgroup$ – Stefano Mar 16 '14 at 2:18
0
$\begingroup$

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.

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

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.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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