Every number as a sum of $2^e3^f$ with a special condition

Question

Can we write every number $n \in \mathbb{N}$ and $n \geq 2$ like this: $$n = 2^{x_1}3^{y_1} + 2^{x_2}3^{y_2} + \ldots + 2^{x_t}3^{y_t}$$ so that $2^{x_i}3^{y_i} \nmid 2^{x_j}3^{y_j}$ for every $i \neq j$ and $i,j \in \{0, 1, 2, ..., t\}$

I thought of proving this by induction but I don't know hot to handle the extra condition given.

Answer 1

By suitable rearrangement of the summands, we can express the non-divisibility condition as follows:

Theorem. For every positive integer $n$ there are integers $$\tag1\left.\begin{array}lt\ge1,\\x_1>x_2>\ldots >x_t\ge 0,\\0\le y_1<y_2<\ldots <y_t\end{array}\qquad\right\}$$ such that $$\tag2n=\sum_{k=1}^t2^{x_k}3^{y_k}=2^{x_1}3^{y_1}+2^{x_2}3^{y_2}+\ldots +2^{x_t}3^{y_t}.$$

The non-divisibility follows because of two distinct summands, one contains a lower power of $2$ and the other a lower power of $3$ as factor.

Proof. (by strong induction). Let $n$ be a positive n integer and assume that such a representation can be found for all smaller positive integers.

Case (i): $n$ is even. Then $\hat n:=\frac n2$ is a smaller positive integer. Hence by induction hypothesis, there are integers $\hat t\ge 1$, $\hat x_1>\ldots> \hat x_t\ge0$, and $0\le \hat y_1<\ldots< \hat y_t$ such that $$\hat n=\sum_{k=1}^{\hat t}2^{\hat x_k}3^{\hat y_k}.$$ Let $t=\hat t$, $x_k=\hat x_k+1$, $y_k=\hat y_k$ for $1\le k\le t$. Then $(1)$ holds and $$\sum_{k=1}^t2^{x_k}3^{y_k}=\sum_{k=1}^{\hat t}2^{1+\hat x_k}3^{\hat y_k}=2\hat n=n.$$

Case (ii): $n$ is odd. Find the largest power of $3$ that is $\le n$, i.e., find the integer $m\ge 0$ such that $$\tag33^m\le n < 3^{m+1}.$$ If $3^m=n$, we are done by letting $t=1$, $x_1=0$, $y_1=m$. Otherwise, $n-3^m$ is even and positive, hence $\tilde n:=\frac{n-3^m}2$ is a positive integer. By induction hypotheses, there are $\tilde t$ and $\tilde x_1>\ldots >\tilde x_t\ge 0$, $0\le \tilde y_1<\ldots <\tilde y_t$ such that $$\tilde n=\sum_{k=0}^{\tilde t}2^{\tilde x_k}3^{\tilde y_k}.$$ Let $t=\tilde t+1$, $x_k=\tilde x_k+1$ for $1\le k\le \tilde t$, $x_t=0$, $y_k=\tilde y_k$ for $1\le k\le \tilde t$, $y_t=m$. Then the first two lines of $(1)$ are clear, as well as $$ \sum_{k=1}^t2^{x_k}3^{y_k}=\sum_{k=1}^{\tilde t}2^{1+\tilde x_k}3^{\tilde y_k}\;+2^03^m=2\tilde n+3^m=n.$$ To see that the last line of $(1)$ holds, note that $y_{t-1}\ge y_t=m$ would imply $n\ge 2^{x_{t-1}}3^{y_{t-1}}+2^03^{y_t}\ge 2\cdot 3^m+3^m=3^{m+1}$, contrary to $(3)$. $\square$