Lesson 1

We never expand \(\prod_{i}(1+x^{p_i})\) all at once. Instead we multiply the factors one at a time, and because we only care about prices up to \(B\), we discard every power above \(B\) as we go. Following a single coefficient through this process gives a recurrence. Let \(C_{i}(b)\) be the number of portfolios that use only the first \(i\) stocks and have total price \(b\). The initial values are \(C_{0}(0)=1\) and \(C_{0}(b)=0\) for \(b>0\). When we process stock \(i\), there are two possibilities: either we do not buy it, or we buy it. Therefore, \[C_{i}(b)=C_{i-1}(b)+C_{i-1}(b-p_{i}).\] Here \(C_{i-1}(b-p_{i})\) is treated as \(0\) when \(b<p_{i}\). This recurrence is exactly multiplication by the factor \((1+x^{p_i})\), truncated to degrees at most \(B\). So the dynamic program is not a rival of the generating function; it is the generating function, built up one factor at a time.