Q) We call a number \(k\) as stable if there exists \(k\) distinct natural numbers \(a_1,a_2..a_k\) with \(a_i>1\) \(\forall i=1,2..k\) such that
\(\sum\limits_{i=1}^{k}\frac{1}{a_i}=1\). Show that if \(k\) is stable, then so is \(k+1\). Hence, or otherwise find all stable numbers
Solution:
We assume that \(k\) is stable. Thus there exists \(k\) different natural numbers satisfying the given condition. We need to find \(k+1\) distinct natural numbers that satisfy the given condition.
We have
\(\frac{1}{a_1}+\frac{1}{a_2}+…+\frac{1}{a_k}=1\).
We try to construct the set of the \(k+1\) numbers from the given set of \(k\) numbers.
Let’s try to create an algorithm to generate this set of \(k+1\) numbers from the set of \(k\) numbers. We start with an example: \(k=3\). The numbers are \(\frac{1}{2}, \frac{1}{3}, \frac{1}{6}\). Let’s see if we can get the numbers for \(k=4\) starting with this set. We need to basically somehow break 1 number into 2 numbers. Let’s see if we can bring in \(\frac{1}{4}\) from \(\frac{1}{3}\). We actually can! The new set becomes \(\frac{1}{2}, \frac{1}{4}, \frac{1}{12}, \frac{1}{6}\).
This process of breaking \(\frac{1}{a_k}\) into \(\frac{1}{a_k+1}, \frac{1}{a_k(a_k+1)}\) will thus work – except when one of these new numbers is already present in the given set. Can we assure that none of these new numbers will be present in the given set?
We’re using \(\frac{1}{a_k}=\frac{1}{a_k+1}+\frac{1}{a_k(a_k+1)}\) for the decomposition of 1 number into 2, and hence we are able to create a set of \(k+1\) numbers from a set of \(k\) numbers. What if we choose to decompose the minimum number of the given set? Let’s see for this case:
- Choose \(a_k\) such that \(\frac{1}{a_k}\) is the minimum of the given \(k\) numbers
- Decompose \(\frac{1}{a_k}\rightarrow \frac{1}{a_k+1}+\frac{1}{a_k(a_k+1)}\).
- The 2 new numbers are even less than \(\frac{1}{a_k}\) and since \(\frac{1}{a_k}\) was the minimum among the given numbers, these new numbers did not exist in the set of given \(k\) numbers.
We have already shown that \(k=3\) is stable. Hence all numbers after \(2\) are stable.