Consider the following problem:

Problem

Show that there do no exist non-negative integers k and m such that \( k! + 48 = 48(k+1)^m \)

Discussion

Claim 1: \( k \geq 9 \)

If there are such integers then \( k! = 48 \times ((k+1)^m – 1 )\).

Expanding we have \( k! = 48 \times (k^m + m \cdot k^{m-1} + {m \choose 2} k^{m-2} + \cdots + {m \choose {m-2}} k^2 + {m \choose {m-1} } k + 1 – 1 ) \)

Hence \( k! = 48k\times ( k^{m-1} + m \cdot k^{m-2} + {m \choose 2} k^{m-3} + \cdots + {m \choose {m-2}} k + {m \choose {m-1} } ) \)

Dividing by k on both sides we have \( (k-1)! = 48\times ( k^{m-1} + m \cdot k^{m-2} + {m \choose 2} k^{m-3} + \cdots + {m \choose {m-2}} k + {m \choose {m-1} } ) \) … (equation (1) – we will use this again later)

This implies 48 divides (k-1)! or \( (k-1) \geq 6 \Rightarrow k \geq 7 \)

In fact, we can quickly check that k = 7 and k = 8 does not work. After all, for k = 7, \( \frac{7!}{48} + 1 = 105 + 1 = 106 \) is not \( 8^m \) for any m. Similarly for k = 8, \( \frac{8!}{48} + 1 = 840 + 1 = 841 \) is not \( 9^m \) for any m.

Claim 2: k is even

\( \frac{k!}{48} + 1 = (k+1)^m \)

Since \( k > 8 \), then \( \frac{k!}{48} = \frac{1\times 2 \times 3 \times \cdots \times 8 \times \cdots k}{48} = 840 \times \cdots \times k \). Hence \( \frac{k!}{48} \) is even (as it is a multiple of 840). This implies \( \frac{k!}{48} + 1 \) is odd.

But that means \( (k+1)^m \) is odd or k+1 is odd. Hence k is even.

Let \( k = 2k_1 \).

Claim 3: k divides \( \frac {(k-1)!}{48} \)

We need to show that \( \frac {(k-1)!}{48} \) is divisible by 2 and \(k_1 \). Since we showed \( k \geq 9 \) in claim 1, and then showed k is even; this implies k is at least 10 or more.

\( \frac {(k-1)!}{48} \\ = \frac {1 \times 2 \times 3 \times \cdots \times 9 \times \cdots \times (k-1)} {48} \\ = 1 \times 5 \times 3 \times 7 \times 8 \times 9 \times \cdots \times (k-1) \)

For k = 10, we see that \(1 \times 5 \times 3 \times 7 \times 8 \times 9 \) is easily divisible by 10 (5 exists and 8 supplies one 2).

For k = 12, we see that \(1 \times 5 \times 3 \times 7 \times 8 \times 9 \times 10 \times 11 \) is also divisible by 12 (3 exists and 8 supplies one 4).

From k=14 onwards, this will be trivially true because: \( k/2 \geq 7 \) will be present in the product (as it is not canceled off by division by 48), and another 2 will be supplied by the first even number that follows k/2. (There will be one such even number, because \( \frac{k}{2} + 2 \leq k-1\) as \( 6 \leq k \) (in fact it 6 is much less than k as we have reached 14 or more).

Claim 4: k divides m

From Equation 1, we have:

\( (k-1)! = 48\times ( k^{m-1} + m \cdot k^{m-2} + {m \choose 2} k^{m-3} + \cdots + {m \choose {m-2}} k + {m \choose {m-1} } ) \)

This implies \( \frac {(k-1)!}{48} = k \times (k^{m-2} + m \cdot k^{m-3} + \cdots + {m \choose {m-2}} ) + m \)

Therefore \( \frac {(k-1)!}{48} – k \times (k^{m-2} + m \cdot k^{m-3} + \cdots + {m \choose {m-2}} ) = m \)

From Claim 3 we know k divides \( \frac {(k-1)!}{48} \). Hence the LHS of the above equation is divisible by k. This implies RHS is also divisible by k. Hence k divides m.

Let \( m = Qk \) where Q could be 1.

Claim 5: k cannot divide m (hence contradiction)

Use A. M. – G.M. Inequality to establish:

$$ \frac { 1+ 2 + \cdots + k}{k} > (1 \times 2 \times 3 \times \cdots \times k ) ^{\frac{1}{k}} $$

Strictly inequality holds, as the numbers are not all equal. This implies:

$$ \frac { (k+1)^k}{2^k} > k! $$

Therefore \( \frac { (k+1)^k}{2^k} + 48 > k! + 48 \) … (2)

Clearly \( 48 (k+1)^k > \frac { (k+1)^k}{2^k} + 48 \) … (3).

Why? Divide both sides by \( (k+1)^k \). Then you have \( 48 > \frac { 1}{2^k} + \frac{48}{(k+1)^k} \). k is 9 or more, right hand sides is (much) smaller than 1. Hence 48 is certainly greater than RHS.

Combining (2) and (3) we have \( 48 (k+1)^k > k! + 48 \). Since k divides m we have \( 48 (k+1)^m > 48 (k+1)^k > k! + 48 \).

Conclusion

Even before we start working on this problem, we should check some basic cases (where k and m are small; that is 0, 1, 2 etc.).

Also see

Advanced Math Olympiad Course at Cheenta