Very nice problem.: My solution: $(n-2) 2^n+1$ is solution of this problem. Lemma: we can write every natural number $a\ge (n-2) 2^n+2$ as the sum of one or more elements of $A_n$. Prove: we show this by induction on $n$. Assume that it is true for $n$. Now we prove it for $n+1$ note that from induction assumption we can write every $a\ge (n-2) 2^n+2$ as a sum of some elements of $A_n$: $a=k_1(2^n-1)+k_2(2^n-2)+k_3(2^n-2^2)+\cdots +k_{n-1}(2^n-2^{n-1})\longrightarrow 2a=k_1(2^{n+1}-2)+k_2(2^{n+1}-2^2)+\cdots +k_{n-1}(2^{n+1}-2^n)$ so we can write every even natural number greater than $(n-2)2^{n+1}+4$ as the sum of elements of $A_{n+1}$(1) so it's enough to prove that every odd number greater than $(n-1)2^{n+1}+2$ as the sum of elements of $A_{n+1}$ take an odd number $b\ge (n-1)2^{n+1}+3$ note that $c=b-(2^{n+1}-1)\ge (n-2)2^{n+1}+4$ because $c$ is an even number using (1) we can write it as the sum of elements of $A_{n+1}$ hence we can write $b=c+(2^{n+1}-1)$ as a sum of elements of $A_{n+1}$ and the lemma proved hear. Now it is enough to show that we can't write $(n-2)2^n+1$ as the sum of elements of $A_n$ we prove this by induction assume that it is true for $n$ and we can't write $(n-2)2^n+1$ as sum of elements of $A_n$. Assume for a sake of a contradiction that we can write $d=(n-1)2^{n+1}+1$ as the sum of elements of $A_{n+1}$: $(n-1)2^{n+1}+1=k_1(2^{n+1}-1)+k_2(2^{n+1}-2)+\cdots +k_n(2^{n+1}-2^n)=k_1(2^{n+1}-1)+2s$ since $d$ is odd we get that $k_1=2k+1\ge 1$ is an odd number so $(n-2)2^n+1=k(2^{n+1}-1)+s$(2) it is easy to see that $s$ is the sum of elements of $A_n$ and also $2^{n+1}-1=2(2^n-2^{n-1})+2^n-1$ is the sum of elements of $A_n$ hence from (2) we deduce that $(n-2)2^n+1$ is the sum of elements of $A_n$ which contradicts our assumption. DONE

How you guess the answer?

arshakus wrote: How you guess the answer? When I saw this problem for the first time I remembered the following lemma: Lemma: $a,b$ are two natural numbers such that $\text{gcd} (a,b)=1$ then for every natural number $c> ab-a-b$ there are natural numbers $x,y$ such that $c=ax+by$. First it's obvious that for the case $n=2$ the answer is $1$. For $n=3$ note that $A_3={7,6,4}$. Because $(4,7)=1$ From the lemma every positive integer greater than $17$ can be written in a form $4k+7t$ but it is easy to see that $10,11,\cdots ,16$ can be written as the sum of elements of $A_3$ and $9$ can't be written. So from here I found that the answer for $n=3$ is $9=(2^3-2)+(2^3-2^2)-1$ from here I guessed that the answer for the case $n$ is $(2^n-2)+(2^n-2^2)+\cdots +(2^n-2^{n-1})-1=(n-2) 2^n+1$

arshakus wrote: How you guess the answer? My idea for guessing the answer was observing modulo $2^{n-1}$.I wasn trying to find the smallest numeber that we can represent as sum of elements from the set with the condition that it is congruen to modulo 1 while dividing with $2^{n-1}$.It turns out that the smallest number that we cant represent is exatcly $(n-2)\cdot 2^{n} +1$ EDIT the reason why i was observing modulo $2^{n-1}$ is tht the smallest number in the set is $2^{n-1}$ and later showed that every other residue bigger than 1 can be obtained with the condition that its smallest sum is less than when residue is1.

Let $f(n)$ be the answer for $n$.Call a number good if it can be expressed as a linear combination of the members of $A_{n+1}$ and bad otherwise.Note that any even number greater than $2f(n)$ is good,because any integer greater than $f(n)$ is good for $n$ and $f(n)+j=\sum_{i=0}^{n-1}{c_i(2^{n}-2^{i})} \implies 2f(n)+2j=\sum_{i=1}^{n}{c_{i-1}(2^{n+1}-2^{i})}$. I now show that any odd number greater than $2f(n)+2^{n+1}-1$ is good.A number of this type can be written as $2^{n+1}-1+k$.Now note that $k$ is an even number greater than $2f(n)$,and we have already shown that a number of this type is good. My next claim is that $2f(n)+2^{n+1}-1$ is bad.Suppose it is good.Then $2f(n)+2^{n+1}-1=\sum_{i=0}^{n}{c_i(2^{n+1}-2^i}$ for some set of $c_i$'s.Then $f(n)=(2^{n+1}-1)\frac{c_0-1}{2}+\sum_{i=0}^{n-1}{c_i(2^n-2^{i})}$.Now note that $2^{n+1}-1=2(2^{n}-2^{n-1})+2^n-1$.Substituting we get that $f(n)$ can be expressed as a linear combination of the members of $A_n$.This is a contradiction which proves my claim. Summing these facts we get that $f(n+1)=2f(n)+2^{n+1}-1$ with $f(2)=1$.Now a simple induction shows that $f(n)=(n-2)2^n+1$.

arshakus wrote: How you guess the answer? I commented on that in an earlier thread. http://www.artofproblemsolving.com/community/u151857h1113414p5085268 The basic idea is to look at these numbers in binary.

The answer is $(n-2)2^n+1$. For brevity, set $a_k = 2^n - 2^k$. Observe that for any $k < n-1$, we have $2a_k = a_{k+1} + 2a_{n-1}$, so assume we use at most one of each $a_k$ for all $k < n-1$. Now by considering the numbers in binary, we find that each subset of $\{a_0, \dots, a_{n-2}\}$ sum leaves a different residue modulo $a_{n-1} = 2^{n-1}$ when summed. Thus the inexpressible numbers are those of the form $\textstyle\sum_{i \in I} a_i - ca_{n-1}$ for some $c \ge 1$ and $I \subseteq \{0, \dots, n-2\}$. In particular, the largest is $\textstyle\sum_{k=0}^{n-2} \left( 2^n-2^k \right) - 2^{n-1} = (n-1)2^n - (2^{n-1}-1) - 2^{n-1} = (n-2)2^n+1$.

Notice that 2 is a member of the set hence we can write any even no as sum of 2 repeteadly n times if it is 2n to get 2n. Secondly if k = 0 then we get an odd number \(2^{n} -1\) taking n = 2 we get 3 as an element of s. So now 3 +2 is expressed as sum of elements of s I.expect 5. Now we can keep adding 2 to get all the odd no.s as well as the sum of elements of s. Hence the only odd number which can't be expressed as sum of elements of s is 1 . Every larger odd even number is expressable as the sum of elements of s.

Akash20 wrote: Notice that 2 is a member of the set Why?

Taking n=2 and k=1 we have \(2^{2} - 2\) = 2

Akash20 wrote: Taking n=2 and k=1 we have \(2^{2} - 2\) = 2 $n$ is a fixed given number, so you can't possibly take $n=2$.

Not quite clear from the question here, I got it as the set includes all the numbers which can be represented in the given form with n being a varying natural number.

Assume that maximal number that we can't achieve with $A_n$ is $f_n$. Note that $A_{n+1}=\{2^{n+1}-1\} \cup 2A_n$ where $2A_n=\{2x|x\in A_n\}$. Now since we can with $A_{n}$ achieve any number greater that $f_n$ , with$2A_n$ we can achieve any even number greater than $2f_n$.$(1)$ Note that we can't achieve $2^{n+1}-1+f_n$ but we can achieve any number greater than that(if it's even we can achieve it by $ (1)$, if it's odd subtract $2^{n+1}-1$ and then apply $(1)$). So we have that $f_{n+1}=2f_n+2^{n+1}-1$. Assume that $f_n=g(n)2^n+1$. Since $g(n+1)=g(n)+1$ and $g(2)=0$ we have that $f_n=(n-2)2^n+1$.

I have a little bit different proof that we can't write $2^n(n-2)+1$ as sum. Suppose we can do it, then \[2^n(n-2)+1=(2^n)k-(2^{a_1}+\cdots+2^{a_k})\]\[2^{a_1}+\cdots+2^{a_k}=2^n(k-n+1)+(2^1+\cdots+2^{n-2}+2^{n-1})\]So we can obviously get an inequality \[k\geq 2(k-n+1)+n \longrightarrow n-2\geq k\]so we get a contradiction.

shauneu-nm wrote: I have a little bit different proof that we can't write $2^n(n-2)+1$ as sum. Suppose we can do it, then \[2^n(n-2)+1=(2^n)k-(2^{a_1}+\cdots+2^{a_k})\]\[2^{a_1}+\cdots+2^{a_k}=2^n(k-n+1)+(2^1+\cdots+2^{n-2}+2^{n-1})\]So we can obviously get an inequality \[k\geq 2(k-n+1)+n \longrightarrow n-2\geq k\]so we get a contradiction. how is this a contradiction?? n-2 \geq k does not contradict anything.

but if we have $k\leq n-2$ then the LHS of the first equation is strictly greater than RHS.

if $a \in A_n , $ a is used when we write X then let's call $a$ loves $X$ let the element of $A_n$ $a_i : a_i > a_{i+1}$ claim(1): $x=2^{n}(n-2)+1 $ isn't pretty suppose $x $ is pretty $2^{n}(n-2)+1\equiv 1 mod 2 $then $a_1 $ loves $x$ so $2^{n}(n-2)+1 - a_1 =2{n}(n-3)+2 \equiv 2 mod 4$ so ${2a_1,a_2}$ loves $x$ (one of them or more) thus $2{n}(n-3-)+4 \alpha_1 \equiv 4 mod 8 $ then ${4a_1,2a_2,a_3}$ loves $x$ (maybe $2a_1+a_2$) but the important thing is that we always add $2^k $ and substract at least one of $2^n $ thus when we do this operation finitly we will have that $2^k : k < n-1$ is pretty which is a contradiction claim(2): any $y>x $ is pretty note that $s=\sum{a_i}=2^{n}(n-1)+1$ let's define $\Omega_k$: if $k \le n-2$ $s$ will be $s+a_{k+1}-a_k=s-a_k$ if $k=n-1$ then just use $a_n$ if $T= \{s- \gamma : \gamma \le 2^n\}$ $\gamma=(1001001.......)_2$ then we start from the left and when we see $1$ in the $k^{th}$ place we do $\Omega_k$ and if $y > s$ then let $y \equiv j mod 2^{n-1}$ where $j\in T$ let $y=2^{n-1}l+j$ and use $j$ and $a_n $ $l $times and we win

The answer is $(n-2)2^n+1$. It is not hard to check $(n-2)2^n+1$ is not a linear combination of elements of $A_n$: for binary reasons, the linear combination must include $2^n-2^k$ for each $1\le k<n$, hence \[(n-2)2^n+1\ge\sum_{k=1}^{n-1}\left(2^n-2^k\right)=(n-2)2^n+2,\]contradiction. Hence $(n-2)2^n+1$ is not expressible. We now check the upper bound. Say a number is $T$-expressible if it can be expressed as the sum of $T$ elements of $A_n$. All $k$ with $(n-2)2^n+2\le k\le(n-1)(2^n-1)$ are $(n-1)$-expressible. Indeed, $(n-1)2^n-k$ is among $1$, $2$, $\ldots$, $2^n-2$. All of these have at most $n-1$ digits in its binary representation. $~$ For $T\ge n$, All $k$ with $(T-1)(2^n-1)+1\le k\le T(2^n-1)$ are $T$-expressible. It suffices for $T\cdot2^n-k\in[T,(2^n-2)+T]$ to be expressible as $T$ elements of $\{1,2,\ldots,2^{n-1}\}$. For binary reasons, all such numbers may be expressed as the sum of at most $T$ powers of $2$. If such $k$ is expressible as $m$ powers of two, $m<T$, then $k$ can be expressed as $m+1$ powers of two: indeed, since $k\ge T$, one of these powers of two is $2^i$, with $i\ge1$. Then replace $2^i$ with two copies of $2^{i-1}$. It is easy to check that this covers all integers greater than $(n-2)2^n+1$, so we are done.

The answer is $(n-2)2^n+1$. For a residue of $2^{n-1}$ $m$, let $f(m)$ be the smallest positive integer congruent to $m$ that can be written as the sum of one or more elements of $A_n$. Claim: For any $m\neq 1$, $f(m)\le (n-2)2^n+1$ Proof: Let the binary representation of the integer $2^{n-1}-m\neq2^{n-1}-1$ be $2^{a_1}+\dots2^{a_k}$ for some nonnegative integers $a_i\le n -2$ and $k\le n-2$. Then the sum of $2^n-2^{a_1}+\dots+2^n-2^{a_k}$ is congruent to $m \mod{2^{n-1}}$ by construction, and is less than or equal to $2^n+\dots2^n=k2^n\le(n-2)2^n$ as desired. Claim:$f(1)=(n-2)2^n+2^{n-1}+1$. Proof: The sum of $2^n-2^0,\dots,2^n-2^{n-2}$ is $(n-2)2^n+2^{n-1}+1$. To show that $(n-2)2^n+1$ cannot be written as a sum of elements of $A_n$, we prove the more general fact: Claim:Let $m$ be any integer at most $k$. There do not exist non-negative integers $a_1,\dots,a_m \le n-1$ satisfying $2^{a_1}+\dots+2^{a_m}=(k-n+2)2^n-1$. Proof: We induct on $n$ and a fixed $k-n$. For $n=1$, we have all $a_i=0$ and simplifiying both sides we get the true statement $m\neq2k+1$. Suppose for all smaller $n$ our claim holds, and suppose for contradiction that there do exist $a_1,\dots,a_m$ satisfying the equation. Since the RHS is odd, we must have an odd number of $a_i=0$. WLOG assume $a_1,\dots a_p=0$, where $p$ is odd. Then rearranging our equation a bit, we get $$2^0+\dots +2^0 + 2^{a_p-1}+\dots +2^{a_m-1}=( (k-1)-(n-1)+2)2^{n-1}+1$$. We have $\frac{p-1}{2}+m-p\le k-1$ terms on the LHS so we can apply induction on $k-1$ and $n-1$ which gives a contradiction. Then, we are done

The main idea is that $A_n=\{2^n-1\} \cup 2A_{n-1}$. Let $m_n$ be the maximum number not expressible by $A_n$. We claim $m_n=1+(n-2)2^n$. Induct on $n$, with $n=1$ obvious. First, we show that $1+(n-2)2^n$ is not achievable by $A_n$. Suppose it is. Since $1+(n-2)2^n$ is odd, and the only odd element of $A_n$ is $2^n-1$, we must use $2^n-1$ an odd number of times. Suppose we use it $k$ times. Then $1+(n-2)2^n-k(2^n-1)$ is also achievable by $A_n$. Since we use $2^n-1$ no more, $\tfrac12(1+(n-2)2^n-k(2^n-1))$ is achievable by $A_{n-1}$. This means that \[ \frac{1+(n-2)2^n-k(2^n-1)}{2} + \frac{k-1}{2} \cdot (2^n-1) = 1+(n-3)2^n\]is also achievable by $A_{n-1}$, contradicting the inductive hypothesis on $n-1$. Therefore, $1+(n-2)2^n$ is not achievable by $A_n$. Now we show that every number $N>1+(n-2)2^n$ is achievable by $A_n$. If $N$ is even, then don't use $2^n-1$; since $N/2 > 1+(n-2)2^{n-1} \ge 1+(n-3)2^{n-1}$, we can get $N/2$ by $A_{n-1}$, so we can get $N$ by $2A_{n-1} \subseteq A_n$. If $N$ is odd, then use one $2^n-1$, and then we can achieve $\tfrac{N-(2^n-1)}{2}> \tfrac12(1+(n-2)2^n-(2^n-1)) = 1+(n-3)2^n$ using $A_{n-1}$.

Seems different from all the others posted here. It looks longer than most posts in this thread, but I think the presentation is actually quite simple. We claim the answer is $(n-2)2^n + 1$. First, by writing $2^n - 2^k = 2^k + 2^{k+1} + \cdots + 2^{n-1}$, we see that a positive integer can be expressed as the sum of some elements of $A_n$ if and only if it has an expression of the form \[ a_1 + 2a_2 + 2^2 a_3 + \cdots + 2^{n-1}a_n,\qquad(*) \]where $a_1 \leq a_2 \leq \cdots \leq a_n$. To prove $(n-2)2^n + 1$ is sufficient, we will actually show a stronger claim. Claim. No integer of the form $m2^n + 1$, where $m\leq n-2$, can be expressed as the sum of some elements of $A_n$. Proof. Induction. Base cases are easy. For the inductive step, suppose $m2^n + 1$ can be written in the form $(*)$ for some $m$ and $a_1,\ldots, a_n$. The fact that $(a_i)$ is increasing yields \[ m2^n + 1 \leq a_n(1+2+\cdots + 2^{n-1}) = (2^n - 1)a_n, \]which implies $a_n \geq m+1$. Then \[ a_1 + 2a_2 + \cdots + 2^{n-2}a_{n-1} = m2^n + 1 - a_n2^{n-1} = (2m - a_n)2^{n-1} + 1, \]and since $2m - a_n \leq m-1\leq n-3$ the inductive hypothesis kicks in, yielding a contradiction. $\blacksquare$ Now we show every integer greater than $(n-2)2^n + 1$ can be expressed in the desired form. Here, the key observation is that \[ A_n = \{2^n - 1\}\cup 2A_{n-1}. \]Now, if $m > (n-2)2^n + 1$, then \[ \frac{m - (2^n - 1)}{2} > \frac{(n-2)2^n + 1 - (2^n - 1)}{2} = (n-3)2^{n-1} + 1, \]and so by induction either $\tfrac 12m$ or $\tfrac 12(m - (2^n - 1))$ can be expressed as the sum of elements of $A_{n-1}$ (depending on whether $m$ is even or odd). Unravelling the above expression shows that $m$ can be expressed as the sum of elements of $A_n$.

We claim that the desired largest positive integer is $(n-2)2^n+1$. Firstly, we show that $(n-2)2^n+1$ is not achievable. Note that $$(n-2)2^n+1<(n-1)2^{n} -2^{n}+2=(n-1)2^{n} -\sum_{i=1}^{n-1} 2^{i}=\sum_{i=1}^{n-1} 2^{n}-2^{i} ,$$which essentially means that it is one less than sum of $2^{n}-2^{i}$, where $i$ decreases from $n-1$ to $1$. For the sake of contradiction, $(n-2)2^n+1$ is achievable. By modulo $2$, to achieve $(n-2)2^n+1$, the sum must contain $2^n-1$, thus we reduce our sum to $(n-2)2^n+1-2^n+1=(n-3)2^n+2$. Now by modulo $4$, this momentary sum must contain $2^n-2$ or $2^n-1$ twice. We reduce the momentary sum even further and look modulo $2^k$ in $k$-th step - in this step, we conclude that this momentary sum must contain $2^n-2^{k-1}$ once, $2^n-2^{k-2}$ twice, $\ldots$, $2^{k-1}$ times $2^n-1$. By the assumption after some step (which is at most $n-1$-th step), we achieve desired sum and thus we let $\mathcal{S}$ to denote the set of powers chosen to complete the sum. Therefore, the desired sum is $$(n-2)2^n+1=\sum_{i\in\mathcal{S}} 2^{n}-2^{i} \geq \sum_{i=0}^{n-2} 2^{n}-2^{i} >\sum_{i=1}^{n-1} 2^{n}-2^{i},$$but this contradicts the first inequality. Now, we claim that every integer bigger than $(n-2)2^n+1$ is achievable. Claim. Every integer between $2^{n-1}-1$ and $2^{n}-2$ is achievable picking $n-1$ elements from the set $\{1,2,\ldots,2^{n-1}\}$. We proceed by induction. The base case $n=2$ is trivial. Assume this is true for $n-1$, i.e. every integer is achievable between $2^{n-2}-1$ and $2^{n-1}-2$. Now, since every integer between $2^{n-2}-1$ and $2^{n-1}-2$ is achievable, adding $2^{n-2}$ to every such integer, we get that every integer is achievable between $2^{n-1}-1$ and $2^{n-1}+2^{n-2}-2$. Adding $2^{n-1}$ to every integer between $2^{n-2}-1$ and $2^{n-1}-2$, we get that every integer between $2^{n-1}+2^{n-2}-1$ and $2^{n}-2$ is achievable. Thus, in total we covered the range from $2^{n-1}-1$ to $2^{n}-2$, this completes the induction. Therefore by the claim above, we achieve every integer between $(n-1)2^n-(2^{n}-2)=(n-2)2^n+2$ and $(n-1)2^n-(2^{n-1}-1)=(n-2)2^n+2^{n-1}+1$. Now adding any number of $2^n-2^{n-1}=2^{n-1}$'s to the integer between $(n-2)2^n+2$ and $(n-2)2^n+2^{n-1}+1$, we can achieve any integer greater that $(n-2)2^n+1$. We are done.

Fun problem! Call a number happy if there exists such a sum and sad otherwise. Let $M_n$ be the largest sad number (the desired value). Claim: If $N$ is the largest even sad number then $M_n = 2^n - 1 + N$ Notice that $A_n$ has exactly one odd element. Thus, if $k$ is happy and odd then $k - (2^n-1)$ is also happy since $2^n-1$ must be included in the sum. Similarly, if $k$ is sad and odd then $k - (2^n-1)$ is also sad. Thus, we see that if $N$ is the largest sad even number then $N + 2^k - 1$ is sad. And, by assumption, all even numbers $K>N$ are happy, so $K + 2^k - 1$ is happy as well. This yields all odd and even numbers $>N + 2^k - 1$ being happy while $N + 2^k - 1$ is sad. So, $M_n = N +2^k-1$. Proving the claim. Thus, let us find the largest even sad number. Let us divide each element in $A_n$ by $2$ (except $2^n-1$) and get a new set $A_n'$. Clearly, if $T$ is the largest sad number wrt $A_n'$ then $2T$ is the largest even sad number wrt $A_n$. We have... $A_n' = \{ 2^n-1, 2^{n-1}-1, 2^{n-1}-2, 2^{n-1}-4,...,2^{n-1}-2^{n-2} \}$ Clearly, we can remove $2^n-1$ from $A_n'$ because $2^n-1 = 2^{n-1}-1 + 2^{n-2} + 2^{n-2}$ making it a sum of other elements in $A_n'$. Hence we get. $A_n' = \{ 2^{n-1}-1, 2^{n-1}-2, 2^{n-1}-4,...,2^{n-1}-2^{n-2} \} = A_{n-1}$ Which gives us the recursion $M_n = 2^n -1 +2M_{n-1}$. Realizing $M_2 = 1$ for obvious reasons, we get $M_n = (n-2)2^n + 1$.

The answer is $\boxed{(n-2)2^n+1}$. Notice that the smallest term in the set $A_n$ is $2^{n-1}$. To find the smallest positive integer that cannot be reached satisfying that it is some residue $r \pmod {2^{n-1}}$, it is clear that we can find the smallest number that is $r \pmod {2^{n-1}}$ that can be reached by all the terms excluding $2^{n-1}$, and then subtract $2^{n-1}$. Let the smallest number that is $r \pmod {2^{n-1}}$ that can be reached by all the terms excluding $2^{n-1}$ be an r-representative. We want to find the value of $r$ that has the greatest $r$-representative. Claim: Out of all $0\le r \le 2^{n-1}-1$, $r=1$ has the greatest $r$-representative. Proof. Notice that $\pmod {2^{n-1}}$, the terms (other than $2^{n-1}$) have residues $-2^k$ for $0\le k\le n-2$. We now prove a subclaim. Subclaim: The $1$-representative can be found by adding every term in $A_n$ other than $2^{n-1}$. Proof. Notice that this combination of terms makes the number $1\pmod {2^{n-1}}$. We now prove that there is no combination of terms that can achieve a lower number having the same residue. Consider the following two operations: 1. If there is at least two of the term that is $-2^k \pmod {2^{n-1}}, k<n-2$, then delete two of these and replace it with one term that is $-2^{k+1} \pmod {2^{n-1}}$. 2. If there is at least two of the term that is $-2^k \pmod {2^{n-1}}, k=n-2$, then delete two of these. Notice that both operations keep the residue constant and lower the number. Therefore the optimal construction cannot be operated on, therefore it cannot use more than one of the same term. However, the only construction that does this is seen to be the construction in the subclaim. $\blacksquare$ Notice that any other residue $r\ne 1$ can be achieved by expressing $r-2^{n-1}$ in binary and then using the appropriate terms corresponding to the binary representation. Because $r\ne 1$, this uses a subset of the terms of $A_n$ not containing $2^{n-1}$, with each term being used at most once. This is clearly lower than the $1$-representative number (which uses every element of $A_n$ but 2^{n-1} once), proving the claim. $\blacksquare$ Therefore we can get the largest number that cannot be reached by subtracting $2^{n-1}$ from the $1$-representative. Notice that the sum of the terms other than $2^{n-1}$ is equal to $$(n-1)2^n-(2^0+2^1+\ldots+2^{n-2})=(n-1)2^n-(2^{n-1}-1)=1+(n-2)2^n+2^{n-1}.$$Subtracting $2^{n-1}$ yields the answer stated at the beginning of the proof.

Let $f(n)$ be the answer. Claim: $f(n)=2^n-1+2f(n-1)$. proof: Note that since $A_n=2A_{n-1}\cup\{2^n-1\}$ and every integer $>f(n-1)$, is a sum of elements from $A_{n-1}$, every interger $>2^n-1+2f(n-1)$ is a sum of elements from $A_n$. Now, we show that $2^n-1+2f(n-1)$ is not a sum of elements from $A_n$. Assume contrary. Then, since $2^n-1+2f(n-1)$ is odd, $2^n-1$, being the only odd number in $A_n$, must appear in the sum. So, $2f(n-1)$ is a sum of elements from $A_n$: $2f(n-1)=a_1(2^n-1)+a_2 (2^n-2)+a_3 (2^n-4)+\dots+a_n (2^n-2^{n-1})$, where $a_i\geq 0$ are intergers. $a_1$ is clearly even. So, let it be $a_1=2k$. Then, $$f(n-1)=k(2^n-1)+a_2 (2^{n-1}-1)+a_3 (2^{n-1}-2)+\dots+a_n (2^{n-1}-2^{n-2})=$$$$=k(2^{n-1}-1+2(2^{n-1}-2^{n-2}))+a_2 (2^{n-1}-1)+a_3 (2^{n-1}-2)+\dots+a_n (2^{n-1}-2^{n-2})$$is a sum of elements from $A_{n-1}$. This is a contradiction. $\blacksquare$ Now, having $f(2)=1$ and $f(n)=2^n-1+2f(n-1)$, we define $g(n)=\frac{f(n)}{2^n}$ and the recurrence becomes $g(n)=1-\frac{1}{2^n}+g(n-1)$. Induction gives $$g(n)=(1-\frac{1}{2^n})+(1-\frac{1}{2^{n-1}})+\dots+(1-\frac{1}{8})+g(2)=(n-2)-(\frac{1}{2^n}+\frac{1}{2^{n-1}}+\dots+\frac{1}{8}) +\frac{1}{4}=$$$$=(n-2)-\frac{1+2+4+\dots+2^{n-3}}{2^n}+\frac{1}{4}=(n-2)-\frac{2^{n-2}-1}{2^n}+\frac{1}{4}$$ Solving $\frac{f(n)}{2^n}=(n-2)-\frac{2^{n-2}-1}{2^n}+\frac{1}{4}$ gives $f(n)=(n-2)2^n+1$.

hajimbrak wrote: Let $n \ge 2$ be an integer, and let $A_n$ be the set \[A_n = \{2^n - 2^k\mid k \in \mathbb{Z},\, 0 \le k < n\}.\]Determine the largest positive integer that cannot be written as the sum of one or more (not necessarily distinct) elements of $A_n$ . Proposed by Serbia Nice problem. Call a number good if it can be written in mentioned way. Claim 1-: Any natural number $n$ can be written as sum of some power of $2$ with atmost one power$=0$. Prove-: Just use induction with Base case $n=1$. Now as $\sum_{i=0}^{n-1} A_i=(n-1)2^n+1=h(n)$ Is good. And also as $2^na=a(2^{n-1}+2^{n-1})=2aA_{n-1}$ So $2^na$ is good for any $a\in N$ Claim 2-: All natural number $N$ such that $h(n)-2^n+k=N$ are good for all $k>0$ Prove-: We will prove it in $3$ cases Case 1-: when $N=h(n)-2^n+2k$ for any $1\leq k\leq 2^{n-1}$ then observe By Claim $1$ let $2k=2^{k_1}+..+2^{k_x}$ for $k_i<n$ for all $1\leq i\leq x$ So $N=\sum_{i=0}^{n-1} (2^n-2^i)-(2^n-2^{k_1})+(2^{k_2}+..+2^{k_x})$ Now as $2^{n}a$ is always good So it suffices to prove that $N=h(n)-2^n+2k$ is good for $1\leq k\leq 2^{n-1}$ and if $k>2^{n-1}$ we will have $2k=2^n+2m$ then $2k=2^n +2^{k_1}+..2^{k_x}$ So $N=\sum_{i=0}^{n-1} (2^n-2^i)+ 2^{k_1}+..2^{k_x}$ and again as $2^na$ is always good so $N=h(n)-2^n+2k$ is always good. and our case $1$ is proved. Case 2-: When $N=h(n)-(2^n-1)+2k=2^n+\sum_{i=1}^{n-1} A_i +2k$ which Now equivalent to proving case $1$ which we already did. Case 3-: $k=0$ is not . Prove-: if $k=0$ then $N=h(n)-2^n\implies N=\sum_{i=1}^{n-1} (2^n-2^i)-1$ So it is Not possible to represent. Hence our Claim $2$ is proved. And we get that largest Number which is not good is of the form $(n-2)2^n+1$ $\blacksquare$ It Becomes easy if we know the answer. So here's How I guessed the answer-: I first observe that $h(n)$ is always good. And then tried to check if I can get any Number Greater then $h(n)$ which is not good. Then immediately By Claim 1 I realised that this Not possible so I got that Answer would be less then $h(n)$ and then started checking for numbers less then $h(n)$ and then immediately I had intuition of the answer.

We claim that the answer is $X=2^n(n-2)+1$ Call a number representable if it satisfies the problem statement. $\color{black} \rule{25cm}{2.5pt}$ Claim: Every natural number $a \ge (n-2)2^n+2$ is representable. Proof: We will prove this by induction. The base case $n=1$ is clear.Suppose that $n$ works and we will show that $n+1$ also satisfies. By the inductive hypothesis every number $X \ge (n-2)2^n+1$ is representable and $a=k_1(2^n-1)+k_2(2^n-2)+k_3(2^n-2^2)+\cdots +k_{n-1}(2^n-2^{n-1})\longrightarrow 2a=k_1(2^{n+1}-2)+k_2(2^{n+1}-2^2)+\cdots +k_{n-1}(2^{n+1}-2^n)$ is also representable hence we just have to prove the result for odd numbers. Now choose any odd integer $X>(n-1)2^{n+1}+1$,then $X-(2^{\log_2(x)-1}-1)$ is even and is representable with elements of $A_k$ for some $k<n+1$ so we are done. $\color{black} \rule{25cm}{2.5pt}$ Claim:(induction for the answer) $(n-2)2^n+1$ isn’t representable. Proof: We’ll again do this by induction where the base case $n=1$ works trivally by Chicken Mcnugget Theorem. By the inductive hypothesis,$k=n$ satisfies and we will prove the result for $k=n+1$ For the sake of contradiction,assume that $(n-1)2^{n+1}+1$ is representable. Notice that this implies $$(n-1)2^{n+1}+1=k_1(2^{n+1}-1)+k_2(2^{n+1}-2)+\cdots +k_n(2^{n+1}-2^n)=k_1(2^{n+1}-1)+2 \sum_{x=1}^n \sum_{j=1}^n |2^x-2^j|$$,is representable. However this is impossible by the inductive hypothesis,since this implies $2^{n}(n-2)+1$ is representable, contradiction. $\color{black} \rule{25cm}{2.5pt}$

this is a very nice problem.This can be proved by the $(n-2)2^n+1$ stain from induction.

We claim the answer is $(n-2)2^n + 1$. First, it is easy to see that if you can make a number $x$, you can make any number $>x$ with the same remainder modulo $2^n$. This is because you can add two elements of $2(2^n - 2^{n-1}) = 2(2^{n-1}) = 2^n$. Notice that the elements of $A_n$ can be rewritten modulo $2^n$ as $-1, -2, -4 , \cdots, -2^{n-1}.$ But notice that making a number that is $-k \pmod{2^n}$ is equivalent to expressing $k$ in base $2$, as you have to form it by adding $-1, -2, -4, \cdots$. This shows that we will never need more than one of each element. This method is optimal because the lowest terms are ones with a lower modulo $2^n$, so getting the larger powers of 2 out of the way will get to $-k$ faster and keep the least number that can be expressed as the sum of elements in $A$ smaller. Furthermore, the worst case scenario is making $-2^n+1 \pmod{2^n}$, since you need to use all the elements. This means the least number that can be created using the elements in $A$ and is also $1 \pmod{2^n}$ is $(2^n-1)+(2^n-2) + \cdots +(2^n-2^{n-1}) = n \cdot 2^n - (2^n -1) = (n-1)2^n +1$. But this CAN be achieved and we want the greatest that can't be achieved, so we must subtract $2^n$ to get $\boxed{(n-2)2^n + 1}.$

The answer is $-2^n + \sum\limits_{i=0}^{k-1} (2^n-2^i) = (n-1)2^n - (2^n - 1)$. Let $a_i = 2^n - 2^i$ for integers $0 \leq i \leq n-1$. First, we show that all numbers larger than this can be written. Claim: For any $b$ between $0$ and $2^n-2$, the integer $a \cdot 2^n - b$ can be written for some $a \leq n-1$. Proof. Express $b$ in binary, and take the sum \[ \sum\limits_{i = 0}^{n-1} \begin{cases*} a_i & $i$th digit of $b = 1$ \\ 0 & $i$th digit of $b = 0$ \\ \end{cases*} \]As an example, for $n = 4$ and $b = 5$, this would give $2^4 - 1 + 2^4 - 4 = 2 \cdot 2^4 - 5$. At most $n-1$ terms are added up (and therefore $a \leq n-1$) because $b$ is an $n$ digit binary string that must have at least $1$ zero (as $b < 2^n-1$). Furthermore, it is not hard to show that this gives the sum has the desired value $\pmod{2^n}$. $\blacksquare$ Finally, the number $n\cdot 2^n - (2^n-1)$ is representable as it is equal to $\sum\limits_{i=0}^{k-1} a_i$. This finishes because we can continuously add $2^{k-1} + 2^{k-1}$ (and all values $\pmod{2^k}$ are covered). Now, we show that we cannot express $(n-1)2^n - (2^n-1)$ as the sum of terms in $A_n$. Assume for the sake of contradiction that \[ (n-1)2^n - (2^n-1) = \sum\limits_{i=0}^{n-1} a_i b_i \]for nonnegative integers $b_0,b_1,\ldots,b_{n-1}$. Taking $\pmod{2^n}$, this is equivalent to \[ \sum\limits_{i=0}^{n-1} 2^i b_i \equiv 2^n - 1\pmod{2^n} \]and it is possible to show that $\sum\limits_{i = 0}^{n-1} a_ib_i \geq n \cdot 2^n - (2^n-1)$ (note first that by size if all $ b_i \in \{0,1\}$ then all $b_i = 1$; furthermore, if $b_i \geq 2$ we can move $b_{i+1} \rightarrow b_{i+1} + 1$ and $b_i \rightarrow b_i - 2$ which is more efficient; therefore the minimum must occur when all $b_i = 1$).

Induct. $(n-2)2^n + 1$.

I claim that the answer is $\boxed{(n-2)2^n+1}$. Let $f(n,k)=2^n-2^k$ for simplicity. Let our wanted answer be $X_n$. We'll ignore $n=2$ for now and do it separately later. If $X_n$ is even, then $X_n+f(n,0)$ would also satisfy the condition(as the only way to form it requires an odd number, which can only be $f(n,0)$), so $X_n$ has to be odd. Now, note that $$2f(n,0)=2^{n+1}-2^1=2\cdot 2^{n-1}+2^n-2^1=2f(n,n-1)+f(n,1),$$so if $C$ can be formed, then $C$ can be formed with at most one $f(n,0)$, in which the $f(n,0)$ is used if and only if $C$ is odd. So, $X_n-f(n,0)$ is double a number that cannot be formed with $A_{n-1}$, and a number that cannot be formed with $A_{n-1}$ always doubles to a number that cannot be formed with $A_n$, so $X_n-f(n,0)$ actually works. This means that $X_n=f(n,0)+2X_{n-1}$. Now, $X_2=1$ because $A_2=\{2,3\}$. It is now easy to see that the claimed answer is correct. QED.

We claim the answer $(n-2)2^n+1$. Define $a_k=2^n-2^k;$ notice that $a_k=a_{k+1}+2a_{n-1},$ so we may assume that each $a_k$ for $k<n-1$ is used at most once in every sum. Now we claim, that all numbers which cant' be represented as a sum, are of form $-ma_{n-1}+\sum_{i=0}^{n-2} k_i a_i,$ for $m>0$ and $k_i\in \left \{ 0,1 \right \},$ which gives the result. This however easily follows from the following Lemma. All $2^{n-1}$ sums of type $\sum_{i=0}^{n-2} \alpha_i a_i$ for $\alpha_i \in \left \{ 0,1 \right \}$ are pairwise noncongruent modulo $2^{n-1}.$ Proof. Assume that $\sum_{i=0}^{n-2} \alpha_i a_i\equiv \sum_{i=0}^{n-2} \beta_i a_i \pmod{2^{n-1}}.$ for $\alpha_i,\beta_i \in \left \{ 0,1 \right \}.$ Then we get $$2^{n-1}\mid l2^n- \sum_{i=0}^{n-2} \gamma_i a_i\implies 2^{n-1}\mid \sum_{i=0}^{n-2} \gamma_i a_i$$for $\gamma_i \in \left \{ -1,0,1\right \}.$ Since $\sum_{i=0}^{n-2}<2^{n-1}$ it hence follows that $\gamma_i =0$ $\Box$

We claim that the answer is $a_n$, where the sequence $a$ satisfies $$a_2=1$$$$a_{n+1}=2a_n+2^{n+1}-1.$$For example, the first few terms are $1,9,33,97,257,641.$ We will first show that $a_n$ is not achievable. For $n=2$ obviously we can not reach 1. We will use induction. Suppose that it is impossible to reach $a_n$ for $n$. Now, consider how we can reach $a_{n+1}=2a_n+2^{n+1}-1$ for $n+1$. Note that this is odd, so we must use the $2^{n+1}-1$ term at least once. Then, we need to get $2a_n$ using the remaining terms. However, the terms other than $2^{n+1}-1$ are just double what they are when we had $n$, so if $a_n$ is not reachable before, then $2a_n$ is not reachable now, so we have shown this by induction. We will then show that values larger than $a_n$ are reachable. We will again use induction. This is obviously true for $n=2$ Suppose that for $n$, all values larger than $a_n$ is reachable. We will now try a number larger than $a_{n+1}$ for $n+1$. If it is even, we can just not use the $2^{n+1}-1$ term, and since $\frac{a_{n+1}}{2}>a_n$, our inductive hypothesis tells us that we can just use a construction for $n$ but with everything doubled. If it is odd, we will use the $2^{n+1}-1$ term, and we will be left with an even number larger than $2a_n$. Then, since again everything is just doubled, the inductive hypothesis tells us that any even larger than $2a_n$ is reachable as well, so we are done. edit: just realized that my sequence is actually just $a_n=2^n(n-2)+1$, which you can easily induct to show once you get the recursive formula once you see the pattern, but i didn't see the pattern when first solving oops

Let a $n$-representation of $x$ be a sequence of $n$ positive integers $(a_0,a_1,\dots, a_{n-1})$ such that \[x=\sum_{i=0}^{n-1}{a_i(2^n-2^k)}\]Let the minimal $n$-representation of $x$ be the sequence that minimizes each term, prioritizing the terms with the smaller index. In any minimal $n$-representation, let $i$ be the smallest index such that $a_i\ge 2$, then note that unless $i=n-1$, we can subtract two from $a_i$, add one to $a_{i+1}$, and add two to $a_{n-1}$ and get a more minimal $n$-representation of $x$ since \[2(2^{n}-2^{i})=2^n-2^{a+1}+2(2^n-2^{n-1})\]Therefore in the minimal $n$-representation, $a_i\le 1$ for all $0\le i\le n-2$. In this case, while we vary the binary sequence $(a_0,a_1,\dots, a_{n-2})$, $x$ goes over every possible remainder $\pmod {2^{n-1}}$ so this minimal sequence is indeed unique, and we can determine a unique $a_{n-1}$ from the previous terms. $x$ cannot be represented if and only if $a_{n-1}$ is forced to be negative. The maximum we can get is by adding all of the $2^n-2^k$ for $k=0,1,\dots, n-1$ and then subtracting $2^{n-1}$, which gives $(n-2)2^n+1$.

The answer is $(n-2)2^n+1$. We first prove that this can't be achieved. To do that, we prove the stronger claim that $k2^n+1$ isn't constructible for $0 \le k \le n-2$. We do this with induction. The base case is obvious. Now we prove $k-1 \implies k$. Assume there is a construction for $k$. Now say we use $a_i$ of the term $2^n-2^i$. If $a_j \ge 2$ for some $j$ and $j < n-1$ we have that $(a_0,a_1, \dots , a_{j-1},a_j-2,a_{j+1}-1,a_{j+2}, \dots , a_{n-1})$ produces a construction for $(k-1)2^n+1$ contradiction to the induction. If $j=n-1$, we have that $(a_0,a_1, \dots, a_{n-2}, a_{n-1}-2)$ produces a construction for $(k-1)2^n+1$. Thus $a_i \le 1$ for all $i$. Thus $2^n \mid k2^n+1 - \sum 2^n a_i + \sum 2^i a_i \implies 2^n \mid 1+\sum 2^i a_i$. Note that $1+\sum 2^i a_i \le 2^n$ with equality only if $a_i=1$ for all $i$, which must occur. Thus our construction gives $(n-1)2^n+1$ and we're done. We now construct all numbers bigger than $(n-2)2^n+1$. Note that if we can construct $r$, we can construct $r+2^{n-1}$, so we prove we can construct $(n-2)2^n+p$ for $2 \le p \le 2^{n-1}+1$. Let $q=2^n-p$ and let $q = \sum 2^{q_i}$ for integers $q_i$. Note that there is at most $n-1$ of these integers because $2^{n-1}-1 \le q \le 2^n-2$ and $1+2+ \cdots + 2^{n-1}=2^n -1 > 2^n-2$. Now we construct $(n-2)2^n+p = (n-1)2^n-q$ with $\sum \left(2^n - 2^{q_i}\right) + 2 \cdot \left(2^n-2^{n-1}\right) \cdot (n-1-\text{number of } q_i)$ and since the number of $q_i$ is less than or equal to $n-1$ all terms are nonnegative and this construction works.

Can admin delete this comment I accidentally posted twice.

I claim that $\boxed{(n - 2) \cdot 2^n + 1}$ is the largest such value. We say that $N$ is expressible if $N$ is the sum of the elements of $A_n,$ and $N$ is inexpressible otherwise. Claim: $N = (n - 2) \cdot 2^n + 1$ is inexpressible. Proof: By way of contradiction, assume $N = a_0(2^n - 2^0) + a_1(2^n - 2^1) + \cdots + a_{n - 1}(2^n - 2^{n - 1})$. Then \begin{align*} \sum_{k = 0}^{n - 1} (2^n - 2^k) - 2^n &= \sum_{k = 0}^{n - 1} a_k(2^n - 2^k), \text{ with } a_i \in \{0, 1\}, \text{ }a_i \text{ not all} = 0. \\ \implies (n - 1) \cdot 2^n + 1 + \sum_{k = 0}^{n - 1} a_k2^k &= 2^n(1 + a_0 + a_1 + \cdots a_{n - 1}) \\ \implies \sum_{k = 0}^{n - 1} a_k &\equiv 0 \pmod{2^n} \implies \text{all } a_i = 1, \end{align*}a contradiction. $\square$ Now as $N = (n - 2) \cdot 2^n + 1$ is inexpressible, we will show that all $M \geq (n - 2) \cdot 2^n + 2$ are expressible. Claim: All $M \geq (n - 2) \cdot 2^n + 2$ are expressible. Proof: Consider when $M$ is in the interval $M \in [(n - 2) \cdot 2^n + 2, (n - 1) \cdot 2^n + 1]$. We then have that if $M = (n - 2) \cdot 2^n + 1 + \ell$, where $1 \leq \ell \leq 2^n$, that $\ell$ can be represented in binary form, and is therefore expressible. Hence $M$ is expressible. Now for all $M > (n - 1) \cdot 2^n + 1$, just append $2^n$ to every value within $[(n - 2) \cdot 2^n + 2, (n - 1) \cdot 2^n + 1]$ to generate expressible numbers for all $M > (n - 2) \cdot 2^n + 1$. $\square$ Hence all numbers greater than our initial largest inexpressible number is expressible, as was to be shown. $\blacksquare$

I claim the answer is $(n - 2)2^n + 1$. We prove the construction inductively. Construction: Clearly for $n = 2$ we have $A_2 = \{ 2,3 \}$ and the claim holds by Chicken McNugget. Now for the inductive step, if we can form $(n - 2) 2^n + 2$ and all numbers above using $A_n$, we see that all doubles of elements in $A_n$ are in $A_{n + 1}$, so we can form all evens at least $(n - 2) 2^{n + 1} + 4$. We can then form all odds at least $(n - 2) 2^{n + 1} + 4 + (2^{n + 1} - 1) = (n + 1 - 2)2^{n + 1} + 3$. Thus we can form all numbers above $(n - 2)2^{n} + 1$. Bound: Assume for the sake of contradiction that we can form $(n - 2)2^n + 1$, then we have $\sum_{1 \le i \ le k} 2^n - 2^{x_i} = (n -2)2^n + 1$ for some sequence of length $k$ denoted $x$. Claim: Some subsequence $y$ of $x$ satisfies $\sum 2^{y_i} = 2^{n} - 1$. Repeatedly replace two equal elements in the sequence $2^{x_i}$ with their sum. Note that it is always true that every element in the sequence is the sum of distinct elements of the original sequence (no original element is part of two sums, since it would imply the element was combined twice which is impossible). Clearly we can only do this operation finitely many times due to size, so eventually we just get the binary representation of $\sum 2^{x_i}$, which has elements summing to $2^{n} - 1$ since $\sum 2^{x_i} \equiv 2^{n} - 1 \mod 2^n$, and these elements are all sums of distinct elements of the original sequence, so it suffices to take the sequence of these original elements. Claim: No sequence of powers of two summing to $2^n - 1$ has size less than $n$. Assume for the sake of contradiction some sequence exists. Note that we can replace two equal element in the sequence with their sum to get a smaller sequence that also sums to $2^n - 1$. Clearly we can only repeat this move finitely many times by size, so at some point we must get a sequence of distinct powers of $2$ that sums to $2^n - 1$, however this is just the binary representation of $2^n -1$, which has $n$ powers of $2$, contradiction. Now we finish by noting $\sum 2^n - 2^{x_i} \ge \sum 2^{n} - 2^{y_i} \ge n2^n - (2^n - 1) \ge (n - 2)2^n + 1$, contradiction.

The answer is $(n-2)2^n+1$. Suppose that $(n-2)2^n+1=\sum_{i=0}^{n-1}c_i(2^n-2^i)$ for nonnegative integers $c_0,c_1,\dots,c_{n-1}$. Taking modulo $2^k$ when starting from $k=1$ and incrementing $k$ by $1$ at each step, we find that $c_i$ is odd for all $i$, implying that $(n-2)2^n+1\ge\sum_{i=0}^{n-1}(2^n-2^i)=(n-1)2^n+1$, a contradiction. Now we show that all integers larger than $(n-2)2^n+1$ are expressible as sums of elements of $A_n$. This is clearly true for $n=2$. By induction, if our claim holds for $n-1$, consider some $M>(n-2)2^n+1$. If $M$ is even, we have $\frac{M}2>(n-2)2^{n-1}+1$, so we can write $\frac{M}2$ as the sum of elements of $A_{n-1}$ and double each term, as $\{2m\mid m\in A_{n-1}\}\subseteq A_n$. If $M$ is odd, the same reasoning applies to $\frac{M-(2^n-1)}2$. $\blacksquare$