I a quite confused by the wording of the following problem:
Consider the formal power series $R(X) = \sum_{n\geq 1} r_n X^n$ over $GF(2)[[X]]$. Show that $R$ is algebraic over $GF(2)[X]$ by deriving an algebraic equation, with polynomial coefficients, of which R is a root.
Here $GF(2)$ is the Galois field with two elements, and $r_n = 0$ if and only if n is of the form $4^a(8k+7)$, otherwise $r_n = 1$ (this sequence).
My abstract algebra may be a bit lacking for this course. Essentially what the problem is asking for is a algebraic equation
$$ A(X) = \sum_{n\geq0} a_n X^n = 0 $$
Where each $a_i \in GF(2)[X]$ is a polynomial, and $R(X)$ is a root of $A(X)$.
Am I interpreting the wording correctly? To be a little more explicit, the use of the word "over" is what confuses me the most. In this context what does it mean to be algebraic "over" something?
Your interpretation is more or less correct. In general, if $C$ is a commutative ring and $D$ is a subring of $C$, then an element $c\in C$ is said to be algebraic over $D$ if there exists a polynomial $f(T)\in D[T]$ (not the zero polynomial) such that $f(c)=0$. The "over $D$" just means that the coefficients of $f(T)$ must be elements of $D$. In your case, $C=GF(2)[[X]]$ and $D=GF(2)[X]$.
So in this case, that means you want a nonzero polynomial $f(T)$ whose coefficients are elements of $GF(2)[X]$ such that $f(R(X))=0$. This is almost what you wrote with your $A(X)$, but there are a few points to be careful of. First, $f(T)$ must be a polynomial, which means that your sum $\sum_{n\geq0} a_n X^n$ should be a finite sum (I'm not sure if this is what you had in mind). Second, $f(T)$ must be nonzero, so at least one of your $a_n$ must be nonzero (otherwise $R(X)$ would trivially be a root no matter what). Finally, I would strongly recommend using a variable different from $X$ (as I have done using $T$) to avoid confusion with the use of $X$ as an element of $GF(2)[[X]]$.