Let A(n) denote the number of sequences a1≥a2≥⋯≥ak of positive integers for which a1+⋯+ak=n and each ai+1 is a power of two (i=1,2,⋯,k). Let B(n) denote the number of sequences b1≥b2≥⋯≥bm of positive integers for which b1+⋯+bm=n and each inequality bj≥2bj+1 holds (j=1,2,⋯,m−1). Prove that A(n)=B(n) for every positive integer n. Senior Problems Committee of the Australian Mathematical Olympiad Committee
Problem
Source: APMO 2017, problem 3
Tags: combinatorics, APMO
14.05.2017 18:43
BartSimpsons wrote: Let A(n) denote the number of sequences a1≥a2≥⋅≥ak of positive integers for which a1+⋯+ak=n and each ai+1 is a power of two (i=1,2,⋯,k). Let B(n) denote the number of sequences b1≥b2≥⋯≥bm of positive integers for which b1+⋯+bm=n and each inequality bj≥2bj+1 holds (j=1,2,⋯,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 ∀k and B(2)=1 because m=1,b1=2 is the only solution.
14.05.2017 18:55
aviateurpilot wrote: for n=2, A(2)=0 because we can't find such sequence ∀k and B(2)=1 because m=1,b1=2 is the only solution. A(2)=1 because the sequence 1,1 works.
14.05.2017 18:58
Consider the set Sdef:={(2k−1)|k⩾ 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...
14.05.2017 19:30
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
14.05.2017 20:02
wasn't this pretty easy for an apmo.I think the motivation is the dummy variable concept which has been seen a lot before.
15.05.2017 00:44
ignore...
15.05.2017 01:06
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.
18.05.2017 22:06
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.
21.05.2017 10:20
It's on OEIS. https://oeis.org/search?q=A000929&language=english&go=Search
22.05.2017 02:00
12.08.2019 03:54
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,\ldotsare linearly independent, or that (1,0,0,\ldots),(1,2,0,0,\ldots),(1,2,4,0,0,\ldots),\ldotsare 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.
12.08.2019 05:03
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 ys 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).
18.12.2019 10:32
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}.
02.03.2020 12:43
here is an oldest source: Kürschák competition 2011
16.06.2020 21:59
An older source: PFTB 8.13, which was proposed by D.R.Hickerson to AMM(as the book said).
26.06.2020 21:09
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,\vdotsb_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.
05.09.2020 05:35
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
21.09.2020 02:11
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 writeb_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_iso 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
22.11.2020 20:17
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_iwhere 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=nand 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.
29.12.2020 05:12
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.
11.01.2021 00:18
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} = nSo 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).
14.02.2021 14:46
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.
14.06.2021 15:14
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
24.08.2021 22:06
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.
28.08.2021 07:49
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
10.03.2022 07:02
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
13.06.2022 02:18
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.
09.03.2023 23:04
Just use a slightly smarter version of the partition bijection. Similar to proving \sum \left \lfloor \frac{n}{k} \right \rfloor = \sum d(k)
02.05.2023 22:00
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).
22.06.2023 18:59
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.
23.08.2023 01:40
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.
14.10.2023 00:45
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).
18.12.2023 17:11
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_1We 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
22.12.2023 20:07
basically i am pattern (enjinir)
02.01.2024 00:41
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.
26.03.2024 14:23
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
29.12.2024 03:37
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
05.01.2025 17:51
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).