Consider the recurrence relation $x_{n+4}\equiv x_n+x_{n+1}+x_{n+3}$ mod 2, with initial values $1\text{,}0\text{,}0\text{,}0$. We need to use 0s and 1s, but we need to tell Sage that they are numbers mod 2. One way is to define “o” (that’s a lower-case “oh”) and “l” (that’s an “ell”) to be 0 and 1 mod 2:

F=GF(2) 
o=F(0); l=F(1)

We also could use F(0) every time we want to enter a 0, but the present method saves some typing. Now we specify the coefficients and initial values of the recurrence relation, along with how many terms we want. In the following, we ask for 20 terms:

s=lfsr_sequence([l,l,o,l],[l,o,o,o],20);s

This evaluates to

[1, 0, 0, 0, 1, 1, 1, 0, 0, 0, 1, 1, 1, 0, 0, 0, 1, 1, 1, 0]

Suppose we are given these terms of a sequence and we want to find what recurrence relation generates it:

berlekamp_massey(s)

This evaluates to

x^4 + x^3 + x + 1

When this is interpreted as $x^4\equiv 1+1x+0x^2+1x^3$ mod 2, we see that the coefficients 1, 1, 0, 1 of the polynomial give the coefficients of recurrence relation. In fact, it gives the smallest relation that generates the sequence.

Note: Even though the output for s has 0s and 1s, if we try entering the command berlekamp_massey([1,1,0,1,1,0]) we get x^3 - 1. If we instead enter berlekamp_massey([l,l,o,l,l,o]), we get x^2 + x + 1. Why? The first is looking at a sequence of integers generated by the relation $x_{n+3}=x_n$ while the second is looking at the sequence of integers mod 2 generated by $x_{n+2}\equiv x_n+x_{n+1}$ mod 2. Sage defaults to integers if nothing is specified. But it remembers that the 0s and 1s that it wrote in s are still integers mod 2.