In this thread here, it makes sense why there is exponential blow up because of the conversion. My question is how would we use induction to prove this? I've started, but I'm getting mixed up with the inductive step.
We start off with the base case being n=2, we have 4 terms, $P,Q,R,S$. As a result of distribution, we generate $((P \lor Q) \land R) \lor (P \lor Q) \land S)$, and this leads to $(P \lor R) \land (Q \lor R) \land (P \lor S) \land (Q \lor S)$, so $2^2 = 4$ clauses. For the inductive hypothesis, we assume that for $n=k$, we will have $2^k$ clauses. Can anyone show how we would do the inductive step?
I get stuck here. Say we have $n=k+1$ terms, then what we end up getting is $2^1 \times 2^k = 2^{k+1}$ clauses, but I can't generate the reasoning behind it. Can anyone help me reason with this step? Thanks.