Reply To: Maths
I think I have a proof (shown below) that proves that the solutions given by @Astralica to the problem given by @USB-C_is_supreme are all the solutions that exist.
Before I start with my proof, I want to establish a few facts:
1: The only prime factor of 2^k, where k is a natural number, is 2. (Natural number is defined here as any integer greater than or equal to one. )
1.1: It follows from Fact 1 that 2^k – 1 is an odd number.
1.2: It follows from Fact 1 that 2^k does not have 3 as one of its prime factors and hence 2^k cannot be a multiple of 3.
2: k! is the product of all natural numbers smaller than or equal to k, for any natural number k. It follows that any natural number k must be a factor of m! for all integer m greater than or equal to k.
2.1: It follows from Fact 2 that k! is even for any integer k greater than or equal to 2.
2.2: It follows from Fact 2 that k! is a multiple of 3 for any integer k greater than or equal to 3.
2.3: It follows from Fact 2 that k! is a multiple of 4 for any integer k greater than or equal to 4.
In the first part of my proof, I want to show that a and b cannot both be greater than or equal to 3. To achieve this, I want to use proof by contradiction:
Suppose that both a and b are greater than or equal to 3. It follows from Fact 2.2 that a! and b! must both be multiples of 3, hence the sum of a! and b! must also be a multiple of 3. However, we know from Fact 1.2 that 2^n cannot be a multiple of 3 when n is an positive integer. This leads to a contradiction as a multiple of 3 cannot be equal to a number that is not a multiple of 3, meaning that a! + b! cannot equal 2^n when both a and b are greater than or equal to 3.
It follows that the smallest number out of a and b must be either 1 or 2. This means that any solution will be one of two cases: either the smallest number out of a and b is 1, or the smallest number out of a and b is 2. We can assume, without loss of generality, that a is smaller than or equal to b due to the symmetry (we can swap a and b and the equation stays exactly the same: a! + b! = 2^n —> b! + a! = 2^n).
Case 1: a = 1, hence a! = 1.
This gives 1 + b! = 2^n. Rearrange to get b! = 2^n – 1. We know from Fact 1.1 that that 2^n – 1 has to be an odd number, meaning that b! also has to be odd. However, we know from Fact 2.1 that b! must be even for all b greater than or equal to 2. This leaves 1 as the only possible value of b. We can substitute this into the expression to get a! + b! = 1! + 1! = 2, which is 2^1. Hence the only valid solution in Case 1 is a = 1, b = 1, n = 1.
Case 2: a = 2, hence a! = 2*1 = 2.
This gives 2 + b! = 2^n. Rearrange to get b! = 2^n – 2. Factorise to get b! = 2(2^(n-1) – 1). Clearly, n cannot be 1 because 2(2^(1-1) – 1) equals 0 and no b! can give 0 (we know from Fact 2 that b! is the product of all natural numbers smaller than or equal to b and the product cannot be 0 as 0 is not considered a natural number in this proof). We know from Fact 1.1 that that 2^(n-1) – 1 has to be an odd number for any integer n greater than or equal to 2. It follows that b! must be 2 times an odd number, meaning that it is a multiple of 2 but not a multiple of 4. However, we know from Fact 2.3 that b! must be a multiple of 4 for all b greater than or equal to 4. This leaves 2 and 3 as the only two possible values of b (b cannot be 1 as we have assumed that b is greater than or equal to a). Substituting both gives 2! + 2! = 2 + 2 = 4 = 2^2 and 2! + 3! = 2 + 3*2*1 = 2 + 6 = 8 = 2^3, giving the two solutions a = 2, b = 2, n = 2 and a = 2, b = 3, n = 3.
Since we have assumed that a is smaller than or equal to b by exploiting the symmetrical nature of the equation, we have to obtain the final solution a = 3, b = 2, n = 3 by swapping a and b. We do not get any other solutions by swapping a and b since for the other 2 solutions, a and b are equal so swapping them will only give the same solution.
Hence I believe I have proven that the only 4 solutions (a,b,n) to the equation a! + b! = 2^n where a, b and n are all natural numbers are (1,1,1), (2,2,2), (2,3,3) and (3,2,3). QED