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

False. Take $s_{n+1}=s_n$ and $t_{n+2}=t_{n+1}+t_n$. The only nonzero length-one fill produces constant ones. Constant ones cannot satisfy the second linear recurrence relation, since $1+1=0$ in ${\mathbb{F}}_2$. Thus these linear-feedback shift registers have no identical outputs from nonzero fills.