Expressing a term of the sequence by the sum of previous terms

Art of Problem Solving

AoPS Online

High School Olympiads Regional, national, and international math olympiads

Regional, national, and international math olympiads

3 M G

BBookmark VNew Topic kLocked

High School Olympiads Regional, national, and international math olympiads

Regional, national, and international math olympiads

3 M G

BBookmark VNew Topic kLocked

No tags match your search

M

Expressing a term of the sequence by the sum of previous terms

G H J

Reveal topic tags

L

G H BBookmark kLocked kLocked NReply

Source: ISL 2018 N3

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

18 posts

#1 h Jul 17, 2019, 12:15 PM • 3 Y

Y by centslordm, Adventure10, deplasmanyollari

Define the sequence $a_0,a_1,a_2,\hdots$ by $a_n=2^n+2^{\lfloor n/2\rfloor}$ . Prove that there are infinitely many terms of the sequence which can be expressed as a sum of (two or more) distinct terms of the sequence, as well as infinitely many of those which cannot be expressed in such a way.

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

6877 posts

#2 h Jul 17, 2019, 12:55 PM • 10 Y

Y by pavel kozlov, rashah76, ayan_mathematics_king, Siddharth03, v4913, centslordm, akasht, Adventure10, Ali_Vafa, NicoN9

Let $\begin{align*} S_n &= a_0 + \dots + a_n \\ &= 2^{n+1} + 2^{\left\lfloor (n+1)/2 \right\rfloor} + 2^{\left\lceil (n+1)/2 \right\rceil} - 3 \\ &= a_{n+1} + (2^{\left\lceil (n+1)/2 \right\rceil} - 3). \end{align*}$ Here is a table of the first several $a_n$ and $S_n$ for concreteness. $\begin{array}{rrlrl} n & a_n & & S_n & \\ \hline 0 & 2 & = 2^{0} + 2^{0} & 2 & = 2^1+2^0+2^1-3 \\ 1 & 3 & = 2^{1} + 2^{0} & 5 & = 2^2+2^1+2^1-3 \\ 2 & 6 & = 2^{2} + 2^{1} & 11 & = 2^3+2^1+2^2-3 \\ 3 & 10 & = 2^{3} + 2^{1} & 21 &= 2^4+2^2+2^2-3 \\ 4 & 20 & = 2^{4} + 2^{2} & 41 &= 2^5+2^2+2^3-3 \\ 5 & 36 & = 2^{5} + 2^{2} & 77 &= 2^{6}+2^3+2^3-3 \\ 6 & 72 & = 2^{6} + 2^{3} & 149 &= 2^{7}+2^3+2^4-3 \\ 7 & 136 & = 2^{7} + 2^{3} & 285 &= 2^{8}+2^4+2^4-3 \\ 8 & 272 & = 2^{8} + 2^{4} & 557 &= 2^{9}+2^4+2^5-3 \\ 9 & 528 & = 2^{9} + 2^{4} & 1085 &= 2^{10}+2^5+2^5-3 \\ 10 & 1056 & = 2^{10} + 2^{5} & 2141 &= 2^{11}+2^5+2^6-3 \\ 11 & 2080 & = 2^{11} + 2^{5} & 4221 &= 2^{12}+2^6+2^6-3 \\ 12 & 4160 & = 2^{12} + 2^{6} & 8381 &= 2^{13}+2^6+2^7-3 \\ 13 & 8256 & = 2^{13} + 2^{6} & 16637 &= 2^{14}+2^7+2^7-3 \\ 14 & 16512 & = 2^{14} + 2^{7} & 33149 &= 2^{15}+2^7+2^8-3 \\ 15 & 32896 & = 2^{15} + 2^{7} & 66045 &= 2^{16}+2^8+2^8-3 \\ 16 & 65792 & = 2^{16} + 2^{8} & 131837 &= 2^{17}+2^8+2^9-3 \\ 17 & 131328 & = 2^{17} + 2^{8} & 263165 &= 2^{18}+2^9+2^9-3 \\ \end{array}$ The idea is that each $a_n$ is close to the previous partial sum $S_{n-1}$ . We say $x \in {\mathbb Z}_{\ge 0}$ is representable if it can be written as the sum of zero or more terms in the sequence. We write $x \iff y$ to denote that either both $x$ and $y$ are representable, or neither is. The main claim is:

Claim: Let $n$ be a be a nonnegative integer.

If $x$ and $y$ are nonnegative integers with $x+y = S_n$ and $x,y < a_{n+1}$ , then $x \iff y$ .
The number $a_n$ can be represented as the sum of previous terms if and only if $S_{n-1} - a_n = 2^{\left\lceil n/2 \right\rceil} - 3$ can be.

Proof. If $x$ is representable, then it is the sum of some subset $S \subseteq \{a_0, \dots, a_n\}$ ; the complement of $S$ then has sum $y$ . The second bullet point is similar. $\blacksquare$

Now it is straightforward to finish by focusing only on terms of the form $2^k-3$ and seeing how the first part of the claim applies to them. One simple way to do this is notice that for $k \ge 2$ we have a chain $(2^{4k-2}-3) \iff \underbrace{2^{2k}}_{=2^{2k-1}+2^{2k-1}} \iff \underbrace{(2^{k+1}-3)}_{=2^k+2^k-3}.$ Thus since $2^3 - 3 = 5 = a_0 + a_1$ is representable, we get an infinite chain $(2^3-3) \iff 2^4 \iff (2^6-3) \iff 2^{10} \iff (2^{18}-3) \iff 2^{34} \iff \cdots.$ Similarly, one can check $2^7-3 = 125$ is not representable (according to $125 \iff 24 \iff 17 \iff 4$ , say); thus we get another infinite chain $(2^7-3) \iff 2^{12} \iff (2^{22}-3) \iff 2^{42} \iff (2^{82}-3) \iff 2^{162} \iff \cdots.$

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

1595 posts

#3 h Jul 17, 2019, 3:53 PM • 4 Y

Y by akasht, Adventure10, Mango247, bhan2025

Bashy and fake NT

Call a positive integer $k$ weakly expressible if and only if it can be written in the sum of (at least one) different terms in $a_0,a_1,...$ . And call it strongly expressible if and only if it can be written in the sum of (at least two) different terms.

First, we introduce the following small claim.

Claim: For any positive integer $n$ ,

$a_0+a_1+a_2+...+a_{2n-1} = 2^{2n}+2^{n+1}-3$ ,
$a_0+a_1+a_2+...+a_{2n} = 2^{2n+1}+3\cdot 2^n -3.$

Proof: Straightforward computation.

Now, here is the crucial observation. For any positive integers $k,n$ such that $k\leqslant a_n$ , we have
$\boxed{k\text{ is strongly expressible}\iff (a_0+a_1+..+a_{n-1})-k\text{ is weakly expressible}.}$ Using specific cases of this observation and a few computations. We deduce the following claims for any $n\geqslant 3$ .

Claim: $a_{2n-1}$ is strongly expressible $\iff 2^n-3$ is strongly expressible.

Proof: Note that $2^n-3\in (a_{n-1},a_n)$ . Thus the notions of weakly and strongly expressible for $2^n-3$ are equivalent. Moreover,
$(a_0+a_1+...+a_{2n-2}) - (a_{2n-1}) = (2^{2n-1}+3\cdot 2^{n-1}-3) - (2^{2n-1}+2^{n-1}) = 2^n-3$ thus by our observation we are done.

Claim: $2^{4n-6}-3$ is strongly expressible $\iff 2^{2n-1}$ is strongly expressible $\iff 2^n-3$ is strongly expressible.

Proof: Clearly each of $2^n-3, 2^{2n-1}, 2^{4n-6}-3$ are not in range of $a_i$ . Thus we can abandon the notion weakly/strongly expressible. Now observe that
$\begin{align*} (a_0+a_1+a_2+...+a_{4n-7}) - (2^{4n-6}-3) &= (2^{4n-6} + 2^{2n-2}-3) - (2^{4n-6}-3) = 2^{2n-2} \\ (a_0+a_1+a_2+...+a_{2n-3}) - 2^{2n-2} &= (2^{2n-2} + 2^n - 3) - 2^{2n-2} = 2^n-3. \end{align*}$ thus using the observation twice, we are done.

The two claims implies that $a_{2n-1}$ is strongly expressible $\iff a_{8n-13}$ is inexpressible. Thus it suffices to find an example which can/cannot be expressed. Aiding with the $2^n-3$ claim, a straightforward calculation reveals $a_7$ is expressible while $a_{13}$ cannot hence we are done.

This post has been edited 1 time. Last edited by MarkBcc168, Jul 17, 2019, 3:53 PM

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

1671 posts

pad

#6 h May 28, 2020, 9:37 PM • 3 Y

Y by Mango247, Mango247, Mango247

Notice that $a_0+\cdots+a_{n-1}$ is very close to $a_n$ due to the fact that $a_n$ is close to $2^n$ . In particular,
$\begin{align*} a_0 + \cdots + a_{2k-1} &= (2^{2k}-1) + 2(2^k-1) = 2^{2k} + 2^{k+1} - 3 \\ a_0+\cdots +a_{2k}&= (2^{2k+1}-1)+2(2^{k}-1)+2^k=2^{2k+1} + 2^{k+1}+2^k - 3. \end{align*}$ So $(a_0+\cdots+a_{2k-1})-a_{2k} = 2^k - 3$ and $(a_0+\cdots+a_{2k})-a_{2k+1} = 2^{k+1}-3$ . In summary,
$a_n = (a_0+\cdots + a_{n-1}) - (2^{\lceil n/2 \rceil}-3).$ Therefore, $a_n$ is expressible iff $2^{\lceil n/2 \rceil}-3$ is expressible, since $2^{\lceil n/2 \rceil}-3$ will just be the terms remaining from $a_0+\cdots+a_{n-1}$ when we remove the terms that sum to $a_n$ .

Therefore, it suffices to find infinitely many $2^k-3$ that are expressible and infinitely that are not. Note that $2^3-3=5=a_0+a_1$ is expressible, and $2^7-3 = 125$ is not expressible. Hence, if we can find an infinite chain $k<k_1<k_2<\cdots$ for each initial $k$ such that $2^{k_i}-3$ is expressible iff $2^{k_{i+1}}-3$ is expressible, then we will be done, as the chain starting with $2^3-3$ will all be expressible, and the chain starting with $2^7-3$ will all not be expressible. We have
$2^k-3 = (a_0+\cdots+a_{2k-3}) - 2^{2k-2}.$ So $2^k-3$ is expressible iff $2^{2k-2}$ is expressible. And
$2^{2k-2} = (a_0+\cdots+a_{4k-7}) - (2^{4k-6}-3),$ so $2^{2k-2}$ is expressible iff $2^{4k-6}-3$ is expressible. In conclusion, $2^k-3$ is expressible iff $2^{4k-6}$ is expressible, so we are done.

Remarks

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

354 posts

#7 h Jun 17, 2020, 5:53 AM • 1 Y

Y by OronSH

Solution with jclash

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

380 posts

#8 h Aug 13, 2020, 12:22 PM

Y by

Same idea as the ones posted earlier.

Say that an integer $k$ is expressible if it may me written as a sum of one or more distinct terms in the sequence $\{a_n\}$ , and let $S_n = a_0 + a_1 + a_2 + \cdots + a_n$ .

With a straightforward computation,
$\begin{align*} S_{2k-1} &= 2^{2k} + 2^k + 2^k - 3 \\ S_{2k} &= 2^{2k+1} + 2^{k+1} + 2^k - 3 \end{align*}$
First, observe that
$m \text{ is expressible } \iff S_{n} - m \text{ is expressible } \tag{$\dagger$}$ because if $m$ is expressible as a sum of a subsequence $A$ , then $S_{n} - m$ is equal to the sum of $\{a_0, a_1, a_2, \dots, a_{n}\} \setminus A$ . In particular, $a_{2k}$ is expressible if and only if $2^k - 3$ is expressible. However, by applying $(\dagger)$ with $(m,n) = (2^{4k-2}-3, 4k-3)$ and $2^{2k}, S_{2k-1}$ , we obtain that
$2^{4k-2} - 3 \text{ is expressible } \iff 2^{2k} \text{ is expressible } \iff 2^{k+1} - 3 \text{ is expressible }$ This implies that $a_{8k-4}$ is expressible if and only if $a_{2k+2}$ is expressible. However, it is easy to check manually that $a_8$ is not expressible and that $a_6$ is expressible. Thus we can produce infinitely expressible and non-expressible elements of the sequence $a_n$ by induction.

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

492 posts

#9 h Sep 8, 2020, 2:39 AM

Y by

redacted

This post has been edited 4 times. Last edited by fukano_2, Oct 27, 2021, 10:35 AM

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

1184 posts

L567

#10 h Jun 28, 2021, 8:09 AM • 1 Y

Y by starchan

Cute. Solved with Pujnk

Observe that $a_{2k} = 2^{2k} + 2^{k} = 2(2^{2k-1} + 2^{k-1}) = 2a_{2k-1}$

Let $S(n)$ denote $a_0 + a_1 + a_2 + ... + a_n$ .

Claim: $S(2k-1) = a_{2k} + 2^k - 3 = 2^{2k} + 2^{k+1} - 3$

Proof: Just induct, the base case is true. Then, we have $S(2k-1) = a_{2k-1} + a_{2k-2} + S(2k-3) = 2^{2k-1} + 2^{k-1} + 2^{2k-2} + 2^{k-1} + 2^{2k-2} + 2^{k} - 3 = 2^{2k}+ 2^{k+1} - 3$ , as desired. $\square$

Call a number representable if it can be written as the sum of two or more distinct elements of the sequence. Observe that if a number $n$ is representable, with all the terms of the sequence $\le a_m$ , then we have that $S_m - n$ is also representable by just picking all those terms that were not picked earlier. The converse also obviously holds.

So, we have that $a_{2n}$ is representable if and only if $2^n - 3$ is representable. Also, note that $2^{2n}$ is representable if and only if $2^{n+1} - 3$ is representable.

Adopting the notation from previous posts, this means we have $2^{4n-2} - 3 \iff 2^{2n} \iff 2^{n+1}-3$ . So, it suffices to find one value of $2^n - 3$ that is and is not representable since then we can generate infinitely many of them using this (We need $n > 1$ though)

For a representable one, we have $n=3$ works since $5 = 2 + 3$ and for one that is not, bashing, we see that $a_7 = 125$ cannot be represented. So, we are done. $\blacksquare$

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

2726 posts

#11 h Jun 29, 2021, 10:35 PM • 3 Y

Y by Mango247, Mango247, Mango247

In general, consider $S_k = a_0 + \ldots = a_k$ . Note

If $k$ is odd, then $\begin{align*}S_k = (2^0 +2^1 + \ldots + 2^k) + 2(2^0 + 2^1 + \ldots + 2^{(k-1)/2}) &= 2^{k+1} + 2^{(k+3)/2} - 3\\&= a_{k+1} + (2^{(k+1)/2} - 3).\end{align*}$
If $k$ is even, then $\begin{align*}S_k = (2^0 + 2^1 + \ldots + 2^k) + 2(2^0 + 2^1 + \ldots + 2^{(k-2)/2}) + 2^{k/2} &= 2^{k+1} + 3 \cdot 2^{k/2} - 3\\&= a_{k+1} + (2^{(k+2)/2} - 3).\end{align*}$

Hence, generally, we have $a_{k+1} = S_k - (2^{\left\lceil (k+1)/2 \right\rceil} - 3)$ , so thus $a_{k+1}$ is expressible if and only if $(2^{\left\lceil (k+1)/2 \right\rceil} - 3)$ is (we don't have to worry about it having an $a_i$ term in its expression where $i > k$ in for size reasons).

So it suffices to find infinitely many expressible and inexpressible $(2^{\left\lceil (k+1)/2 \right\rceil} - 3)$ across $k \in \mathbb{Z}_+$ .

Note that, given an expressible $2^t - 3$ , we have $S_{2t - 3} - (2^t - 3) = 2^{2t - 2}$ is expressible (and vice versa), and also when given an expressible $2^{2t - 2}$ we have $S_{4t - 7} - 2^{2t-2}= 2^{4t - 6} - 3$ is expressible (and vice versa). We therefore conclude that $2^t - 3$ is expressible iff $2^{4t - 6} - 3$ is expressible.

Note that $2^3 - 3 = 5 = (2^1 + 2^0) + (2^0 + 2^0)$ is expressible, hence we are able to construct an increasing infinite chain $3, f(3), f(f(3)), \ldots = 3, 6, 18, \ldots$ where $f(n) = 4n-6$ for all positive integers $n$ .

The number $2^{f^k(3)} - 3$ is thus always expressible, which indeed exhibits an infinite number of expressible positive integers.

We can probably find a $2^r - 3$ that is inexpressible, and similarly construct a chain $r, f(r), f(f(r), \ldots$ for which $2^{f^k(r)} - 3$ is inexpressible for all $k$ , also exhibiting an infinite number of inexpressible integers.

This post has been edited 13 times. Last edited by jj_ca888, Jun 29, 2021, 10:42 PM

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

434 posts

#12 h Jun 30, 2021, 11:52 PM • 1 Y

Y by Mango247

Claim: $a_n$ is expressible if an only if there exists a subset of previous $n$ terms summing to $2^{\lceil n/2 \rceil} - 3.$

Proof. This is easily verifiable by considering $n$ even vs $n$ odd and evaluating
$\left(\sum_{i=0}^{n-1} 2^i + 2^{\lfloor i/2\rfloor}\right) - (2^n + 2^{\lfloor n/2 \rfloor}) = 2^{\lceil n/2 \rceil} - 3.$ In other words, given a subset of previous terms summing to $a_n,$ we can instead consider the set of terms not chosen, of which must sum to the above, and conversely, if such a set of terms equals $2^{\lceil n/2 \rceil} - 3,$ then $a_n$ is expressible. $\blacksquare$

Claim: $2^k-3$ is expressible if and only if $2^{4k-6}-3$ is expressible.

Proof. If $2^k-3$ is expressible, then note that we may express
$\begin{align*} 2^k-3 + (a_{2k-2} + a_{2k-1} + a_{2k} + \cdots + a_{4k-7}) &= 2^k-3 + ((2^{k-1} + 2^{2k-2}) + (2^{k-1} + 2^{2k-1}) + \cdots + (2^{2k-4} + 2^{4k-8}) + (2^{2k-4} + 2^{4k-7})) \\ &= 2^k - 3 + 2^k(1 + 2 + \cdots + 2^{3k-7}) \\ &= 2^{4k-6} - 3, \end{align*}$ So the forward direction is true. For the reverse, suppose $2^{4k-6}-3$ is expressible, then note that,
$\sum_{i=0}^{4k-7} a_i - (2^{4k-6}-3)= 2^{2k-2} ,$ So $2^{2k-2}$ is expressible. Moreover,
$\sum_{i=0}^{2k-3} a_i - 2^{2k-2} = 2^k-3,$ Implying the desired result. $\blacksquare$

Thus, it suffices to find one non expressible and one expressible of the form $2^k-3,$ giving us infinite chains of expressible terms, for which $2^7-3$ and $2^3-3$ suffice, respectively.

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

277 posts

#13 h Dec 25, 2021, 9:57 AM

Y by

Interesting. Here is a considerably messier but different solution. Also, display mode is slightly overused in this solution, sorry about that.

$\color{red} \boxed{\textbf{Getting Started and Building Up Towards the Solution}}$
$\textbf{Lemma 1:}$
The problem is equivalent to finding infinitely many $k \in \mathbb{N}$ such that there exist and do not exist $b_1,..,b_s \in \{1,..,k\}$ such that $\sum_{i=1}^{s}a_{b_i} = 2^{k+1}-3$ $\textbf{Proof)}$
If $n = 2k+2$ , notice that $a_2+...+a_{2k+1} = 2^{2k+2}+2^{k+2}-3$ Then notice that we have to find distinct $b_1,...,b_s \in \{1,..,2k+2\}$ such that $2^{2k+2}+2^{k+1} = a_{2k+2}=a_2+...+a_{2k+1} - \sum_{i=1}^{s}a_{b_i} = 2^{2k+2}+2^{k+2}-3-\sum_{i=1}^{s}a_{b_i}$ and therefore we need to have that $2^{k+1}-3 = \sum_{i=1}^{s}a_{b_i}$ If $n=2k+1$ , notice that $a_2+...+a_{2k-1}+a_{2k} = 2^{2k}+2^{k+1}-3 + 2^{2k}+2^k = 2^{2k+1}+2^{k+1}+2^k-3$ We then again need to find $b_1,..,b_s \in \{1,..,2k+1\}$ such that $2^{2k+1}+2^k=a_{2k+1} = a_2+...+a_{2k} - \sum_{i=1}^{s}a_{b_i} = 2^{2k+1}+2^{k+1}+2^k-3 - \sum_{i=1}^{s}a_{b_i}$ and consequently $\sum_{i=1}^{s}a_{b_i} = 2^{k+1}-3$ which proves the desired claim. $\blacksquare$

Call some positive integer $N$ $\textit{old}$ if it can be written as a sum of terms of the sequence and $\textit{new}$ otherwise. Moreover, say that $n$ is $\textit{sad}$ if $2^n-3$ is new and $\textit{happy}$ if $2^n-3$ is old.

$\color{blue} \boxed{\textbf{The Construction}}$
We will firstly construct infinitely many $k \in \mathbb{N}$ such that there are $b_1,..,b_s \in \{1,..,k\}$ such that $\sum_{i=1}^{s}a_{b_i} = 2^0+ 2^2 + 2^3+...+2^k = 2^{k+1}-3$ which would imply that $k+1$ is old.
$\textbf{Lemma 2:}$
The above condition is satisfied for all positive integers of the form $2^{2n}+1$ meaning that $2^{2n}+2$ is happy for all $n \in \mathbb{N}$ .
$\textbf{Proof)}$
For every $n \geq 1$ , let $A_n = \{i \in \mathbb{N} \mid 2^{2n-1}+2 \leq i \leq 2^{2n}+1\}$ and let $A_0 = \{1,2\}$ define $B_n = \cup_{i=1}^{n}A_i$ , we will induct on $n$ to show that $\sum_{i \in B_n} a_i = a_{2^{2n}+1}$ with base case $n=1$ .
$\textbf{Inductive Step:}$
Notice that $\sum_{i=2^{2n-1}+2} ^{2^{2n}+1} a_i = \sum_{i=2^{2n-2}+2}^{2^{2n}+1} 2^i = \sum_{0 \leq i \leq 2^{2n}+1, i\neq 1}2^i - \sum_{i \in A_{n-1}} a_i = 2^{2^{2n}+2}-3 - \sum_{i \in A_{n-1}} a_i$ completing the inductive step and the construction $\blacksquare$

$\color{blue} \boxed{\textbf{The Destruction}}$
We know by $\textbf{Lemma 1}$ that the destructive part of the problem is equivalent to showing that there are infinitely many sad $n$ .

$\textbf{Lemma 3:}$ If $n$ is sad, so is $4n-6$ , for all $n \geq 2$ .
$\textbf{Proof)}$
Assume FTSOC that $n$ is sad, yet $4n-6$ is happy.
Then, notice that we can find $A \subset \{1,..,4n-7\}$ such that $2^{4n-6}+2^{2n-2}-3 - \sum_{j \in A} a_{b_j}= \sum_{i=1}^{4n-7} a_i - \sum_{j \in A} a_{b_j} = 2^{4n-6}-3$ meaning that $\sum_{j \in A} a_{b_j} = 2^{2n-2}$ and furthermore that $2^{2n-2}$ is old, meaning that, $2^{2n-2}+2^{n}-3 = \sum_{i \not\in A, i \leq 2n-3} a_{b_i} + \sum_{j \in A} a_{b_j} = \sum_{i \not\in A, i \leq 2n-3} a_{b_i} + 2^{2n-2}$ and consequently, $\sum_{i \not\in A, i \leq 2n-3} a_{b_i} = 2^n-3$ meaning that $n$ is happy, clearly contradicting our initial assumption. $\blacksquare$ .

Now, notice that $5$ is sad meaning that if we define $x_{n+1} = 4x_n-6$ with $x_0 = 5$ , $x_i$ is sad for all $i \in \mathbb{N}$ and the sequence is clearly growing meaning that there are infinitely many sad integers.

Notice that we have proven that there are infinitely many happy and infinitely many sad positive integers which finishes as a consequence of $\textbf{Lemma 1}$ . $\blacksquare$

Motivation and Thoughts

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

5001 posts

#14 h May 30, 2022, 3:24 PM • 2 Y

Y by Mango247, Mango247

Define the partial sums $S_n=a_0+\cdots+a_n$ . A simple computation yields that we have $S_n=2^{n+1}+2^{\lfloor (n+1)/2 \rfloor}+2^{\lceil (n+1)/2\rceil}-3=a_{n+1}+2^{\lceil (n+1)/2\rceil}-3$ . Call a positive integer \textit{expressible} if it can be written as the sum of distinct terms in the sequence $(a_n)$ . The key idea is that if some $x<S_n$ is expressible, then so must $S_n-x$ by taking all the terms not included in the expression of $x$ , and vice versa. Writing $x \iff y$ if $x$ is expressible iff $y$ is, we have $x \iff S_n-x$ , provided that $S_n>x$ .
Thus, we have $a_n \iff 2^{\lceil n/2 \rceil}-3$ , so it suffices to find infinitely many $n$ such that $2^n-3$ is expressible and infinitely many $n$ such that it's not. Since $S_{2n-3}=2^{2n-2}+2^n-3$ , we have $2^n-3 \iff 2^{2n-2}$ . Then, since $S_{4n-7}=2^{4n-6}+2^{2n-2}-3$ , we have $2^{2n-2} \iff 2^{4n-6}-3$ . Since we can manually check that $2^3-3=5$ is expressible and $2^7-3=125$ isn't, we have the following infinite chains
$2^3-5 \iff 2^6-5 \iff 2^{18}-5 \iff \cdots$ and
$2^7-5 \iff 2^{22}-5 \iff 2^{82}-5 \iff \cdots,$ so we're done. $\blacksquare$

This post has been edited 1 time. Last edited by IAmTheHazard, Jun 2, 2022, 6:43 PM

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

1541 posts

#15 h May 27, 2023, 3:00 AM

Y by

Define $s_n = \sum_{i=0}^{n-1} a_i$ .
Then, note that $s_{2k} = (2^0 + 2^1 + \dots + 2^{2k-1}) + 2(2^0 + 2^1 + \dots + 2^{k-1}) = 2^{2k} + 2^{k+1} - 3$ and $s_{2k+1} = (2^0 + 2^1 + \dots + 2^{2k}) + 2(2^0 + 2^1 + \dots + 2^{k-1}) + 2^k = 2^{2k} + 2^{k+1} + 2^k - 3$ so we get $s_{2k} - a_{2k} = 2^k - 3, s_{2k+1} - a_{2k+1} = 2^{k+1} - 3$
It remains to show there are infinite $2^k - 3$ that are the sum of two or more distinct and infinitely many that are not.
Note that $(2^k - 3) + s_{4k-7} - s_{2k-3} = 2^{4k-6} - 3$ Note that $a$ is a sum iff $s_n - a$ is a sum for all $a$ .
Then $2^k - 3$ is a sum iff $s_{2k-3} - (2^k - 3)$ is a sum iff $2^{4k-6} - 3$ is a sum.
Since $2^3 - 3$ is a sum and $2^7 - 3$ is not a sum, the result follows.

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

awesomeming327.

1719 posts

awesomeming327.

#16 h Jun 6, 2023, 9:41 PM

Y by

Let $S_n=a_0+a_1+a_2+\dots + a_n$ . Note that if $n$ is odd then
$\begin{align*} S_n &= a_0+a_1+\dots + a_n\\ &= (2^0 + 2^0) + (2^1 + 2^0) + (2^2+2^1) + (2^3 + 2^1) + \dots + \left(2^n + 2^{\left(\frac{n-1}{2}\right)}\right) \\ &= 2^{n+1}-1 + 2^1 + 2^2 + \dots + 2^{\left(\frac{n+1}{2}\right)} \\ &= 2^{n+1}-1 + 2^{\left(\frac{n+3}{2}\right)} - 2 \\ &= a_{n+1} + 2^{\left(\frac{n+1}{2}\right)} - 3 \end{align*}$ If $n$ is even then
$\begin{align*} S_n &= a_0+a_1+\dots + a_n \\ &= (2^0 + 2^0) + (2^1 + 2^0) + (2^2+2^1) + (2^3 + 2^1) + \dots + \left(2^n + 2^{\left(\frac{n}{2}\right)}\right) \\ &= 2^{n+1}-1 + 2^1 + 2^2 + \dots + 2^{\left(\frac{n}{2}\right)}+2^{\left(\frac{n}{2}\right)} \\ &= 2^{n+1}-1 + 2^{\left(\frac{n+2}{2}\right)} + 2^{\left(\frac{n}{2}\right)} - 2 \\ &= a_{n+1} + 2^{\left(\frac{n+2}{2}\right)} - 3 \end{align*}$ Either way, we have $S_n=a_{n+1}+\left(2^{\left\lfloor\frac{n}{2}+1\right\rfloor}-3\right)$ . Now let $f(x)$ be $1$ if $x$ can be represented as a sum of one or more distinct terms of the sequence less than $x$ and $0$ if not. We wish to prove that infinitely many $i$ such that $f(a_i)=0$ and infinitely many $i$ such that $f(a_i)=1$ .

Note that if $x$ and $y$ are not terms of the sequence, and $x+y=S_n$ then $f(x)=f(y)$ since we can just take the sum of all the terms of sequence we didn't use for $x$ in $y$ . If $x$ is a term of the sequence then the result also holds if $x$ is exactly $a_{n+1}$ .

For example, $f(a_5)=f(S_4-a_5)=f(5)=1$ and $f(a_{13})=f(S_{12}-a_{13})=f(125)=0$ . Now, we have
$f(a_{2k})=f(2^{k}-3)=f(2^{2k-2})=f(2^{4k-6}-3)=f(a_{8k-12})$ which implies the result.

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

1745 posts

OronSH

#17 h Jan 17, 2024, 3:55 PM

Y by

First, for $n \ge 2$ we see that $\sum_{i=0}^{2n-1}a_i=2^{2n}+2^{n+1}-3<2^{2n+1}<a_{2n+1}.$ Thus if $a_{2n+1}$ is representable its representation must have $a_{2n}.$ Now $a_{2n+1}$ is representable iff some subset of $a_i$ for $0\le i\le 2n-1$ to sum to $a_{2n+1}-a_{2n}=2^{2n}.$ Since we have $\sum_{i=0}^{2n-1}a_i=2^{2n}+2^{n+1}-3$ we see that if it is representable then its representation must have $a_i$ for all $n+1\le i\le 2n-1.$ We can check that $2^{2n}-\sum_{i=n+1}^{2n-1}a_i=2^{\frac{n+3}2}$ if $n$ is odd, and we can notice that $a_{n+1}>2^{\frac{n+3}2}.$ Thus for odd $n\ge 3,$ we see that $2^{2n}$ is representable iff $2^{\frac{n+3}2}$ is representable.

Now suppose there is a finite number of $i$ such that $a_{2i+1}$ is not representable. This is equivalent to there being a finite number of $i$ such that $2^{2i}$ is representable. Of these, consider the largest $i,$ which must exist and be greater than or equal to $6$ since we can check that $2^{12}$ is unrepresentable. Now if we have $2i=\frac{n+3}2,$ then we see that when $n=4i-3>i$ then $2^{2n}$ is representable, contradiction. Thus there are an infinite number of unrepresentable $a_i.$ We proceed in the same way to show that there are an infinite number of representable $a_i,$ except we use that the largest $i$ must exist and is greater than or equal to $2$ since $2^4$ is representable by $6+10=a_2+a_3.$

This post has been edited 2 times. Last edited by OronSH, Jan 17, 2024, 10:04 PM

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

759 posts

#18 h Sep 11, 2024, 12:02 AM

Y by

$2^3, 2^4, \dots, 2^11$ are all possible to construct what the frick ;-;
Subjective Rating (MOHs) $\text{[math]}$

Attachments:

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

651 posts

#19 h Apr 25, 2025, 3:52 PM

Y by

We say a number is writeable if it can be written as the sum of two or more distinct previous terms. Note that $\sum_{k = 0}^{2n} a_k = 2^{2n + 1} + 2^{n + 1} + 2^n - 3,$ and $\sum_{k = 0}^{2n - 1} a_k = 2^{2n} + 2^{n + 1} - 3.$

I claim that $2^n - 3$ is writeable if and only if $a_{2n}$ is writeable. We have that $\sum_{k = 0}^{2n - 1} a_n - (2^n - 3) = 2^{2n} + 2^{n}.$

I claim that $2^{4n + 2} - 3$ is writeable if and only if $2^{n + 2} - 3$ is writeable. We have that $\sum_{k = 0}^{4n + 1} a_n - (2^{4n + 2} - 3) = 2^{4n + 2} + 2^{2n + 2} - 3 - 2^{4n + 2}+3 = 2^{2n + 2},$ but $\sum_{k = 0}^{2n + 1} a_k - 2^{2n + 2} = 2^{n + 2} - 3.$ This finishes, as we can provide at least one example of when it is writeable and when it isn't.

Z K Y

N Quick Reply

G

H

=

© 2025 AoPS Incorporated

a