Probem: Let $n \ge 2$ be an integer. Then there always exists a family of $2^{n-1}$ subsets of {$1,2,...,n$} such that for every 3 distinct, non-empty members of that family, none of them is the union of the other two.
In the attempt of solving this problem, by mathematical induction. Assume the proposition is true with $n$, that means I have a family of $2^{n-1}$ subsets $A_1, A_2,...,A_{2^{n-1}}$ such that for every 3 distinct, non-empty members of that family, none of them is the union of the other two. Then, I add $n+1$ to each of subsets as above, but it's not correct.
Now I'm stuck without a clue. Please give me a hint to a correct direction.
Any help is greatly appreciated.
I tried to construct such a family of subsets, and I got it: First I divided the family of subsets in disjoint sub-families of subsets by the number of elements: $$0: \{ \emptyset \}\\ 1: \{\{1\},...,\{n\}\}\\ 2: \{\{1,2\},...,\{1,n\},\{2,3\},...,\{n-1,n\}\}\\ ...\\ n:\{\{1,...,n\}\}.$$ As we know, every sub-family with sets containing $i\in\{0,...,n\}$ elements consists of $\binom{n}{i}$ sets.
Now we are going to create for every $i\in\{0,...,n\}$ sub-families of sets from the previous:
For $i=0$ we keep $\{\emptyset\}$ as it is. For $i$ being odd we throw out every subset containing for example $n$, so we construct $$ \{\{x_1,...,x_i\}|x_1,...,x_i \in\{1,...,n-1\},\,x_k\neq x_l\; \forall k,l\in \{1,...,i\}\,:\, k\neq l\}. $$ Every family consists of $\binom{n-1}{i}$ subsets for every odd $i<n$. For $i=n$ we don't have any subset, because the only set with $n$ elements is $\{1,...,n\}$, which contains $n$ and can not be constructed according to the definition above.
If $i$ is even, then the element $n$ has to be in:
$$ \{\{x_1,...,x_i\}|x_1,...,x_{i-1} \in\{1,...,n-1\},\,x_k\neq x_l\,\, \forall k,l\in \{1,...,i-1\}\,:\, k\neq l,\, x_i=n\}. $$ for every even $i$ the family consists of $\binom{n-1}{i-1}$ subsets.
Now you unite these families as one and you have your set. We will check later if we reach $2^{n-1}$, first we will see if the other conditions hold.
We have constructed all our subsets $M\subseteq\{1,...,n\}$ so that if the number of elements is odd, then $n\notin M$ and if it's even, then $n\in M$.
Let's say we have such a family, which is constructed according to the above plan, if we take a set $M\subseteq\{1,...,n\}$ with an odd number of elements, the only disjoint union possible between two other subsets is only possible, if one subset has an even number of elements and the other an odd one (else it would not be disjoint, for example $5=1+4=2+3$, there are no two summands which are both even or both odd). Then such an union is impossible, since $n\notin M$ and $n$ is in the subset with the even number of elements.
If $M\subseteq\{1,...,n\}$ has an even number of elements, then any two subsets of the family we take for a disjoint union have to have either both an even number of elements or both an odd number of elements. If both are even, then both subsets contain $n$, so the union can't be disjoint. On the other hand if both subsets are odd, then both don't contain $n$ and we can't make up $M$.
So we have proven, that this condition holds, it remains to show that the union of these families make at least $2^{n-1}$ subsets. By the way, they are disjoint.
As you can notice, every family with subsets of an even number of elements has the same cardinality as the family of subsets, where the number of elements in each subset is one less (the previous odd number). This holds even if n is even and the family $\{\{1,...,n\}\}$, because it has only one subset and for the previous integer the family has $\binom{n-1}{n-1}=1$ subsets. If $n$ is odd, then the family doesn't contain $\{\{1,...,n\}\}$, because this subset contains $n$. So we can just keep counting the cardinalities for every odd number twice, as long as every odd number $i$ is smaller than $n$.
So we have for odd $n$: $$ 1+\binom{n-1}{1}+\binom{n-1}{1}+\binom{n-1}{3}\binom{n-1}{3}+...+\binom{n-1}{n-2}+\binom{n-1}{n-2}+0\\ =1+2\cdot\sum_{i=0}^{\frac{n-3}{2}}\binom{n-1}{2i+1} =1+2\cdot\sum_{i=0}^{\frac{(n-1)-2}{2}}\binom{n-1}{2i+1}\\ =1+2\cdot\sum_{i=0}^{\lceil\frac{(n-1)-1}{2}\rceil}\binom{n-1}{2i+1} = 1+2\cdot 2^{n-2} \geq 2^{n-1}. $$ For one of the last steps I used an identity of binomial coefficients:
https://proofwiki.org/wiki/Sum_of_Odd_Index_Binomial_Coefficients
For even $n$ we have $$ 1+\binom{n-1}{1}+\binom{n-1}{1}+\binom{n-1}{3}\binom{n-1}{3}+...+\binom{n-1}{n-1}+\binom{n-1}{n-1}\\ =1+2\cdot\sum_{i=0}^{\frac{n-2}{2}}\binom{n-1}{2i+1} =1+2\cdot\sum_{i=0}^{\frac{(n-1)-1}{2}}\binom{n-1}{2i+1}\\ =1+2\cdot\sum_{i=0}^{\lceil\frac{(n-1)-1}{2}\rceil}\binom{n-1}{2i+1} = 1+2\cdot 2^{n-2} \geq 2^{n-1} $$ Here I used similarly:
https://proofwiki.org/wiki/Sum_of_Even_Index_Binomial_Coefficients
So it's proven!