Full question: Prove that if a collection of subsets of {1,2,…,n} has the property that each pair of subsets has at least one element in common, then there are at most $2^{n-1}$ subsets in the collection.
I have tried to do an inductive proof as follows:
Base case: When $n = 1$, there is only the set {1}, so $2^{1-1} = 2^0 = 1$ subset in the collection
Inductive step: Let $P(n)$ denote the number of subsets of {1,2,…n} that have at least one element in common, which we will call $A$, is smaller or equal to $2^{n-1}$
Assume $P(n)$ is true. Now we take a look at $P(n+1)$. We can divide subsets of {1,2,…,n+1} into two kind, those containing $n+1$, and those that don't. We know there are $A$ subsets that don't contain $n+1$. For subsets containing $n+1$, we can have $2^n$ subsets. In total, $A + 2^n \geq 2^{n+1-1} = 2^n$, which is obviously incorrect.
I'm not sure if it's possible to do it with an inductive proof, so any kind of proof is welcome. However, it would be great if someone could explain how to do it with the method above, and perhaps point out my mistakes.
Best Answer
An inductive proof is not the way to go.
What I think you’re missing in your attempt to prove the result by induction is that there are many such collections of subsets of $[n]$. For instance, if $n=3$ one such collection is
$$\big\{\{1\},\{1,2\},\{1,2,3\},\{1,2,3,4\}\big\}\;,$$
and another is
$$\big\{\{1,2\},\{1,3\},\{2,3\},\{1,2,3\}\big\}\;.$$
Thus, the induction step of a proof by induction would have to start by letting $\mathscr{A}$ be a collection of subsets of $[n+1]$ such that every pair of members of $\mathscr{A}$ have an element in common; the idea would be to use the induction hypothesis to show that $|\mathscr{A}|\le 2^n$.