[proofplan] We proceed by induction on $r$ and, for fixed $r$, by strong induction on $|\mathcal{A}|$. First reduce to the case where $\mathcal{A}$ is left-compressed (via the [Simple Compression Reduces Shadow](/theorems/2592) theorem). Then partition $\mathcal{A}$ according to whether element $1$ is present, use the left-compression property to relate the shadow of $\mathcal{A}_0$ (sets not containing $1$) to $\mathcal{A}_1$ (sets containing $1$), derive $|\mathcal{A}_1| \geq \binom{x-1}{r-1}$ by contradiction, and combine with an inductive application on $r$ to obtain $|\partial \mathcal{A}| \geq \binom{x}{r-1}$. [/proofplan] [step:Reduce to a left-compressed family] By repeatedly applying simple compressions $C_{ij}$ for all $i < j$ (which is possible since the family is finite and each compression either changes the family or fixes it), we may assume $\mathcal{A}$ is left-compressed. The [Simple Compression Reduces Shadow](/theorems/2592) theorem guarantees that each compression preserves $|\mathcal{A}|$ and does not increase $|\partial \mathcal{A}|$. A left-compressed family satisfies: whenever $A \in \mathcal{A}$, $j \in A$, $i \notin A$, and $i < j$, the set $(A \setminus \{j\}) \cup \{i\} \in \mathcal{A}$. [guided] Before starting the induction, we simplify the structure of $\mathcal{A}$. A family is left-compressed if replacing any element by a smaller element not already present always stays in the family. We can reach this condition by iteratively applying simple compressions $C_{ij}$ for all pairs $i < j$. Each application of $C_{ij}$ preserves $|\mathcal{A}|$ (by the size-preserving property of compressions) and satisfies $|\partial C_{ij}(\mathcal{A})| \leq |\partial \mathcal{A}|$ (by the [Simple Compression Reduces Shadow](/theorems/2592) theorem). Since $X$ is finite, there are finitely many pairs $(i, j)$, and each compression either changes $\mathcal{A}$ or fixes it. The process terminates because $\Sigma(\mathcal{A}) = \sum_{A \in \mathcal{A}} \sum_{i \in A} 2^i$ strictly decreases at each nontrivial compression. The resulting family is left-compressed, has the same size, and has shadow no larger than the original. So it suffices to prove the bound $|\partial \mathcal{A}| \geq \binom{x}{r-1}$ for left-compressed families $\mathcal{A}$. [/guided] [/step] [step:Set up the double induction and the base cases] We induct on $r \geq 1$ and, for fixed $r$, on $|\mathcal{A}|$. **Base case $r = 1$**: The family $\mathcal{A} \subseteq X^{(1)}$ consists of $|\mathcal{A}|$ singletons, so $|\mathcal{A}| = \binom{x}{1} = x$ gives $x = |\mathcal{A}|$. The shadow is $\partial \mathcal{A} = \{\varnothing\}$ if $\mathcal{A} \neq \varnothing$, so $|\partial \mathcal{A}| = 1 = \binom{x}{0}$. The bound holds. **Base case $|\mathcal{A}| = 1$**: We have $\binom{x}{r} = 1$, so $x = r$ (since $\binom{r}{r} = 1$). The single set $A \in \mathcal{A}$ has $|\partial \{A\}| = r = \binom{r}{r-1} = \binom{x}{r-1}$. The bound holds with equality. [guided] We use a double induction: the outer induction is on $r$ (the uniformity), and for each $r$, we use strong induction on $|\mathcal{A}|$. This means when proving the result for a particular $r$ and $|\mathcal{A}|$, we may use the result for all smaller $r'$ (with any family size) and for the same $r$ with any smaller family. **Base case $r = 1$**: Each member of $\mathcal{A}$ is a singleton $\{a\}$, and its shadow consists of $\varnothing$ alone. So $|\partial \mathcal{A}| = 1$ whenever $\mathcal{A} \neq \varnothing$. We have $|\mathcal{A}| = x$ (from $\binom{x}{1} = x$), and $\binom{x}{0} = 1$, so the bound $|\partial \mathcal{A}| \geq \binom{x}{0}$ holds. **Base case $|\mathcal{A}| = 1$**: A single $r$-element set has exactly $\binom{r}{r-1} = r$ subsets of size $r - 1$, so $|\partial \mathcal{A}| = r$. Since $|\mathcal{A}| = 1 = \binom{r}{r}$, we have $x = r$, and $\binom{x}{r-1} = \binom{r}{r-1} = r = |\partial \mathcal{A}|$. [/guided] [/step] [step:Partition $\mathcal{A}$ into $\mathcal{A}_0$ and $\mathcal{A}_1$ according to the presence of element $1$] For the inductive step, assume $r \geq 2$ and $|\mathcal{A}| \geq 2$. Partition $\mathcal{A}$ into \begin{align*} \mathcal{A}_0 &= \{ A \in \mathcal{A} : 1 \notin A \}, \\ \mathcal{A}_1 &= \{ A \in \mathcal{A} : 1 \in A \}. \end{align*} Define $\mathcal{A}_1 - 1 = \{ A \setminus \{1\} : A \in \mathcal{A}_1 \} \subseteq X^{(r-1)}$, which has $|\mathcal{A}_1 - 1| = |\mathcal{A}_1|$ (the map $A \mapsto A \setminus \{1\}$ is injective on $\mathcal{A}_1$). Since $\mathcal{A}$ is left-compressed and $|\mathcal{A}| \geq 2$, the subfamily $\mathcal{A}_1$ is nonempty: for any $A \in \mathcal{A}_0$, pick any $j \in A$; then $j > 1$ (since $1 \notin A$), and left-compression gives $(A \setminus \{j\}) \cup \{1\} \in \mathcal{A}_1$. In particular, $|\mathcal{A}_0| < |\mathcal{A}|$. [/step] [step:Show $\partial \mathcal{A}_0 \subseteq \mathcal{A}_1 - 1$ using left-compression] Let $B \in \partial \mathcal{A}_0$. Then $|B| = r - 1$ and $B \subset A$ for some $A \in \mathcal{A}_0$. Since $A \in \mathcal{A}_0$, we have $1 \notin A$, so $1 \notin B$. The set $A$ has exactly one element $j \in A \setminus B$, and $j > 1$ since $1 \notin A$. Since $\mathcal{A}$ is left-compressed, $1 \notin A$, and $j \in A$ with $1 < j$, the set $A' = (A \setminus \{j\}) \cup \{1\}$ belongs to $\mathcal{A}$. Since $1 \in A'$, we have $A' \in \mathcal{A}_1$. Moreover, $B \subset A$ with $j \notin B$ gives $B \subseteq A \setminus \{j\} = A' \setminus \{1\}$, so $B \subseteq A' \setminus \{1\} \in \mathcal{A}_1 - 1$. Since $|B| = r - 1 = |A' \setminus \{1\}|$, we have $B = A' \setminus \{1\} \in \mathcal{A}_1 - 1$. This shows $\partial \mathcal{A}_0 \subseteq \mathcal{A}_1 - 1$, and in particular \begin{align*} |\partial \mathcal{A}_0| \leq |\mathcal{A}_1 - 1| = |\mathcal{A}_1|. \end{align*} [guided] Let $B \in \partial \mathcal{A}_0$, so $B$ is an $(r-1)$-element subset of some $A \in \mathcal{A}_0$. Since $1 \notin A$ (as $A \in \mathcal{A}_0$), we also have $1 \notin B$. Write $A \setminus B = \{j\}$; then $j > 1$. Now use the left-compression property: since $j \in A$, $1 \notin A$, and $1 < j$, replacing $j$ by $1$ gives $A' = (A \setminus \{j\}) \cup \{1\} \in \mathcal{A}$. Since $1 \in A'$, the set $A'$ belongs to $\mathcal{A}_1$. We claim $B = A' \setminus \{1\}$. Indeed, $A' \setminus \{1\} = A \setminus \{j\}$ and $B = A \setminus \{j\}$ (since $B \subset A$ with $A \setminus B = \{j\}$). So $B = A' \setminus \{1\} \in \mathcal{A}_1 - 1$. This inclusion $\partial \mathcal{A}_0 \subseteq \mathcal{A}_1 - 1$ is the crucial consequence of left-compression. Intuitively, it says that every $(r-1)$-subset in the boundary of the "element-$1$-free" part already appears as a "trace" of the "element-$1$-containing" part. It gives the size bound $|\partial \mathcal{A}_0| \leq |\mathcal{A}_1|$. [/guided] [/step] [step:Prove $|\mathcal{A}_1| \geq \binom{x-1}{r-1}$ by contradiction using the inductive hypothesis on $|\mathcal{A}|$] Suppose for contradiction that $|\mathcal{A}_1| < \binom{x-1}{r-1}$. Then \begin{align*} |\mathcal{A}_0| = |\mathcal{A}| - |\mathcal{A}_1| > \binom{x}{r} - \binom{x-1}{r-1} = \binom{x-1}{r}, \end{align*} where the last equality is the Pascal identity $\binom{x}{r} = \binom{x-1}{r-1} + \binom{x-1}{r}$, valid for all real $x$ (the generalised binomial coefficient $\binom{x}{r} = \frac{x(x-1)\cdots(x-r+1)}{r!}$ satisfies this identity by direct computation). Write $|\mathcal{A}_0| = \binom{y}{r}$ for a unique real $y \geq r$ (which exists since $\binom{\cdot}{r}$ is continuous and strictly increasing on $[r, \infty)$ and $|\mathcal{A}_0| \geq 1$). From $|\mathcal{A}_0| > \binom{x-1}{r}$ and the strict monotonicity of $\binom{\cdot}{r}$, we get $y > x - 1$. Since $|\mathcal{A}_0| < |\mathcal{A}|$ (as $\mathcal{A}_1 \neq \varnothing$), the inductive hypothesis (on $|\mathcal{A}|$) applies to $\mathcal{A}_0$: \begin{align*} |\partial \mathcal{A}_0| \geq \binom{y}{r-1}. \end{align*} Since $y > x - 1$ and $\binom{\cdot}{r-1}$ is strictly increasing on $[r-1, \infty)$, we have $\binom{y}{r-1} > \binom{x-1}{r-1}$. Therefore \begin{align*} |\partial \mathcal{A}_0| > \binom{x-1}{r-1} > |\mathcal{A}_1|, \end{align*} contradicting $|\partial \mathcal{A}_0| \leq |\mathcal{A}_1|$ from the previous step. Hence $|\mathcal{A}_1| \geq \binom{x-1}{r-1}$. [guided] Suppose for contradiction that $|\mathcal{A}_1| < \binom{x-1}{r-1}$. We derive a contradiction by showing this forces $|\partial \mathcal{A}_0|$ to exceed $|\mathcal{A}_1|$, violating the inclusion $\partial \mathcal{A}_0 \subseteq \mathcal{A}_1 - 1$. First, compute $|\mathcal{A}_0|$. The partition $\mathcal{A} = \mathcal{A}_0 \sqcup \mathcal{A}_1$ gives \begin{align*} |\mathcal{A}_0| = |\mathcal{A}| - |\mathcal{A}_1| > \binom{x}{r} - \binom{x-1}{r-1}. \end{align*} The generalised Pascal identity states $\binom{x}{r} = \binom{x-1}{r-1} + \binom{x-1}{r}$ for all real $x$. To verify: $\binom{x-1}{r-1} + \binom{x-1}{r} = \frac{(x-1)!_r}{(r-1)! \cdot r} \cdot \left(\frac{r}{1} + \frac{x - r}{1}\right)$ where $(x-1)!_r$ denotes the falling factorial, which simplifies to $\frac{x(x-1)\cdots(x-r+1)}{r!} = \binom{x}{r}$. So $|\mathcal{A}_0| > \binom{x-1}{r}$. Now define $y$ by $\binom{y}{r} = |\mathcal{A}_0|$. The function $t \mapsto \binom{t}{r} = \frac{t(t-1)\cdots(t-r+1)}{r!}$ is a polynomial of degree $r$ in $t$, which is continuous and strictly increasing for $t \geq r$. Since $|\mathcal{A}_0| > \binom{x-1}{r}$, strict monotonicity gives $y > x - 1$. We can apply the inductive hypothesis to $\mathcal{A}_0$ because $|\mathcal{A}_0| < |\mathcal{A}|$ (the subfamily $\mathcal{A}_1$ is nonempty, as shown earlier). The inductive hypothesis gives $|\partial \mathcal{A}_0| \geq \binom{y}{r-1}$. Since $y > x - 1$ and $\binom{\cdot}{r-1}$ is strictly increasing on $[r-1, \infty)$, we get $\binom{y}{r-1} > \binom{x-1}{r-1}$. Chaining the inequalities: $|\partial \mathcal{A}_0| \geq \binom{y}{r-1} > \binom{x-1}{r-1} > |\mathcal{A}_1|$. But $\partial \mathcal{A}_0 \subseteq \mathcal{A}_1 - 1$ gives $|\partial \mathcal{A}_0| \leq |\mathcal{A}_1|$, a contradiction. Therefore $|\mathcal{A}_1| \geq \binom{x-1}{r-1}$. [/guided] [/step] [step:Decompose $\partial \mathcal{A}$ and apply the inductive hypothesis on $r$ to conclude] The shadow of $\mathcal{A}$ satisfies $\partial \mathcal{A} \supseteq \partial \mathcal{A}_1$. We decompose $\partial \mathcal{A}_1$ according to whether element $1$ is present. Each $A \in \mathcal{A}_1$ contains $1$ and has $r$ subsets of size $r - 1$: the set $A \setminus \{1\}$ (which does not contain $1$) and the $r - 1$ sets $A \setminus \{j\}$ for $j \in A \setminus \{1\}$ (each of which contains $1$). Therefore \begin{align*} \partial \mathcal{A}_1 &\supseteq (\mathcal{A}_1 - 1) \;\cup\; \{B \cup \{1\} : B \in \partial(\mathcal{A}_1 - 1)\}. \end{align*} The two parts are disjoint (the first consists of $(r-1)$-sets not containing $1$, the second of $(r-1)$-sets containing $1$). Hence \begin{align*} |\partial \mathcal{A}| \geq |\partial \mathcal{A}_1| \geq |\mathcal{A}_1 - 1| + |\partial(\mathcal{A}_1 - 1)| = |\mathcal{A}_1| + |\partial(\mathcal{A}_1 - 1)|. \end{align*} Since $|\mathcal{A}_1 - 1| = |\mathcal{A}_1| \geq \binom{x-1}{r-1}$, write $|\mathcal{A}_1 - 1| = \binom{z}{r-1}$ for some real $z \geq x - 1 \geq r - 1$. The family $\mathcal{A}_1 - 1 \subseteq X^{(r-1)}$ has uniformity $r - 1$, so the inductive hypothesis on $r$ gives \begin{align*} |\partial(\mathcal{A}_1 - 1)| \geq \binom{z}{r-2}. \end{align*} Since $z \geq x - 1$, and $\binom{\cdot}{r-1}$ and $\binom{\cdot}{r-2}$ are both increasing, \begin{align*} |\partial \mathcal{A}| \geq \binom{z}{r-1} + \binom{z}{r-2} \geq \binom{x-1}{r-1} + \binom{x-1}{r-2} = \binom{x}{r-1}, \end{align*} where the last equality is the Pascal identity $\binom{x-1}{r-1} + \binom{x-1}{r-2} = \binom{x}{r-1}$. [guided] We now bring everything together. The shadow of $\mathcal{A}_1$ decomposes naturally. Each set $A \in \mathcal{A}_1$ has the form $A = \{1\} \cup A'$ where $A' = A \setminus \{1\} \in \mathcal{A}_1 - 1$. The $(r-1)$-subsets of $A$ split into two types: - $A \setminus \{1\} = A'$: this is a member of $\mathcal{A}_1 - 1$, and it does not contain $1$. - $A \setminus \{j\}$ for $j \in A' = A \setminus \{1\}$: this equals $\{1\} \cup (A' \setminus \{j\})$, and it contains $1$. As $j$ ranges over $A'$, the set $A' \setminus \{j\}$ ranges over all $(r-2)$-subsets of $A'$, so these $(r-1)$-sets of $A$ are in bijection with the members of $\partial(\mathcal{A}_1 - 1)$ that come from $A'$. Taking the union over all $A \in \mathcal{A}_1$, the shadow $\partial \mathcal{A}_1$ contains both $\mathcal{A}_1 - 1$ (the "remove $1$" part) and $\{1\} \cup B : B \in \partial(\mathcal{A}_1 - 1)\}$ (the "keep $1$" part). These two collections are disjoint because the first consists of sets not containing $1$ and the second of sets containing $1$. So \begin{align*} |\partial \mathcal{A}| \geq |\partial \mathcal{A}_1| \geq |\mathcal{A}_1| + |\partial(\mathcal{A}_1 - 1)|. \end{align*} For the first summand, we proved $|\mathcal{A}_1| \geq \binom{x-1}{r-1}$. For the second summand, we apply the inductive hypothesis on $r$. The family $\mathcal{A}_1 - 1$ has uniformity $r - 1$ and size $|\mathcal{A}_1| \geq \binom{x-1}{r-1}$. Writing $|\mathcal{A}_1 - 1| = \binom{z}{r-1}$ for $z \geq x - 1$, the inductive hypothesis gives $|\partial(\mathcal{A}_1 - 1)| \geq \binom{z}{r-2} \geq \binom{x-1}{r-2}$. Combining: \begin{align*} |\partial \mathcal{A}| \geq \binom{x-1}{r-1} + \binom{x-1}{r-2} = \binom{x}{r-1}, \end{align*} where the last step uses the generalised Pascal identity $\binom{x-1}{r-1} + \binom{x-1}{(r-1)-1} = \binom{x}{r-1}$ (applied with $r-1$ in place of $r$). This completes the induction and establishes the Lovász bound. [/guided] [/step]