To get a feel for this problem and also establish the base case for the induction process, let’s start by assigning some values to m.
When m=1, A⊂{1,2} and n(A) or |A| (the cardinality of A)=m+1=2. So for the base case A is a subset of itself, that is, A={1,2}. In this case, a and b can only be a=1, b=2, so a<b and a|b is true because a divides into b. So the base case is true.
When m=2, A⊂{1,2,3,4}, so, since |a|=m+1=3, there are 4 possible subsets because there are 4 ways of selecting 3 elements out of 4. However, three of these include the element 1 and we know when a=1 that a<b ∀b∈{2,3,4} and a|b is true ∀b. That leaves {2,3,4} and in this case, a=2 and b=4 because 2 divides into 4. So the case is proven for m=2.
When m=3, A⊂{1,2,3,4,5,6}. How many possible subsets containing 4 elements?
6C4=15 subsets; but these include those containing element 1. We know that when a=1, a will divide into 2, 3, 4, 5, 6, so we only have to consider 5C4=4 elements. Those subsets containing b=6 will have a=2 and/or 3 in the same subset, so a|b in all cases. The only subset not containing 6 is A={2,3,4,5}, and here we have a=2 and b=4. So the case is proven for m=3.
As m increases by 1, the number of elements in A increases by 2. Since we know that subsets containing 1 will always satisfy the rule, we can consider just (2m-1)Cm subsets (that is, 7C5=56, 9C6=84, etc.). The corresponding largest element in the set will be 2m. We know that the rule must be satisfied by ALL possible subsets A, so, first, we need to consider the subset in which the lowest valued element in the set is as high as possible—the mth element in the set. For example, let’s consider m=5, 6 and 7. Here we have the (2m)th element 10, 12, 14 and the corresponding mth element is 5, 6, 7. |A| is correspondingly 6, 7, 8 (that is, {5,6,7,8,9,10}, {6,7,8,9,10,11,12}, {7,8,9,10,11,12,13,14}). In these cases, the highest element is twice the lowest element. Next, we consider, those subsets NOT containing the (2m)th element. We would need to replace it with another element to make up the cardinality m+1. So in the examples the replacement would be from {2,3,4}, {2,3,4,5}, {2,3,4,5,6}. Each of these replacements has at least one multiple amongst the residual elements. The largest replacement in the examples is 4, 5, 6, each of which is half of a residual element, namely: 8, 10, 12.
So next we remove these and replace them, so as to attempt to disprove the rule. But while this prevents a from being 4, 5, 6 in the examples, it opens up opportunities for {2,3}, {2,3,4}, {2,3,4,5}.
We can conclude then that by continuing this process of reducing and replacing we will be unable in the last resort to exclude a=2. And we know that a=1 allows for any other elements in the subset A. In any set of numbers we can split them (pidgeonhole) them into odds and evens. Going back to the examples, for m=5, 6, 7 there are m-1 odd elements (excluding 1):
{3,5,7,9}, {3,5,7,9,11}, {3,5,7,9,11,13}. To make up the required cardinality we include a=2, but still fall short of |A|=m+1. Since we’ve already included all the possible odd numbers in the attempt to disprove the rule, we’re left with selecting an even number from {4,6,8,10,...}. This would provide b as a multiple of 2 and we would be unable to disprove the rule.
So by induction, and including the base case we established earlier, the rule is proven.
