# how can I proof that n(n+1)(n+2)(n+3) is divisible by 24. this is an induction question and I really don't understand it.

*print*Print*list*Cite

### 2 Answers

Pity that this problem could be solved simpler without induction than with. So, let's at least have fun:)

For n=1 the statement is true. Go from k to k+1:

24 | a(k) = k(k+1)(k+2)(k+3), what about a(k+1) = (k+1)(k+2)(k+3)(k+4)?

For 24 | a(k+1) it is sufficient that 24 | [a(k+1)-a(k)]. This is equal to (k+1)(k+2)(k+3)*4. So, it would be sufficient that 6 | (k+1)(k+2)(k+3) for any k>=0, which is the same that 6 | k(k+1)(k+2) for any k>=1.

Let's prove this by induction:)

For n=1 the statement is true. Go from k to k+1:

6 | b(k) = k(k+1)(k+2), what about b(k+1) = (k+1)(k+2)(k+3)?

For 6 | b(k+1) it is sufficient that 6 | [b(k+1)-b(k)]. This is equal to (k+1)(k+2)*3. So, it would be sufficient that 2 | (k+1)(k+2) for any k>=0, or 2 | k(k+1) for any k>=1.

It is almost evident, but:)

For n=1 the statement is true, 2 | 1*2. Go from k to k+1:

2 | c(k) = k(k+1), what about c(k+1) = (k+1)(k+2)?

For 2 | c(k+1) it is sufficient that 2 | [c(k+1)-c(k)]. This is equal to (k+1)*2. So, it would be sufficient that 2 | (k+1)*2 for any k>=0.

And this is TRUE!:)

-------------------------

(this proof is better than previous, because the same idea works for

120 | n(n+1)(n+2)(n+3)(n+4) and so on)

To prove a statement by induction, it has to be shown that the following two conditions are satisfied:

1) The statement is true for n = 1 (or any applicable initial value of n)

2) Assuming that the statement is true for n = k, the statement is ALSO true for n = k+ 1.

In this case, we need to prove that n(n+1)(n+2)(n+ 3) is divisible by 24. It is easy to check that the first condition is satisfied for n = 1:

n(n+ 1)(n+2)(n+3) = 1(2)(3)(4) = 24, which is divisible by itself.

Now let's see if can show that the second condition is also satisfied. Assume that for some n = k, k(k+1)(k+2)(k+3) is divisible by 24. We then need to show that if this is the case, then this expression for n = k+ 1 will also be divisible by 24. In other words, we need to show that

(k+1)(k+2)(k+3)(k+4) is also divisible by 24.

To do this, multiply out both expressions:

`k(k+1)(k+2)(k+3) = (k^2+ k)(k^2 + 5k + 6) = k^4 + 6k^3 + 11k^2 + 6k`

The second expression will be

`(k+1)(k+2)(k+3)(k+4) = (k^2 + 3k + 2)(k^2 + 7k + 12)`

`=k^4 + 10k^3 + 35k^2 + 50k + 24`

The next part is tricky. We are going to break up some of the terms of the second expression in the following way:

`10k^3 = 6k^3 + 4k^3`

`35k^2 = 11k^2 + 24k^2`

`50k = 6k + 44k`

Then the second expression can be rewritten as follows, by re-arranging the broken up terms:

`(k^4 + 6k^3 + 11k^2 + 6k) + (4k^3 + 24k^2 + 44k + 24)`

Notice that the expression in the first parenthesis is identical to the first expression, multiplied out k(k+1)(k+2)(k+3). This is divisible by 3 by assumption.

The second parenthesis contain terms 24k^2 and 24, which are clearly divisible by 24. We still need to show that the sum of remaining terms,

`4k^3 + 44k = 4(k^3 + 11k)` is divisible by 24. It would require the separate induction process to show that `k^3 + 11k` is in fact divisible by 6 (try it :), and then the product

`4(k^3 + 11k) ` is divisible by 24.

So we have shown that all parts of the sum constituting the second expression,

(k+1)(k+2)(k+3)(k+4) are divisible by 24, as long as k(k+1)(k+2)(k+3) is divisible by 24.

So, by induction, n(n+1)(n+2)(n+3) is divisible by 24.