BartSimpsons wrote: Let $A(n)$ denote the number of sequences $a_1\ge a_2\ge\cdot{}\ge a_k$ of positive integers for which $a_1+\cdots{}+a_k = n$ and each $a_i +1$ is a power of two $(i = 1,2,\cdots{},k)$. Let $B(n)$ denote the number of sequences $b_1\ge b_2\ge \cdots{}\ge b_m$ of positive integers for which $b_1+\cdots{}+b_m =n$ and each inequality $b_j\ge 2b_{j+1}$ holds $(j=1,2,\cdots{}, m-1)$. Prove that $A(n) = B(n)$ for every positive integer $n$. for $n=2$, $A(2)=0$ because we can't find such sequence $\forall k$ and $B(2)=1$ because $m=1,b_1=2$ is the only solution.

aviateurpilot wrote: for $n=2$, $A(2)=0$ because we can't find such sequence $\forall k$ and $B(2)=1$ because $m=1,b_1=2$ is the only solution. $A(2) = 1$ because the sequence $1,1$ works.

Consider the set $$S \overset{\text{def}}{:=} \left \{ (2^k-1) \, | \, k \geqslant 1 \right \}.$$ Claim: Both $A(n), B(n)$ count the number of ways to write $n$ as a sum of (not necessarily distinct) elements of $S$, without ordering. (Proof) For $A(n)$ it's clear; each $a_i$ is an element of $S$ and multiplicities are accounted for by taking many equal $a_i$'s. For $B(n)$ consider the following bijection: $(b_1, \dots, b_m) \mapsto (x_1, \dots, x_m)$ such that $x_m=b_m$ and for all $1 \leqslant j \leqslant m-1$ we have $x_j=b_j-2b_{j+1}$. It is clear that $$n=b_1+\dots+b_m=\sum (2^k-1)x_k,$$ so choosing $x_k$ to be the multiplicity of $2^k-1$ we have the said count for $B(n)$. Evidently, the claim is true so $A(n)=B(n)$ for all $n \geqslant 1$. $\blacksquare$ Note: to check the said map is a bijection is easy; so I'll not do that on AoPS...

Plasma_Vortex wrote: aviateurpilot wrote: for $n=2$, $A(2)=0$ because we can't find such sequence $\forall k$ and $B(2)=1$ because $m=1,b_1=2$ is the only solution. $A(2) = 1$ because the sequence $1,1$ works. thanks. i didn't check $1,1$ because I made a confusion I thought that $a_i-1$ is power of $2$ instead of $a_i+1$

wasn't this pretty easy for an apmo.I think the motivation is the dummy variable concept which has been seen a lot before.

ignore...

We re-parametrize the $b_j$ sequence by writing $$\begin{align*} b_m &= 1 + x_m \\ b_{m-1} &= 2 + 2x_m + x_{m-1} \\ b_{m-2} &= 4 + 4x_m + 2x_{m-1} + x_{m-2} \\ b_{m-3} &= 8 + 8x_m + 4x_{m-1} + 2x_{m-2} + x_{m-3} \\ &\vdots \end{align*}$$ in which case the condition $\sum b_i = n$ becomes $$n = x_1 + 3x_2 + 7x_3 + 15x_4 + \dots + (2^m-1)(x_m + 1).$$ The bijection to $A(n)$ is now obvious, as $x_i$ counts the number of times $a_i = 2^i-1$ appears, with maximal term $a_1 = 2^m-1$.

Another approach: Call an $A$ sequence every sequence for which each $a_i +1$ is a power of two and a $B$ sequence every sequence for which inequality $b_j\ge 2b_{j+1}$ holds. Now call $b_{k,i}$ a $B$ sequence with sum equal to $k$ and has $i$ numbers (i.e $(4,2,1)$ is $b_{7,3}$) Also call $a_{k,i}$ an $A$ sequence with sum equal to $k$ and max number equal to $2^k -1$ (i.e $(3,3,1)$ is $a_{7,2}$) Now take a number $N$. If $(2^m-1) <= N < 2^{m+1}-1$ Then obviously: $B(N) = b_{N,1} + b_{N,2} + ... + b_{N,m}$ and $A(N) = a_{N,1} + a_{N,2} + ... + a_{N,m}$ We will prove $a_{N,i} = b_{N,i}$ and the result will follow. We proceed by strong induction. Assume that for every $k < N$ , $a_{k,i} = b_{k,i}$ holds. Again $(2^m-1) <= N < 2^{m+1}-1$ Now take the $B$ sequence $(2^{i-1} , 2^{i-2} , ... , 1)$ with sum $2^{i}-1 <= N$ In order to make it a $B$ sequence with sum $N$ we must add to it $B$ sequences with sum $N - 2^i + 1$. So we see that $b_{N,i} = b_{N-2^i+1,1} + b_{N-2^i+1,2} +... + b_{N-2^i+1,i}$ Now take an $A$ sequence with sum $N$ and max number $2^i-1$ If we remove the max number we stay with sequences with sum $N-2^i+1$ and a max number that can be $1,2, ... , 2^i-1$ So we conclude that $a_{N,i} = a_{N-2^i+1,1} + a_{N-2^i+1,2} + ... + a_{N-2^i+1,i}$ But $a_{N-2^i+1,j} = b_{N-2^i+1,j}$ from the inductive step so we are done.

It's on OEIS. https://oeis.org/search?q=A000929&language=english&go=Search

Let $\mathcal{A}(n)$ denote the set of sequences that count $A(n)$, and define $\mathcal{B}(n)$ to be the reversed sequences that count $B(n)$ (so $b_m\le b_{m-1}\le\cdots\le b_1$). In particular, $A(n)=|\mathcal{A}(n)|$ and $B(n)=|\mathcal{B}(n)|$. We'll provide a bijection between the two. Given a number $a=2^k-1$ that is one less than a power of $2$, let $\omega_a=(1,2,\ldots,2^{k-1},0,0,\ldots)$. Furthermore, call a sequence of non-negative integers $(c_1,c_2,\ldots)$ droopy if $c_i\ge 2c_{i+1}$ for all $i$. Define $$f:\mathcal{A}(n)\to\mathcal{B}(n)$$ by $$(a_1\ge a_2\ge\cdots\ge a_k)\mapsto\sum_{i=1}^k\omega_{a_i}.$$ Let's first check that this is well defined. To do so, note that the $\omega_a$ are droopy, and the sum of two droopy sequences is droopy. Furthermore, the sum of the elements of $\omega_a$ is $a$, so the $f$ values land in $\mathcal{B}(n)$, as desired. Let's now check that $f$ is an injection. To do this, it suffices to show that the vectors $$\omega_1,\omega_3,\omega_7,\ldots$$ are linearly independent, or that $$(1,0,0,\ldots),(1,2,0,0,\ldots),(1,2,4,0,0,\ldots),\ldots$$ are linearly independent. These vectors when viewed as rows of a matrix make the matrix upper triangular with no zeroes on the diagonal, so any principal finite minor is $1$, which isn't $0$. This proves the claim. It now remains to check that $f$ is a surjection. Given a sequence of length $m$ in $\mathcal{B}(n)$, subtract off an $\omega_{2^{m+1}-1}$, and delete any starting zeroes, and repeat. The set of the $2^{m+1}-1$ numbers that we get form an element of $\mathcal{A}(n)$ that maps to the given element of $\mathcal{B}(n)$, so we're done.

I claim that both $A(n)$ and $B(n)$ count the amount of ways to pick an increasing n-tuple of nonnegatives $(x_1,\ldots,x_k)$ such that $\sum\limits_{i=1}^k 2^{k-i}x_i=n$. For $A(n)$, note that $a_i$ in binary is $111\ldots 1$, so if we add all the $a_i$ in binary without carrying, and then construe each digit as an element in our n-tuple, we find a bijection as desired. For $B(n)$, define a new sequence $y_i=b_i-2b_{i-1}$, $y_m=b_m$. Then, we can write $b_i=y_i+2y_{i+1}+\ldots + 2^{m-i}y_m$ for all $i$. Adding, we will get $2^{m-1}y_m+2^{m-2}(y_m+y_{m-1})+\ldots+(y_1+\ldots+y_m)$. So, for any tuple $(x_1,\ldots,x_m)$, we can biject to a sequence of $y$s in $B(n)$ by setting $y_{m-i}=x_{i+1}-x_i$, $y_m=x_1$. As both $A(n)$ and $B(n)$ biject to the count at the beginning, we must have $A(n)=B(n)$.

One of the best bijection problem I've seen in a while First, we'll prove $A(n) \le B(n)$. Since $a_i + 1$ is a power of $2$, then we could write $a_i + 1 = 2^{f(i)}$, for some $f(i) \in \mathbb{N}$ which gives us $$a_i = 2^{f(i) - 1} + 2^{f(i) - 2} + \dots + 2^0$$ for every $i \in \mathbb{N}$. Now, we could let $$b_n = \sum_{i = 1}^{k} 2^{f(i) - n}$$ and define $2^{f(i) - n} = 0$ when $f(i) < n$. It could be easily checked that $b_j \ge 2b_{j + 1}$, and thus satisfy the condition. Now, we'll prove $B(n) \le A(n)$. Now, notice that a sequence $(b_1, b_2, \dots, b_m)$ could map to: $b_k - 2b_{k + 1}$ values of $2^{k} - 1$, and define $b_{m + 1} = 0$. Since we have the condition $b_i \ge 2b_{i + 1}$ for every $i \in \mathbb{N}$. Then we won't have a negative number of $2^k - 1$. Moreover, the values of the sums is still the same as $$\begin{align*} \sum_{k = 1}^{m} (b_k - 2b_{k + 1}) (2^{k} - 1) &= \sum_{k = 1}^m (2^k - 1)b_k - (2^{k + 1} - 2) b_{k + 1} \\ &= \sum_{k = 1}^m (2^k - 1) b_k - \sum_{k = 1}^m (2^{k + 1} - 1) + \sum_{k = 1}^m b_{k + 1} \\ &= \sum_{k = 1}^m (2^k - 1)b_k - \sum_{k = 2}^{m + 1} (2^{k} - 1)b_k + \sum_{k = 2}^{m + 1} b_k \\ &= \sum_{k = 1}^m b_k \end{align*}$$ Combining the two result, we have $A(n) = B(n)$ for all $n \in \mathbb{N}$.

here is an oldest source: Kürschák competition 2011

An older source: PFTB 8.13, which was proposed by D.R.Hickerson to AMM(as the book said).

We establish a bijection between sequences counted in $A(n)$ and sequences counted in $B(n).$ Consider some sequence $S=\{a_1,a_2,\dots,a_k\}$ counted in $A(n).$ Suppose $a_1+1=2^c$ for some $c.$ For $i\in\{1,2,\dots,c\},$ let $x_i$ be the number of occurrences of $2^{c+1-i}-1$ in $S.$ We have $$x_1+(2x_1+x_2)+\dots+(2^{c-1}x_1+2^{c-2}x_2+\dots+x_c)=\sum_{i=1}^{c}(2^{c+1-i}-1)x_i=n.$$ Therefore, the sequence $\{x_1,2x_1+x_2,\dots,2^{c-1}x_1+2^{c-2}x_2+\dots+x_c\}$ is counted in $B(n).$ Conversely, consdier some sequence $T=\{b_1,b_2,\dots,b_m\}$ counted in $B(n).$ For nonnegative $r_i,$ write $$b_1=r_0,$$ $$b_2=2r_0+r_1,$$ $$b_3=4r_0+2r_1+r_2,$$ $$\vdots$$ $$b_m=2^{m-1}r_0+2^{m-2}r_1+\dots+r_{m-1}.$$ Adding these equations yields $$(2^m-1)r_0+(2^{m-1}-1)r_1+\dots+r_{m-1}=n.$$ Hence, the sequence with $r_i$ terms of value $2^{m-i}-1$ for $i\in\{0,1,\dots,m-1\}$ is the unique sequence counted in $A(n)$ corresponding to $T.$ Thus, we have shown that $A(n)=B(n)$ for all $n,$ as desired.

oops apparently i cant do writeups Consider $c_i=b_{i}-2b_{i+1}$ for $1\le i\le m-1$ and $c_m=b_m$; we have that $b_{m-1}=c_{m-1}+2c_m$, $b_{m-2}=c_{m-2}+2(c_{m-1}+2c_m)=c_{m-2}+2c_{m-1}+2b_{1}$... From here, we can see that $\sum b_i=\sum(2^{j}-1)c_j$; therefore $B(n)$ is equal to the amount of ways that $n$ can be written as a sum of not necessarily distinct positive integers of the form $2^x-1$ without regard to ordering. Obviously the function $A(n)$ counts the number of such sums as well with multiplicity accounted by having equal terms in the $a$ sequence, hence $A(n)=B(n)$ and we have completed our proof. $\blacksquare$

I claim that $A(n), B(n)$ both count the number of ways to select a size $k$ multiset of numbers of the form $2^t - 1$ for positive integers $t$ with sum $n$. This is clear for $A(n)$ because that is how it is defined. For $B(n)$, define the new sequence $c_m = b_m$ and $c_i = b_i - 2b_{i + 1}$ for all $i \in [1, m - 1]$. Note that through a bit of expanding we may write $$b_1 + b_2 + \ldots + b_m = \sum_{i = 1}^m (2^0 + \ldots + 2^{i - 1})c_i = \sum_{i = 1}^m (2^i - 1)c_i$$ so in fact to determine sequences $b_i$ satisfying $B$ is the same as determining a sequence of $c_i$, that is, counting how many $2^i - 1$ there are for each $i$. Hence both $A(n)$ and $B(n)$ count the number of ways to select a size $k$ multiset of numbers of the form $2^t - 1$ for positive integers $t$ with sum $n$ and we are done. $\blacksquare$

The bijection was amazing. We let any number $n$ be written as $\sum_{i=1}^{k}(2^i-1)a_i= \sum_{i=1}^{k}(2^i-1) \cdot c_i$ for nonnegative integers $c_i$ and positive $k$ such that $k=\lfloor \log_2(n+1)\rfloor$. This means that we can write each $2^i-1$ as $\sum_{j=0}^{i-1}2^j$ so our sum is equivalent to $$\sum_{i=1}^{k}\sum_{j=0}^{i-1}2^j \cdot c_i = \sum_{0 \le j < i \le k}2^j \cdot c_i = \sum_{i=1}^k \sum_{j=0}^{k-i} 2^j \cdot c_{i+j}= \sum_{i=1}^k b_i$$ where $b_i=\sum_{j=0}^{k-i} 2^j \cdot c_{i+j}$ for all $c$. This means that for there exists a corresponding sequence of $b_i$ for any $c_i$, also a corresponding sequence of $b_i$ for any $a_i$ so $B(n) \ge A(n).$ Now, for any sequence of $b_i$ we write all terms of it in base $2$, and make it have to have $k$ elements; If there aren't $k$ elements then all the previously undefined ones are zero and so is $b_{k+1}$. Let $c_i=b_i-2b_{i+1}$ so then we have that for each sequence of $b_i$, there must be a unique sequence $c_i$. Now, we see that for all $i$, making $a_i=\sum_{i=1}^{k}(2^i-1) \cdot c_i$ gets us that all $a_i$ are one less than a power of $1$ as such, and $$\sum_{i=1}^{k}a_i=\sum_{i=1}^{k}(2^i-1) \cdot c_i=\sum_{i=1}^{k}(2^i-1)(b_i-2b_{i+1}) = \sum_{i=1}^{k}b_i=n$$ and we are done. An example is if we have $37=1 \cdot 0+3 \cdot 0+7 \cdot 1+15 \cdot 2+31 \cdot 0$, then we see that $$37 = 0(1+2+4+8+16) + 2(1+2+4+8) + 1(1+2+4) + 0(1+2) + 0(1)$$ and we write the number in a 2D grid, with the largest powers corresponding to the numbers on the right and multiplied by each $c_i$ coefficient per row. Now, note that summing the columns gets $37 = (1 \cdot 2)+(2 \cdot 2 + 1 \cdot 1)+(2 \cdot 4 + 1 \cdot 2)+(2 \cdot 8 + 1 \cdot 4)$ - that's our $b_i$ configuration and we are done. We do the same thing to convert our $b_i$ to $a_i$.

Let $S_A$ denote the set of sequences satisfying the first condition, and similarly define $S_B$. For each $i$ define the infinite vector $v_i=(2^{i-1}, 2^{i-2} , \dots , 1 , 0, 0, \dots)$; note the sum of coordinates of $v_i$ is $2^i-1$. For each sequence $(a_1, \dots , a_k) \in S_A$ consider replacing each term $a_j=2^{\ell}-1$ with the vector $v_{\ell}$, and adding these vectors together to obtain some vector $u$. It's clear that the nonzero entries of $u$ form a sequence which is in $S_B$. This map from $S_A$ into $S_B$ is injective (for instance, because the vectors $v_1, v_2 , \dots$ are linearly independent). On the other hand, every element $(b_1 , \dots , b_m) \in S_B$ is in the image of this map (for instance, we can inductively subtract off $v_m$). So the map is bijective and we're done.

For each sequence $a_{1}, a_{2}, \ldots a_{k}$, let $a_{i} = 2^{c_{i}} - 1$. Next, let $r = c_{1}$, and let $d_{r}, d_{r-1}, \ldots d_{1}$ be a sequence such that $d_{i}$ is the number of $j$ such that $c_{j} = i$. Now, consider the sequence $$e_{1} = d_{r}, e_{i} = 2\cdot e_{i-1} + d_{i}$$ This satisfies $e_{i} \geq 2\cdot e_{i-1}$. Furthermore, $$\sum_{i = 1}^{r} e_{i} = \sum_{i = 1}^{r} d_{r-i}\cdot (1 + 2 + 2^{2} + \ldots + 2^{r-i}) = \sum_{i = 1}^{r} d_{r-i} \cdot (2^{r-i} - 1) = \sum_{i=1}^{k} a_{i} = n$$ So this sequence of $e_{i}$ is a sequence that satisfies every B sequence. Since every B sequence can also be expressed this way, we conclude that this is a bijection between A sequences and B sequences, so $A(n) = B(n)$.

For each $i$ defines $$\begin{align*} A_i(n)&=\{(a_1,...,a_m):a_1+...+a_m=n:2^i-1=a_1\geq a_2\geq ...\geq a_m\}\\ B_i(n)&=\{(b_1,...,b_i):b_1+...+b_i=n:b_j\geq 2b_{j+1}:b_1\geq ...\geq b_i\} \end{align*}$$ Claim. If $i,n$ are integers than $|A_i(n)|=|B_i(n)|$ Proof. We proceed by induction on $n$ where the base cases are trivial. Firstly, notice that there is a bijection from $A_i(n)$ to $A$ where $$A=\bigcup\limits_{j=1}^iA_j(n-2^i+1)$$ which sends $(a_1,...,a_m)\to (a_2,...,a_m)$. Meanwhile, notice that $(b_k-2^{i-k})\geq 2(b_{k+1}-2^{i-k-1})$ for every $(b_1,...,b_i)\in B_i(n)$, therefore, there is a bijection from $A_i(n)$ to $B$ where $$B=\bigcup\limits_{j=1}^iB_j(n-2^i+1)$$ which sends $(b_1,...,b_i)$ to $(b_1-2^i,b_2-2^{i-1},...,b_i-1)$. Therefore, by inductive hypothesis, $$|A_i(n)|=|A|=\sum_{j=1}^i|A_j(n-2^i+1)|=\sum_{j=1}^i|B_j(n-2^i+1)|=|B|=|B_i(n)|$$ as desired. $\blacksquare$ This implies $$A(n)=\sum|A_i(n)|=\sum|B_i(n)|=B(n)$$ as desired.

Consider the number of ways to write $n$ as the sum of (not necessarily distinct) elements in the set $$\{2^1-1,2^2-1,2^3-1,\ldots\}.$$ The key claim is that $A(n)$ and $B(n)$ are both equal to this quantity, which immediately implies $A(n)=B(n)$. This is clear for $A(n)$, so now we look at $B(n)$. For any working sequence $b_1 \geq b_2 \geq \cdots \geq b_m$, define the sequence $(e_n)$ with $e_m=b_m$, and for $1 \leq k<m$, $b_k=2b_{k+1}+e_k$. Note that all elements in the sequence $(e_n)$ are nonnegative. It is not hard to verify that $$b_1+b_2+\cdots+b_m=x_1+3x_2+7x_3+\cdots+(2^m-1)x_m=\sum_{k=1}^{m} (2^k-1)x_k,$$ from which the bijection is clear. $\blacksquare$

First, associate each sequence $b_i$ with a sequence $c_i$ of nonnegative integers such that $b_1 = c_1$ and $b_{i+1} = 2b_i + c_{i+1}$ for all $i$. Then $$\sum_{i=1}^m b_i = \sum_{i=1}^m \sum_{j=1}^i 2^{i-j}c_j = \sum_{j=1}^m (2^j-1)c_{m+1-j}$$ and we have a bijection between the set of sequences $b_i$ and the set of sequences $a_i$, as desired.

Consider the following bijection: Say there exist an infinite number of buckets labeled $1, 2, 3, \dots$. Note that since each $a_i$ is exactly one less than a power of $2$, it is equal to the sum of powers of $2$, namely $1+2+\dots+2^\ell$ for some $\ell \ge 0$. Throw these powers of $2$ into the bucket labeled $i$. Now we can produce a working sequence $(b)$ by simply taking out the largest value in each nonempty bucket and letting their sum be $b_1$ (without putting them back in), and repeating the process with $b_2, b_3, \dots$. This works since after taking out a value from a bucket, the next value is either $0$, or exactly half of the previous one taken out, so the resulting sum must be at most one half of the previous sum, i.e. $b_{j+1} \le \frac12 b_j$ for all $j$. Now for its inverse, we start from $b_m$ to $b_1$, moving along the buckets from $1, 2, 3, \dots$, and dividing up'' the number by placing powers of two equal to twice the largest value currently in that bucket in any nonempty bucket, and $1$ into any empty buckets until there is nothing left to give away. It will always be able to give the wanted power of $2$ into all the nonempty buckets because failing to do so would mean that $b_j < 2b_{j+1}$, impossible. Thus, in the end, we simply total up the values in the buckets to find $(a)$, and all these values are one less than a power of $2$. We have shown the necessary bijection, so we are done. $\blacksquare$

Wow this is nice Write $n = b_1 + b_2 + \cdots + b_m = (b_1-2b_2) + 3(b_2 - 2b_3) + 7(b_3 - 2b_4) + \cdots + (2^{m-1}-1)(b_{m-1} - 2b_m) + (2^m - 1)b_m$, so this corresponds to an $A(n)$ sequence where $2^k - 1$ appears with multiplicity $b_{k} - 2b_{k+1}$ (define $b_{m+1} = 0$ for convenience), conversely, in an $A(n)$ sequence, with $2^i$ having multiplicity $x_i$, we can recursively recreate the $b_i$, starting from $b_m$, so there is a bijection between the $A(n)$ and $B(n)$ sequences and so the number of such sequences are equal, done. $\blacksquare$

Consider the following partition of the numbers in the sequence $\{b_n\}$: $$\begin{align*} b_1 &= x_1 \\ b_2 &= 2x_1 + x_2 \\ b_3 &= 4x_2 + 2x_2 + x_3 \\ \vdots & \\ b_m &= 2^{m-1} x_1 + 2^{m-2} x_2 + \cdots + x_m. \end{align*}$$ Obviously, choosing a unique $m$-tuple of nonnegative integers (note that the integers can equal zero) is a bijection to choosing the $b_i$. Now, sum the columns vertically; let the first nonzero sum be a constant times $a_1$, second nonzero sum to be a constant times $a_2$, and so on. Every such sequence of $a_i$'s that are one less than a power of two can be broken into such components; furthermore, by using the sum of a geometric series and factoring out each $x_i$ term from the column sum, each array of $x_i$'s will produce a unique sequence $\{a_n\}$. Thus, both sequences biject to the sequence $\{x_i\}$, so $A(n) = B(n)$ by the bijection.

Just use a slightly smarter version of the partition bijection. Similar to proving $\sum \left \lfloor \frac{n}{k} \right \rfloor = \sum d(k)$

Let we write the sequence $b_i$ as follows $$\begin{align*} &b_m=1+c_m\\ &b_{m-1}=2+2c_m+c_{m-1}\\ &b_{m-2}=4+4c_m+2c_{m-1}+c_{m-2}\\ &\vdots\\ &b_1=2^{m-1}+2^{m-1}c_m+2^{m-2}c_{m-1}+\ldots+c_1 \end{align*}$$ $$n=b_1+b_2+\ldots+b_m= c_1 + 3c_2 + 7c_3 + 15c_4 + \dots + (2^{m-1}-1) c_{m-1} + (2^m-1)(c_m + 1).$$ And now we have an obvious bijection between $A(n)$ and $B(n)$.

We write each $b_{i}$ as $2b_{i+1}+x_{i}$, and $b_{m} = x_{m}$. Thus, we have $$\begin{align*} b_{m} &= x_{m} \\ b_{m-1} &= 2x_{m}+x_{m-1} \\ b_{m-2} &= 4x_{m}+2x_{m-1}+x_{m-2} \\ \cdots \\ b_{1} &= 2^{m-1}x_{m}+2^{m-2}x_{m-1}+\cdots + x_{1} \end{align*}$$ If instead of summing horizontally, we sum vertically, we get $n = (2^{m}-1)x_{m}+(2^{m-1}-1)x_{m-1}+\cdots+ x_{1}$ which can be written as a sum of $2^{k}-1$, which shows the bijection.

oops i like did not see the sequence thing but wtv a solve is a solve In fact, we will show that for each sequence $\{a_i\}$ that satisfies the first property there is exactly one sequence $\{b_j\}$ that satisfies the second condition. Place each of the terms of $\{a_i\}$ in boxes $B_1$, $B_2$, $\dots$, $B_a$ so that box $B_p$ contains exactly the terms that are $2^p-1$ only. Consider $b_1 = \lvert B_a \rvert$ and for $q = 1$, $2$, $\dots$, $a - 1$ let $b_{q+1} = \lvert B_{a-q} \rvert + 2b_q$ - this clearly satisfies the second condition and moreover the sums of the two sequences are equal. For the reverse direction, we use the same boxes as earlier, but this time we place stuff into it. Let $B_a$ have $b_1$ elements and for $p = 1$, $2$, $\dots$, $a-1$ let $B_{a-p}$ have $b_{p+1} - 2b_p$ elements - this also clearly produces a valid sequence $\{a_i\}$ with the same sum as $\{b_j\}$, so we are done.

Let $c_i$ be a sequence defined as $c_i=b_i-2b_{i+1}$ for all $i$ with $1 \le i \le m-1$ and $c_m=b_m.$ Consider a sequence $d_i$ with $d_1 \ge d_2 \ge \dots \ge d_k$ such that the number $2^i-1$ appears $c_i$ times in the sequence $d_i.$ Notice that $d_1+\dots+d_k=\sum_{i=1}^{m-1} c_i(2^i-1)=b_m(2^m-1)+\sum_{i=1}^{m-1} (b_i(2^i-1)-b{i+1}(2^{i+1}-2))=b_1+\dots+b_m=n.$ Therefore, $B(n)$ equals the number of sequences $d_i$ with $d_1+\dots+d_k=n.$ However, these sequences are identical to the sequences $a_i,$ so $A(n)=B(n).$

We can let $x_i$ be the nonnegative value such that $b_j + x_j = 2b_{j+1}$. Notice that we have $$\begin{align} b_m &= b_m \\ b_{m-1} &= 2b_m + x_{m-1} \\ b_{m-2} &= 4b_m + 2x_{m-1} + x_{m-2} \\ b_{m-3} &= 8b_m + 4x_{m-1} + 2x_{m-2} + x_{m-3} \\ & \vdots \end{align}$$ Summing up all of these we get $$(2^m - 1) b_m + (2^{m-1} -1)x_{m-1} + (2^{m-2} -1)x_{m-2} \ldots 3x_2 + x_1$$ We can see that this expression is unigue for all sequences $b$. Now we can see that the sequece of $b_i$ $i$'s for all $i$ works for $A$. $\blacksquare$

basically i am pattern (enjinir)

Sketch The main idea is that taking $1$ off $b_m$, $2$ off $b_{m-1}$, $4$ off $b_{m-2}$, etc is the same as having $2^m-1$ in the sequence $a$. Taking $1$ off $b_{m-1}$, $2$ off $b_{m-2}$, $4$ off $b_{m-3}$, etc is the same as having $2^{m-1}-1$ in the sequence $a$, etc. This creates a bijection.

Let $b_1 \ge b_2 \ge \dots \ge b_m$ be a sequence of positive integers such that $b_i \ge 2b_{i+1}$ for all $1 \le i \le m-1$ and let $k_i = b_i - 2b_{i+1}$. Then note that $n = b_1 + b_2 + \dots + b_m = b_m(2^m - 1) + k_{m-1}(2^{m-1} - 1) + k_{m-2}(2^{m-2} - 1) + \dots + k_1(2^1 - `1)$. Note that $b_m \ge 1$ and $k_i$'s are nonnegative, so $B(n)$ is the number of sequences $a_1 \ge a_2 \ge \dots \ge a_k$ of positive integers for which $a_1 + a_2 + \dots + a_k = n$ and $a_i + 1$ is a power of 2 for all $1 \le i \le k$, thus $A(n) = B(n)$. $\blacksquare$

Consider a new sequence of integers $\{c_m\}$ with $c_m \ge 1$ and $c_i \ge 0$ defined by $$\begin{align*} b_m &= c_m \\ b_{m-1} &= 2c_m + c_{m-1} \\ b_{m-2} &= 4c_m + 2c_{m-1} + c_{m-2} \\ &\cdots \\ b_1 &= 2^{m-1}c_m + \ldots + 2c_2 + c_1. \end{align*}$$ Summing gives $$\sum a_i = n = \sum b_i = (2^m-1)c_m + \ldots + (2^1-1)c_1.$$ Thus we can establish a bijection between the solutions to $\{a_n\}, \{b_n\}$, as desired. $\blacksquare$

The main insight is that $A(n)=B(n)$ equals the number of ways to choose a multi-subset of $\{2^{1}-1, 2^2-1,2^3-1\cdots \}$ with elements-sum equal to $n.$ It is obvious for $A$ so we only prove it for $B.$ To see this, define $c_i=b_i-2b_{i+1}$ for $i=1,\cdots m-1$ and observe that, $$\begin{align*} &b_m = b_m \\ &b_{m-1} = 2b_m + c_{m-1} \\ &b_{m-2} = 4b_m +2c_{m-1} + c_{m-2} \\ \vdots \\ &b_1 = 2^{m-1}b_m + 2^{m-2}c_{m-1} +\cdots +2c_2 + c_1 \end{align*}$$ Summing up, we get $n=\sum b_i = b_m(2^m-1) +c_{m-1}(2^{m-1})+\cdots 3c_2 + c_1.$ Note that each sequence $(b_i)_{i=1}^m$ corresponds to multi-subset of $\{2^{1}-1, 2^2-1,2^3-1\cdots \}$ with $b_m$ biggest elements $2^m-1$ and with $c_i$ elements $2^{i}-1$ and vice-versa. Thus the one-to-one correspondance and $A(n)=B(n).$