# LFSR, different bits from different initial states

Suppose we use an LFSR, which gives output $$x_1x_2x_3\dots$$ from some particular initial state. From another state, different from the previous one, using the same LFSR though, it gives sequence $$y_1y_2y_3\dots$$

Intuitively, some $$i$$ inequality must be true for $$x_i\neq y_i$$, but "intuitively" isn't exactly convincing, neither is "empirically."

Is it true that for some $$i$$ bits, the result will be different, i.e., $$x_i\neq y_i$$, and if so - why?

• Hint: in a Fibonnaci LFSR, the bits of the initial state are also the first bits of the output; this makes it easy to prove the result for such LFSR. Then you can use the equivalence of Fibonnaci and Galois LFSRs to prove the result for the other kind.
– fgrieu
Sep 19 '15 at 16:19
• But of course! Thanks.. it was too close to think about Sep 19 '15 at 16:36