Any positive integer can be written as $2^{\sum_{k=1}^N n_k+m_k}+\sum_{i=1}^{N} 2^{\left(\sum_{k=i}^N n_k+m_{k+1}\right)}\left(2^{m_i}-1\right)$

Question

I want to prove this theorem:

Theorem: For every natural number $n \in \mathbb{N}$, there exist natural numbers (they can be $0$): $\{n_1,...,n_N\} $ and $\{m_1,...,m_N\}$ such that:

$$n=2^{(n_1+...+n_N)+(m_1+...+m_N)}+\sum_{i=1}^{N} 2^{(n_{i}+...+n_N)+(m_{i+1}+...+m_N)}\big(2^{m_i}-1\big)$$

For example:

For $n=6$, choose $n_1=1=m_1$. Then: $$6=2^{n_1+m_1}+2^{n_1+0} (2^m_1-1)=2^2+2(2-1)=4+2=6$$

For $n=2$, choose $n_1=1, m_1=0$. $$2=2^{n_1+m_1}+2^{n_1+0}(2^m_1-1)=2^1+2^1(1-1)=2$$

¿How can I proof this by induction? Any ideas?

Answer 1

Let call $$ f(N)=2^{(n_1+...+n_N)+(m_1+...+m_N)}+\sum_{i=1}^{N} 2^{(n_{i}+...+n_N)+(m_{i+1}+...+m_N)}\big(2^{m_i}-1\big) $$ we have $$ f(N)=2^{n_N+m_N} \left(2^{(n_1+...+n_{N-1})+(m_1+...+m_{N-1})}+\sum_{i=1}^{N-1} 2^{(n_{i}+...+n_{N-1})+(m_{i+1}+...+m_{N-1})}\big(2^{m_i}-1\big)\right)+ 2^{n_N}(2^{m_N}-1) $$ so $$ f(N)=2^{n_N+m_N} f(N-1) + 2^{n_N}(2^{m_N}-1) $$ Now assume that a number $n=f(N-1)$ for some coefficients $(n_1,\cdots n_{N-1})$,$(m_1,\cdots m_{N-1})$ than $2n=f(N)$ with coefficients $$ (n_1,\cdots n_{N-1},1),(m_1,\cdots m_{N-1},0) $$ and $2n+1=f(N)$ with coefficients $$ (n_1,\cdots n_{N-1},0),(m_1,\cdots m_{N-1},1) $$ so the theorem is true by prefix induction (see also this question)

This also prove that you can choose $n_i, m_i \in \{0,1\}$