Thread: 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 .

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)

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

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 .

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.

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 the set of natural numbers with 0? Then the base case should be considered for n = 0.

If then n is divisible by 3.

If then 2n+1 is divisible by 3.

If then n+1 is divisible by 3.


Each of these three cases yields a factor of that is divisible by 3, so we're done.

Multiplying through the square brackets gives me: = = (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!

...or maybe it's 3Z + (k + 1)(6k) + (k + 1)(6) = = ?

Originally Posted by GrigOrig99

...or maybe it's 3Z + (k + 1)(6k) + (k + 1)(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).

Great. Thank you very much.

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 + 2k² + 2k + 2k² + 3k + 2k² + 7k + 6

= 3t + 6k² + 12k + 6

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