we suppose that $ n = \sum_{k = 0}^{m}n_k2^{k}$ where $ n_k\in\{0,1\}$ $ a(n)\le 2a( \sum_{k = 0}^{m - 1}n_k2^{k} ) + 2n_ma(2^{m})\le..\le \sum_{k = 0}^{m}2^{m + 1 - k}n_ka(2^{k} )$ $ a(n)\le \sum_{k = 0}^{m}\frac {2^{m + 1 - k}}{(k + 1)^c}$ i don't know if $ \sum_{k=0}^{m}\frac{2^{m+1-k}}{(k+1)^c}$ is bounded, i will see

aviateurpilot wrote: i don't know if $ \sum_{k = 0}^{m}\frac {2^{m + 1 - k}}{(k + 1)^c}$ is bounded, i will see Unfortunately $ \sum_{k = 0}^{m}\frac {2^{m + 1 - k}}{(k + 1)^c} \ge \frac {2^{m + 1 }}{(1)^c}$ is unbounded

I have a completely different solution. Consider the binary representation of $ n$ and suppose $ n$ has at least ten digits in this representation. For convenience, put $ a_0 = 0.$

Repetitive application of $ a_{\alpha+\beta} \leq 2 (a_\alpha + a_\beta)$ yields \[ a_n \leq 2 a_{A_0} + 2 a_{n - A_0} \leq 2 a_{A_0} + 4 a_{A_1} + 4 a_{n - A_0 - A_1} \leq \cdots \leq \sum_{i \geq 0} 2^{i+1} a_{A_i}\] Let $ m$ be an arbitrary integer, the binary representation of $ m$ consisting of $ k + 2^t$ digits, the last $ k$ of which $ 0,$ we will call such an integer a $ (k,t)-$integer. Suppose $ m_1$ is the integer obtained by erasing the first $ 2^{t-1}$ digits of $ m,$ so that $ m_1$ and $ m - m_1$ are $ (k, t-1)-$ and $ (k + 2^{t-1}, t - 1)-$integers, respectively. Then induction on $ t$ and usage of the fact $ a_m \leq 2 (a_{m_1} + a_{m - m_1})$ proves that $ a_m \leq \tfrac{2^{2t}}{(k+1)^c}.$ In particular, $ A_i$ has $ \tfrac {1}{2^w-1} (2^{w(i+1)} - 1)$ digits, and $ \tfrac {1}{2^w - 1} (2^{wi} - 1)$ trailing zeros, hence a rough estimate is $ a_{A_i} \leq \tfrac{2^{2wi}}{2^{cw(i-1)}}.$ This means \[ a_n \leq \sum_{i \geq 0} 2^{2wi + i + 1 - cw(i-1)} = 2^{1+cw} \sum_{i \geq 0} 2^{2(w+1)i - cwi}\] But $ w > \tfrac{2}{c-2}$ so $ 2(w+1)i < cwi,$ so the above sum converges, and we are done.

What a great problem! We write $m=2^{x_1}+...+2^{x_l}$ where $x_i+1 \ge i$ and let's call $(y_1,...,y_l)$ a "valid split" if we can partition $\{ 1,...,l \}$ into 2 sets, each of which is partitioned into two sets, each of which is partitioned into 2 sets, etcetera (until we reach a set with only 1 element, and we no longer partition it) in such a way that the number $i$ belongs to $\le y_i$ sets. Then if we look at $m=(2^{\text{something}}+...+2^{\text{something}}) + (2^{\text{something}}+...+2^{\text{something}})$ and we keep partitioning $m$, then we will arrive at $m \le \sum a(2^{x_i})2^{y_i} \le \sum \frac{2^{y_i}}{i^c}$. Thus it is enough to have $2^{y_i} = \mathcal{O}(i^{c-1-\epsilon})$, for some $\epsilon >0$, since $\sum \frac{1}{i^{1+\epsilon}}$ converges. Now we do the "greedy" algorithm (kinda), let $\gamma = c-1-\epsilon >1$ and take $2^{y_l}= \lfloor i^{\gamma} \rfloor 2^C$, where $\lfloor x \rfloor$ means the biggest power of $2$ that is $\le x$ and $C$ a constant we haven't decided yet, and do it again for $l-1$, and repeat. How do we know that the resulting $(y_1,...,y_l)$ is a valid split? Notice how $\sum 1/2^{y_i} \le (2/2^C) \left( \sum 1/i^{\gamma} \right) < (2^{1-C}) \zeta (\gamma)$, and for an adequate choice of $C$, this is $<1$. Thus all that remains is to prove that if $(y_1,...,y_l)$ are such that $\sum 2^{-y_i} < 1$, then it's a valid split. But this is very easy. I prove by induction on $l$ that if $\sum 2^{-y_i} \le 1$, then it's valid split. Base case is trivial ($l=2, y_1=y_2=1$). For the inductive step, I prove the following lemma which kills it by strong induction: Lemma: If we have some (at least 2) numbers $2^x$ with $x$ natural, and their sum is $\le 2^M$, then we can partition them into two sets, each with sum $\le 2^{M-1}$ Proof: If we have two equal powers $2^m=2^m$, then "merge" them into one: $2^{m+1}$. (unless $m+1=M$). (Note: $m=M$ is impossible since we have at least 2 numbers). Repeat until the only powers that repeat (possibly) are $2^{M-1}$. If we are left with >1 $2^{M-1}$'s, then we are left with exactly two and nothing more, and the partition is clear. Otherwise, we are left with 1 or 0 $2^{M-1}$'s. So we can view it as a binary number $1101101001001$ or something like that. Let the first set in the partition be the highest power of $2$ that occurs, and the other set of the partition be the other powers of $2$, and this satisfies, so we're done.

The key idea is the following: If positive integers $a_1,a_2,\ldots,a_k$ satisfy $\sum_{i=1}^k\frac1{2^{a_i}}=1$, then for any positive integers $n_1,n_2,\ldots,n_k$ with $n=n_1+n_2+\cdots+n_k$ we have that $a(n)\le\sum_{i=1}^k2^{a_i}a(n_i)$. The proof of this is not very difficult, just note that the largest number among $a_1,a_2,\ldots,a_k$ must appear at least twice in order for the sum of their reciprocals to be 1. If $a_i=a_j=\max(a_1,a_2,\ldots,a_k)$, then $2^{a_i-1}a(n_i+n_j)\le2^{a_i}a(n_i)+2^{a_j}a(n_j)$, so we can combine $n_i,n_j$ into $n_i+n_j$, replace $a_i,a_j$ with $a_i-1$, and induct down. In fact, we can even show that this still holds when we relax the condition to $\sum_{i=1}^k\frac1{2^{a_i}}\le1$. This is as we can continually decrease $\max(a_1,a_2,\ldots,a_k)$ by 1 to obtain a smaller value for $\sum_{i=1}^k2^{a_i}a(n_i)$ while preserving $\sum_{i=1}^k\frac1{2^{a_i}}\le1$. Eventually we will have $\sum_{i=1}^k\frac1{2^{a_i}}=1$, which proves the bound by the previous paragraph. Now, let $X=\sum_{i=1}^{\infty}i^{-\frac c2}$ and define the sequence $b_0,b_1,\ldots$ by $b_i=\left\lceil\log_2(X(i+1)^{\frac c2})\right\rceil$. We have for any $k$ that $\sum_{i=0}^k\frac1{2^{b_i}}\le\sum_{i=0}^k\frac1{X(i+1)^{\frac c2}}<\sum_{i=0}^\infty\frac1{X(i+1)^{\frac c2}}=1$. Now, suppose that $n=2^{c_0}+2^{c_1}+\cdots+2^{c_k}$ is the binary representation of $n$ with $c_0<c_1<\cdots<c_k$. Then, we know that \[a(n)\le\sum_{i=0}^k2^{b_i}a(2^{c_i})\le\sum_{i=0}^k\frac{2^{b_i}}{(c_i+1)^c}\le\sum_{i=0}^k\frac{2^{b_i}}{(i+1)^c}\le\sum_{i=0}^k\frac{2X(i+1)^{\frac c2}}{(i+1)^c}<\sum_{i=0}^\infty\frac{2X}{(i+1)^{\frac c2}}=2X^2\]so $a(n)$ is bounded as desired.

Can somebody explain where I'm understanding the problem wrongly/making an error since I'm getting an "example" of a sequence which is unbounded (I didn't read the above solutions since I didn't solve it yet) for $c = 3$ ? Thanks. This seems very very wrong wrote: Define inductively $$ \displaystyle a_i = \begin{cases} \frac{1}{(j+1)^3} & \text{ if } i= 2^j \text{ for some integer j} \\ \min_{1 \leq j \leq i-1}2*(a_j + a_{i-j}) & \text{ otherwise }

that this sequence satisfies the question's criterion and for $i \geq 2$, we have $a_{2^{i}-1} = \frac{ 2^{i-2}}{(i-1)^3} + \sum_{0 \ \leq j \leq i-2} \frac{2^{j}}{(j+1)^3}$ which is divergent

Very nice problem! In my experience, this problem the type where it can be useful to $\textbf{\textsf{imagine the form}}$ of the Solution. (Before finding one, of course) Also, as it's a crime to prove a sequence is bounded without explicitly stating the bound beforehand: I claim that $a_n$ is at most $2C^2$, where \[ C = \sum_{i=1}^{\infty} \dfrac{1}{i^{c/2}}. \]To be exact, since the sum is bounded, $C$ is the limit of the RHS. Before focusing on bounding $a_n$ for all $n$, let's prove that $C$ is bounded first: $\color{green} \rule{8.5cm}{2pt}$ $\color{green} \clubsuit$ $\boxed{\textbf{Similar to Bounding the Harmonic Series.}}$ $\color{green} \clubsuit$ $\color{green} \rule{8.5cm}{2pt}$ There exists $C \in \mathbb{R}$ as described above. $\color{green} \rule{25cm}{0.2pt}$ $\color{green} \spadesuit$ $\boxed{\textbf{Proof.}}$ $\color{green} \spadesuit$ Let $c = 2 + d$ and $\frac{c}{2} = 1 + \epsilon_2$ (note that $d = 2 \cdot \epsilon_2$). This isn't really necessary, but I think it's better said this way --- so that we're clear which exponents range around which numbers. Now, we bound $\zeta(1+\epsilon_2)$: \begin{align*} \sum_{i=1}^{\infty} \dfrac{1}{i^{c/2}} &= \dfrac{1}{1^{1+\epsilon_2}} + \left( \dfrac{1}{2^{1+\epsilon_2}} + \dfrac{1}{3^{1+\epsilon_2}}\right) + \left( \dfrac{1}{4^{1+\epsilon_2}} + \cdots + \dfrac{1}{7^{1+\epsilon_2}}\right) + \cdots \\ &< \dfrac{1}{1^{1+\epsilon_2}} + \dfrac{2}{2^{1+\epsilon_2}} + \dfrac{4}{4^{1+\epsilon_2}} + \cdots \\ &= 1 + \dfrac{1}{2^{\epsilon_2}} + \dfrac{1}{4^{\epsilon_2}} + \dfrac{1}{8^{\epsilon_2}} + \cdots \\ &= \dfrac{1}{1-\frac{1}{2^{\epsilon_2}}} \in \mathbb{R}^{+} \end{align*}This statement is proven, as a bounded (positive) series will have a limit. $\blacksquare$ Next, we tackle the problem in its more basic form. $\color{magenta} \rule{8.6cm}{2pt}$ $\color{magenta} \clubsuit$ $\boxed{\textbf{Working in Sets to Visualise the Partition.}}$ $\color{magenta} \clubsuit$ $\color{magenta} \rule{8.6cm}{2pt}$ Fix a $n \in \mathbb{N}$, and let $\mathcal{P}_{ [n] }$ to be the power set of $[n]$ (i.e. the set of all subsets of $\{1,2,\ldots,n\}$. Next, define a function $A: \mathcal{P}_{[n]} \rightarrow \mathbb{R}_0^{+}$ so that \[ A_{S \cup T} \leq 2 A_{S} + 2 A_{T}; \quad \forall S,T \in \mathcal{P}_{[n]} \]where $A_S$ is the image of the set $S$ under $A$. To smooth definitions (and to give a bit more closure for $A$'s range), let the empty set's image to be zero. We attempt to bound $A_{[n]}$ as follows: define $f(k)$ so that \[ f(k) = 2^{u_k}, u_k \in \mathbb{N}; \quad \sum_{i=1}^{n} \dfrac{1}{f(i)} \leq 1 \]Then, \[ A_{[n]} \leq \sum_{k=1}^{n} A_{ \{k\} } f(k) \]$\color{magenta} \rule{25cm}{0.2pt}$ $\color{magenta} \spadesuit$ $\boxed{\textbf{Proof.}}$ $\color{magenta} \spadesuit$ First, let $A_{ \{k\} } = A_k$, $P(S,T)$ be the $A$'s assertion on the sets $S$ and $T$, and $g(k) = \dfrac{1}{f(k)}$ for brevity. Also, we may assume that \[ \sum_{i=1}^{n} \dfrac{1}{f(i)} = \sum_{i=1}^{n} g(i) \geq \dfrac{1}{2} \]as we can let $f(k)$ to be half its original size for all $1 \leq k \leq n$ (and still retaining its $2^{u_k}$ form.)

The key step in proving this is working one step backwards: if we have found a set $S = \{i_1,i_2,\ldots,i_m\}$ so that \[ \sum_{j=1}^{m} g(i_j) = \dfrac{1}{2}, \]we're set by taking $P(S,[n]-S)$ (and induct) since the rest of the $g(i)$s have sum at most $\frac{1}{2}$.

This can be done by rearranging $g(i)$ from largest to smallest: assume that $g(i) \geq g(j)$ whenever $i \leq j$. Pick the first index $m$ so that \[ \sum_{i=1}^{m} g(i) \geq \dfrac{1}{2} \]We will prove that this sum is exactly $\frac{1}{2}$. Let $g(m) = \dfrac{1}{2^M}$. So, all terms $g(i)$ with $i \leq m-1$ is greater than $\dfrac{1}{2^M}$; so their sum have denominator at most $2^M$ (since all their denominators are $2^{d}$ dividing $2^M$ as $d \leq M$). In turn, this implies that \[ \sum_{i=1}^{m-1} g(i) \leq \dfrac{2^{M-1}-1}{2^M}. \]This is because there are no numbers in the interval $\left(\frac{2^{M-1}-1}{2^M},\frac{1}{2} \right)$ have denominator $2^M$ or less. Immediately, we know that this number, added with $g(m)$, cannot exceed $\frac{1}{2}$. We have the desired conclusion. $\blacksquare$ $\blacksquare$ After reaching this point, the direction to solve the problem should be much clearer --- the algorithm to create $A_k f(k)$ has transformed the problem into a construct-the-function problem. For brevity, let $a(n) = a_n$ and $a(2^k) = A_{k+1}$. We set out to proving that $a_n \leq 2C^2$ for any $n \in \mathbb{N}$. $\color{cyan} \rule{7.9cm}{2pt}$ $\color{cyan} \diamondsuit$ $\boxed{\textbf{Small (and non-central) Optimization.}}$ $\color{cyan} \diamondsuit$ $\color{cyan} \rule{7.9cm}{2pt}$ Since we can avoid multiple $A_k$s showing up in $a_n$'s expansion simply by only picking $a(2^i)$ only if $2^i$ is in $n$'s binary expansion, we do exactly that. Formally, let $n = 2^{i_1}+2^{i_2}+\ldots+2^{i_k}$ with $0 \leq i_1 < i_2 < \ldots < i_k$. Observe that since \[ A_{i_k} \leq \dfrac{1}{(i_k+1)^c} \leq \dfrac{1}{k^c}, \]we can assume that $i_k = k-1$ and only prove this for $n = 2^0+2^1+\ldots+2^{k-1}$ (basically do the same thing for $n = 2^{i_1}+2^{i_2}+\ldots+2^{i_k}$ as $n' = 2^k-1$, but $n$'s bound is a bit looser.) $\color{cyan} \rule{25cm}{0.2pt}$ I wouldn't call this an easy finishing, but it remains to establish $f(k)$ to demolish the problem. $\color{blue} \rule{6.1cm}{2pt}$ $\color{blue} \diamondsuit$ $\color{blue} \boxed{\textbf{Finishing: Mostly Counting.}}$ $\color{blue} \diamondsuit$ $\color{blue} \rule{6.1cm}{2pt}$ Set $f(k)$ to be the smallest power of two at least \[ n^{1+\epsilon_2} \cdot \sum_{i=1}^{\infty} \dfrac{1}{n^{1+\epsilon_2}} = C \cdot n^{1+\epsilon_2}. \]It is verifiable that $\sum_{i=1}^{N} g(i) \leq 1$ for any $N \in \mathbb{N}$, and \[ f(k) \leq 2C \cdot n^{1+\epsilon_2} = O(n^{1+\epsilon_2}). \] To replicate what we did on $\color{magenta} \clubsuit$ $\boxed{\textbf{Working in Sets to Visualise the Partition}}$ $\color{magenta} \clubsuit$, set $A_S$ to be the value of \[ a_{s'}, \ \text{where} \ s'= \sum_{i \in S} 2^i. \]We can verify the validness of $P(S,T)$ by the problem condition on $a(m+n) \leq 2a(m) + 2a(n)$. $\color{blue} \rule{6.1cm}{0.2pt}$ By $\color{magenta} \clubsuit$ $\boxed{\textbf{Working in Sets to Visualise the Partition}}$ $\color{magenta} \clubsuit$, we get \begin{align*} a_{2^n-1} = A_{[n]} &\leq \sum_{k=1}^{n} A_kf(k) \\ &= \sum_{k=1}^{n} \dfrac{1}{k^{2+d}} \cdot O(k^{1+\epsilon_2}) \\ &= \sum_{k=1}^{n} O\left(\dfrac{1}{k^{1+\epsilon_2}}\right) \\ &\leq 2C^2. \end{align*}We are done. $\blacksquare$ $\blacksquare$ $\blacksquare$

Nice problem! I wonder why I hadn't tried this before. Note that there are two ways of expanding $a(n)$ into a sum: Lemma: Let $n=b_1+b_2+ \cdots +b_k$ where each $b_i$ are positive integers. Then, (i) $a(n) \leq \sum_{i=1}^k 2^i a(b_i)$ (ii) $a(n) \leq 2^{\lceil \log_2(k) \rceil} \sum_{i=1}^k a(b_i)$ Proof: We prove both using strong induction on $k$. When $k=1$, $$a(n)=a(b_1)=2^{\lceil \log_2(1) \rceil} a(b_1) \leq 2 a(b_1)$$Now assume that both the inequalities are true for all $k<m$, and let $n=b_1+b_2+ \cdots +b_m$. For (i), we have $$a(n) \leq 2a(b_1)+2a(b_2 + \cdots + b_m) \leq 2a(b_1)+2 \sum_{i=2}^m 2^{i-1} a(b_i)= \sum_{i=1}^m 2^i a(b_i)$$by induction hypothesis. For (ii), note that for $m \geq 2$, $$\left \lceil \log_2 \left( \left \lfloor \frac{m}{2} \right \rfloor \right) \right \rceil \leq \left \lceil \log_2 \left( \left \lceil \frac{m}{2} \right \rceil \right) \right \rceil = \lceil \log_2(m) \rceil -1$$Therefore, by induction hypothesis, \begin{align*} a(n) & \leq 2a(b_1+ \cdots +b_{\lfloor \frac{m}{2} \rfloor})+2 a(b_{\lfloor \frac{m}{2} \rfloor+1}+ \cdots +b_m) \\ & \leq 2^{\lceil \log_2( \lfloor \frac{m}{2} \rfloor) \rceil+1} \sum_{i=1}^{\lfloor \frac{m}{2} \rfloor} a(b_i) + 2^{\lceil \log_2( \lceil \frac{m}{2} \rceil) \rceil+1} \sum_{j=\lfloor \frac{m}{2} \rfloor+1}^m a(b_j) \\ & \leq 2^{\lceil \log_2(m) \rceil} \sum_{i=1}^m a(b_i) \end{align*}and we are done. $\blacksquare$ Note that, using $\lceil \log_2(k) \rceil < \log_2(k)+1$, we can write (ii) of the above lemma as: $$a(n) \leq 2k \sum_{i=1}^k a(b_i)$$ Now, let $d>2021+2^{\frac{1}{c-2}}$ be a fixed positive integer. Let $n$ be any positive integer. Write $n=2^{b_1}+ \cdots + 2^{b_l}$ in binary form, with $b_1<b_2< \cdots <b_l$, and let $k$ be the smallest positive integer satisfying $$d+d^2+ \cdots + d^k \geq l$$Let $e_0=0$, let $e_i=d+d^2+ \cdots + d^i$ for $1 \leq i \leq k-1$, and let $e_k=l $. Further, let $$p_i=2^{b_{e_{i-1}+1}}+2^{b_{e_{i-1}+2}}+ \cdots + 2^{b_{e_i}}$$for $1 \leq i \leq k$. Note that each $p_i$ consists of $e_i-e_{i-1} \leq d^i$ summands, and $n=p_1+p_2+ \cdots p_k$. Using part (ii) of the lemma, we get \begin{align*} a(p_i) & \leq 2(e_i-e_{i-1}) \sum_{j=e_{i-1}+1}^{e_i} a(2^{b_j}) \\ & \leq 2d^i \sum_{j=e_{i-1}+1}^{e_i} \frac{1}{(b_j+1)^c} \\ & \leq 2d^i \frac{e_i-e_{i-1}}{(b_{e_{i-1}+1}+1)^c} \ \ \dots \ \text{(since } b_j \text{ is a strictly increasing sequence)} \\ & \leq \frac{2d^{2i}}{(e_{i-1}+1)^c} \ \ \dots \ \text{(since } b_j \geq j-1 \text{ for each index } j \text{)} \\ & \leq \frac{2d^{2i}}{d^{c(i-2)}} \ \ \dots \ \text{(since } e_j \geq d^{j-1}-1 \text{ for all } j \geq 0 \text{)} \\ \end{align*}$$\implies a(p_i) \leq \frac{2d^{2c}}{d^{(c-2)i}}$$for $1 \leq i \leq k$. Note that, by our initial assumption on $d$, $d^{c-2}>2$. Therefore, using part (i) of the lemma, we have \begin{align*} a(n) & \leq \sum_{i=1}^k 2^i a(p_i) \\ & \leq \sum_{i=1}^k \frac{2d^{2c} \cdot 2^i}{d^{(c-2)i}} \\ & < 2d^{2c} \sum_{i=1}^\infty \left ( \frac{2}{d^{c-2}} \right )^i \end{align*}$$\implies a(n) < \frac{2d^{2c}}{\frac{d^{c-2}}{2}-1} \ \ \text{ for all } n \geq 1$$Therefore the sequence $a(n)$ is bounded.

Ok this is wrong because s(n)+.5 isn’t the actual bound; it should be s(n)+1 if you look at 10001 which gets broken into 1001 and 1000. So then the inequality is not true for like x=2 or something which sort of breaks the entire problem. There is probably not much more to be gained learning-wise from fixing the solution (if it’s possible) so I will probably not

Nice problem, but writeup seemed like a pain, which is why I forced myself to write what follows

Comeback arc. I think this solution is pretty similar to what others have but is probably more illuminating. We begin with the following strange claim. Claim: Let $C>1$ be a real constant. There exists an infinite rooted binary tree $T$ where each leaf is labeled with a unique nonnegative integer such that the depth of the vertex with label $\ell$ is at most $\log_2(r(\ell+1)^C)$ for some positive real $r$. The depth of the root vertex is $0$. Proof: By shifting, it suffices to label leaves with unique positive integers such that the vertex with label $\ell$ is depth at most $\log_2(r\ell^C)$. Actually, we give an explicit construction of $T$. Fix a positive integer $N>1$. On layers divisible by $N$ (other than layer $0$), we set aside half of the vertices as leaves and label them with the smallest integers not already used. On every other layer, we do not form new leaves. When going from one layer to the next, every vertex not designated as a leaf receives two children. In this fashion, for every positive integer $k$ the layer $kN$ has $2^{k(N-1)+1}$ vertices, $2^{k(N-1)}$ of which are made into leaves. Thus, as a simple upper bound, the vertex with label $2^{r(N-1)}$ has depth at most $\lceil r\rceil N<(r+1)N$. To get $2^{r(N-1)}=\ell$, we take $r=\tfrac{1}{N-1}\log_2(\ell)$, so the leaf labeled $\ell$ has depth at most $$N\left(\frac{\log_2(\ell)}{N-1}+1\right)=\frac{N}{N-1}\log_2(2^{N-1}\ell)=\log_2(2^N\ell^{N/(N-1)}),$$so taking $N$ large enough such that $\tfrac{N}{N-1}<C$ works (with $r=2^N$). $\blacksquare$ Construct the tree for $C=c/2$. Fix some positive integer $k$: we will bound $a_k$. Delete all of the leaves of $T$ with labels whose corresponding digits aren't $1$ in the binary representation of $k$ (so if the $2^b$ digit is $0$ then we delete the leaf with label $b$). This leaves finitely many labels, so delete the layers below the lowest label, leaving us with a finite binary tree $T'$. Define the weight of a vertex in $T'$ to be the sum of the labels of the leaves that are descendants of it (not necessarily children). By repeatedly applying $a_{m+n} \leq 2(a_m+a_n)$ (one can think of this as "merging" two child vertices—if a child vertex has weight $0$ then define $a_0=0$ and $a_{m+0} \leq 2(a_m+a_0)$ still holds), we find (by induction) that if a vertex $v$ of weight $w$ has descendants labeled $\ell_1,\ldots,\ell_j$ whose depths are $d_1,\ldots,d_j$ more than that of $v$, then $$a_w \leq \sum \frac{2^{d_i}}{(\ell_i)^c}.$$The root vertex has weight $k$, so by the definition of $T$ we have $$a_k \leq \sum_{\text{digit } b \text{ is } 1} \frac{2^{\log_2(r(b+1)^{c/2})}}{(b+1)^c} \leq \sum_{i=0}^{\infty} \frac{r(b+1)^{c/2}}{(b+1)^c}=r\sum_{i=0} \frac{1}{(b+1)^{c/2}}<\infty,$$since $c/2>1$, i.e. $a_k$ is bounded. $\blacksquare$