Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

Just want to get input on my use of induction in this problem:

Question. Use mathematical induction to prove that $(n^2+5)n$ is divisible by $6$ for all integers $n \geqslant 1$.

Proof by mathematical induction.

(1) show base case ($n=1$) is true: $$ ((1)^2 + 5) (1) = 6 $$ $6$ is indeed divisible by $6$, so base case ($n=1$) is true

(2a) Assume case $n$ is true: $(n^2+5)n$ is divisible by $6$.

(2b) Show that case $n$ $\implies$ case $(n+1)$ $$ \begin{align*} ((n+1)^2+5)(n+1) &\rightarrow ((n^2+2n+1)+5)(n+1) \\ &\rightarrow [(n^2+5)+(2n+1)](n+1) \\ &\rightarrow (n^2+5)n + (n^2+5)+(2n+1)n+ (2n+1) \\ &\rightarrow (n^2+5)n + [(n^2+5)+(2n^2+n)+ (2n+1)] \\ &\rightarrow (n^2+5)n + [(3n^2+3n)+6] \end{align*} $$

Now we can see case $(n+1)$ $= (n^2+5)n + (3n^2+3n)+6$.

We know $6$ is divisible by $6$ and we are assuming $(n^2+5)n$ is divisible by $6$ already, so all we need to do is show $(3n^2+3n)$ is divisible by $6$:

Letting $n=1$ for $(3n^2+3n)$ gives: $(3(1)^2+3(1)) = 6$

Thus, it has been demonstrated that $(n^2+5)n$ is divisible by $6$ for all integers $n \geqslant 1$.

I'm not sure if letting $n=1$ for that last expression is enough to prove it is divisible by $6$

share|improve this question
4  
It would be great if you could typeset your question instead of posting images. –  user17762 Dec 9 '11 at 23:23
2  
I would use an arrow $\rightarrow$ only to mean "If . . . then . . ." or "approaches" (in the sense used in calculus). Here you're putting it between expressions when you want to say they're actually equal. You should use "=" for that. –  Michael Hardy Dec 9 '11 at 23:33
    
I suspect that the line "Letting $n=1$ for $(3n^2+3n)$ gives $(3(1)^2+3(1))=6$" is supposed to be the start of another proof by induction that $6\vert(3n^2+3n)$ for all $n\in \mathbb{N}$. –  user5137 Dec 9 '11 at 23:35
    
Well I think he is using trying to use induction twice. We already know (n^2+5)n is divisible by 6 by assumption. That means a 3 can be pulled out. Now we have to show that it is divisible by 2 as well. We know that since (n^2+5)n is divisible by 6 then 2 must divide it as well. Now we must show that n^2+n+2 is divisible by 2. It n is an even number then it obviously divisible by 2. If n is odd then let n=2k+1 then if you work it out you will see you can pull out a 2. That would be one way to do it though induction would make the proof more slick. –  user60887 Mar 30 '13 at 21:25

3 Answers 3

up vote 2 down vote accepted

It is definitively not sufficient, since "letting $n=1$" means "you don't know what to do in every other cases of values of $n$". Since saying that $6$ divides $3n^2 + 3n$ is equivalent to saying that $2$ divides $n^2 + n$, you only need to show the latter. Now why should $2$ divide $n^2+n = n(n+1)$, two consecutive integers? (You could also prove this by induction, but that would be a little useless, would it.)

Hope that helps,

share|improve this answer

The statement that

$3n^2+3n$ is divisible by $6$ for all $n$.

and the statement that

$3(1)^2+3(1)=6$ is divisible by $6$.

are clearly not the same :) You can prove the former statement by showing that $n^2+n=n(n+1)$ is always even (use that either $n$ is even, or $n+1$ is).

By the way, use equals signs ($=$) instead of arrows ($\rightarrow$).

Finally: for any number $k$, "case $k$" refers to the statement

$(k^2+5)k$ is divisible by $6$.

As a statement, it is true, or possibly false. Your goal is to prove that "case $n$" is true for every number $n$. Therefore, you should not think things like

"case $(n+1)$ = $(n^2+5)n+3n^2+3n+6$"

which doesn't really make sense.

share|improve this answer

You can just say that it is always divisible by 6 since it is divisible by 3 (from the expression) and it is divisible by 2 since it is a multiplication of two consecutive integers- one of which is even.

Also the whole problem could be solved very easily using divisibility rather than induction, but I guess your problem asked you to use it.

share|improve this answer

Your Answer

 
discard

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.