# Sparsification Lemma for k-SAT. Proof [closed]

In proof that algorithm output at most $$2^{\varepsilon n}$$ families. There are $$\beta_{k-1} n$$ sets along any path ever added to families. Also, there are $$kn/\alpha$$ families along any path. I can not understand why in this case there are $$\sum_{r=1}^{\frac{kn}{\alpha}}{\beta_{k-1} n}\choose{kn/\alpha}$$ paths.

New contributor
Julia is a new contributor to this site. Take care in asking for clarification, commenting, and answering. Check out our Code of Conduct.
• You missed out on the important property that the $kn/\alpha$ families along a path refers only to the number of families created by adding petals. – Kristoffer Arnsfelt Hansen May 21 at 21:04
• My assumption is folowing: the number of path can be find by recursion T(s,p) = T(s-1,p-1)+T(s-1,p) . s is numer of sets along any path, p is petals steps. If we add the heart we do one heart step(only one set) and number of remaining paths is T(s-1,p). If we add petals in worst case it can be only one set and number of remaining paths is T(s-1,p-1). Alltogether T(s,t)=T(s-1,p-1)+T(s-1,p). It has identity with binomial coeffitient. ${{m}\choose{b}}$, da ${{m-1}\choose{b-1}} + {{m-1}\choose{b}} = {{m}\choose{b}}$. I can't understand why the sum in front of ${\beta_{k-1} n}\choose{kn/\alpha}$ – Julia May 23 at 8:19
• Imagine the recursion tree as a binary tree where at a given branching node the heart is added in the left child and the petals are added in the right child. A leaf of the tree is uniquely described by the root-to-leaf path which in turn is described by the the sequence of left and right children followed. Such a path is of length at most $\beta_{k-1}n$ and follows the right child at most $kn/\alpha$ times. – Kristoffer Arnsfelt Hansen yesterday