2
$\begingroup$

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$

  • 0
    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.2013-03-30

3 Answers 3

2

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,

1

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.

0

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.