4

Consider the following sequence:

$$a_1=1$$ $$a_n=\text{Number of subsets of } \{a_1,a_2,...,a_{n-1}\} \text{ that sum to } a_{n-1}$$

The first few elements of that sequence are

$$1,1,2,2,3,5,6,...$$


What can be said about this sequence?


A simple observation is that since $\{a_{n-1}\}$ trivially sums to itself, $a_n\ge 1$ for all $n\in\mathbb{N}$.

Also, since the number of subsets of an $n$-element set is $2^n$, $a_n\le 2^{n-1}$.

Note that it is far from trivial whether the sequence is even monotonous, since it could be that for some $n\in \mathbb{N}$, $a_n$ explodes to a value so large that there is no subset of $\{a_1,a_2,...,a_{n}\}$ besides $\{a_n\}$ that sums to it, making $a_{n+1}=1$.

user9723763
  • 41
  • this is close. could be just co-incidence though. – Guy Mar 17 '14 at 14:56
  • Yes, I saw that, but I thought it a coincidence also. There are several hits on OEIS for those numbers; none seem to fit even remotely (except maybe for some hidden "deep" connection). – user9723763 Mar 17 '14 at 14:58
  • "deep" yes. interesting if someone comes up with something. – Guy Mar 17 '14 at 15:02
  • I find the notation to be a little confusing given that some of the elements $a_i$ may be identical. Perhaps it would be better to say that $a_n$ is the number of subsets $J$ of ${1,2,3,...,n-1}$ such that $\sum_{j \in J} a_j = a_{n-1}$. If this is so I wrote some code to brute force count some more in the sequence and came up with: (1, 1, 2, 2, 3, 5, 6, 8, 11, 17, 25, 33), which thus far is increasing. – Squid Mar 17 '14 at 16:12
  • 1
    Carrying the computation a little further gives the sequence: 1, 1, 2, 2, 3, 5, 6, 8, 11, 17, 25, 33, 41, 52, 80, 139, 204, 245, 289, 410, 692, 1159, 1477, 2010, 2769, 4247, 6128, 7709, 9817 – Esteban Crespi Mar 17 '14 at 16:19
  • Note that $1477-1159<1159-692$, so at least the differences between consecutive elements are not monotonic. –  Mar 17 '14 at 18:29

0 Answers0