1. Divisibility Proofs

Having a bit of trouble with this one. The final part of my attempt, highlighted in black, is meant to be factored in such a way that it ties into the earlier part of 1. I've tried factoring the final part in different ways, but I just can't get it to match 1. Can anyone help?
Many thanks.

Q.
n(n + 1)(2n + 1) is divisible by 3 for 3 for n $\displaystyle \in \mathbb{N}_0$.

Attempt:
Step 1: For n = 1...
1(1 + 1)(2(1) + 1) => 1(2)(3) => 6, which can be divided by 3.
Therefore, n = 1 is true.

Step 2: For n = k...
Assume k(k + 1)(2k + 1) can be divided by 3,
i.e. k(k + 1)(2k + 1) = 3Z, where Z is an integer...1
Show that n = k + 1 is true...
i.e. (k + 1)(k + 2)(2(k + 1) + 1) can be divided by 3.
(k + 1)(k + 2)(2(k + 1) + 1) => (k + 1)(k + 2)(2k + 2 + 1) => (k + 1)(k + 2)(2k + 3) =>

2k(k + 1)(k + 2) + 3(k + 1)(k + 2)

2. Re: Divisibility Proofs

Represent (k + 1)(k + 2)(2k + 3) as (k+1)[(k+2)((2k+1)+2)] and multiply through the expression in the square brackets.

If you don't need to use induction, it is easier to note that 2n ≡ -n (mod 3).

Also, you are repeating the flaws I pointed out in this thread, namely, saying "n = 1 is true" and "n = k + 1 is true" and using undefined notation =>.

3. Re: Divisibility Proofs

Originally Posted by GrigOrig99
Having a bit of trouble with this one. The final part of my attempt, highlighted in black, is meant to be factored in such a way that it ties into the earlier part of 1. I've tried factoring the final part in different ways, but I just can't get it to match 1. Can anyone help?
Many thanks.

Q.
n(n + 1)(2n + 1) is divisible by 3 for 3 for n $\displaystyle \in \mathbb{N}_0$.

Attempt:
Step 1: For n = 1...
1(1 + 1)(2(1) + 1) => 1(2)(3) => 6, which can be divided by 3.
Therefore, n = 1 is true.

Step 2: For n = k...
Assume k(k + 1)(2k + 1) can be divided by 3,
i.e. k(k + 1)(2k + 1) = 3Z, where Z is an integer...1
Show that n = k + 1 is true...
i.e. (k + 1)(k + 2)(2(k + 1) + 1) can be divided by 3.
(k + 1)(k + 2)(2(k + 1) + 1) => (k + 1)(k + 2)(2k + 2 + 1) => (k + 1)(k + 2)(2k + 3) =>

2k(k + 1)(k + 2) + 3(k + 1)(k + 2)
You're almost there. Note that since k, k+1 and k+2 are three consecutive numbers, one of them must be a multiple of three, and therefore, so must be their product.

4. Re: Divisibility Proofs

Originally Posted by Prove It
You're almost there. Note that since k, k+1 and k+2 are three consecutive numbers, one of them must be a multiple of three, and therefore, so must be their product.
If we are allowed to use the fact that the product of three consecutive integers is divisible by 3, then the induction hypothesis, and therefore induction itself, is not necessary. We simply say that for any k,

k(k + 1)(2k + 1) = k(k + 1)(2(k - 1) + 3) = 2(k - 1)k(k + 1) + 3k(k + 1).

By the way, is $\displaystyle \mathbb{N}_0$ the set of natural numbers with 0? Then the base case should be considered for n = 0.

5. Re: Divisibility Proofs

If $\displaystyle n \equiv 0 (\mod 3)$ then n is divisible by 3.

If $\displaystyle n \equiv 1 (\mod 3)$ then 2n+1 is divisible by 3.

If $\displaystyle n \equiv 2 (\mod 3)$ then n+1 is divisible by 3.

Each of these three cases yields a factor of $\displaystyle n(n+1)(2n+1)$ that is divisible by 3, so we're done.

6. Re: Divisibility Proofs

Multiplying through the square brackets gives me: $\displaystyle (k+1)(2k^2+k+2k+4k+2+4)$ = $\displaystyle (k+1)((2k^2+k)+6k+6)$ = (k + 1)((k)(2k + 1) + 6k + 6) = 3Z + 6k + 6 which can be divided by 3.
Have I done this correctly?

Also, thanks for the alternative solution, Richard. I just want to make sure that I understand both methods of the solution. I'm not ignoring you!

7. Re: Divisibility Proofs

...or maybe it's 3Z + (k + 1)(6k) + (k + 1)(6) = $\displaystyle 3Z+6k^2+6k+6k+6$ = $\displaystyle 3Z+6k^2+12k+6$?

8. Re: Divisibility Proofs

Originally Posted by GrigOrig99
...or maybe it's 3Z + (k + 1)(6k) + (k + 1)(6) = $\displaystyle 3Z+6k^2+6k+6k+6$ = $\displaystyle 3Z+6k^2+12k+6$?
Correct. I should have said that in rewriting (k+1)[(k+2)((2k+1)+2)] it is better to keep 2k + 1. Then this equals

(k + 1)[k(2k + 1) + 2k + 2(2k + 1) + 4] = k(k + 1)(2k + 1) + (k + 1)[6k + 6] = 3Z + 6(k + 1)^2 = 3(Z + 2(k + 1)^2).

9. Re: Divisibility Proofs

Great. Thank you very much.

10. Re: Divisibility Proofs

without loss of generality, we may assume that neither n nor n + 1 is divisible by 3 (or else the conclusion is obvious). in this case, n + 2 is divisible by 3.

but if n + 2 = 3k, then 2n + 1 = 2n + 4 - 3 = 2(n + 2) - 3 = 6k - 3 = 3(2k - 1).

*****
inductively, if k(k + 1)(2k + 1) = 3t

then (k + 1)(k + 2)(2k + 3) = k(k + 2)(2k + 3) + (k + 2)(2k + 3)

= k(k + 1)(2k + 3) + k(2k + 3) + (k + 2)(2k + 3)

= k(k + 1)(2k + 1) + 2k(k + 1) + k(2k + 3) + (k + 2)(2k + 3)

= 3t + 2k2 + 2k + 2k2 + 3k + 2k2 + 7k + 6

= 3t + 6k2 + 12k + 6

= 3(t + 2k2 + 4k + 2), and of course (0)(1)(1) = 0 = (3)(0).