Past exam of the mathematics course of the University of Cambridge / 2009 / ii / Paper 4 / 4H / iii / Solution

True. A length-$d$ linear-feedback shift register has $2^d-1$ nonzero fills, and its first $d$ output bits recover its fill, so these fills give distinct output sequences. If lengths satisfy $r<s$, the longer register has strictly more nonzero outputs. At least one is absent from the shorter register's output set; choosing any nonzero shorter fill then gives unequal outputs. This is the counting property of output sets of different-length linear-feedback registers.