A characteristic 2 polynomial recursion Let $c(n)$ in $\mathbb{Z}/2\mathbb{Z}[x]$ be defined by the recursion $$c(n+4)=c(n+3)+(x^4+x^3+x^2+x)c(n)+x^n\cdot(x+x^2),$$ and the initial conditions 
$$c(0)=0,\quad c(1)=1,\quad c(2)=x,\quad c(3)=x^2.$$
Question: If 4 divides $n$, is $c(n)$ a sum of $c(k)$ with $k$ less than $n$?
Remarks:


*

*I've checked that this holds up to $n=64$.

*The recursion may seem artificial, but it arises in studying the action of the operator $U_3$ on a space of mod $2$ modular forms of level 3. This accounts for the number theory tag.



VARIATION ON A THEME
Now define another sequence $c(n)$ in $\mathbb Z/2\mathbb Z[x]$ by the recursion
$$c(n+6)=c(n+5)+(x^6+x^5+x^2+x)c(n)+x^n\cdot(x+x^2),$$
 and the initial conditions 
$$c(0)=0,\quad c(1)=1,\quad c(2)=1,\quad c(3)=x,\quad c(4)=x^2,\quad c(5)=x^4+x^2+x.$$
Question: If $n$ is 0 or 2 mod 6, is $c(n)$ a sum of $c(k)$ with $k$ less than $n$?


*

*I've checked that this holds through n=44.

*This question bears the same relation to mod 2 modular forms of level 5 that my initial question bears to level 3.


TWO VARIATIONS IN CHARACTERISTIC 3
Variation 2a---Let c(n) in Z/3[x] be defined by the recursion
c(n+3)=c(n+2)-(x^3+x^2+x)c(n)+x^n*(x^3-x), and the initial conditions
c(0)=0,  c(1)=x,  c(2)=x.
If (n,3)=1, define d(n) to be c(n)+c(n+1)+c(n+2) or c(n)-c(n+1) according as n is 1 or 2 mod 3.
Question:  If n is 2 mod 9, is d(n) a Z/3-linear combo of d(k) with k less than n?
Variation 2b---Let c*(n) be c(n)-x^n with c(n) as in variation 2a. For n prime to 3 define d*(n) as in variation 2a, but with c(n) replaced by c*(n).
Question: If n is 2 mod 9, is d*(n) a Z/3 linear combo of d*(k) with k less than n?
Remarks: I've verified that these hold for n up through 83, and am confident that a variant of Peter Mueller's technique will allow one to go much further. The questions are related to calculating the kernels of U_2+I and U_2-I on the space of mod 3 modular forms of level 2, just as the earlier questions were related to calculating the kernels of U_3+I and U_5+I on the spaces of mod 2 modular forms of levels 3 and 5 respectively.
FINAL EDIT (12/7/16)


*

*I've found elementary but apparently mysterious answers to the first 2 questions--see my 2 answers. The arguments are similar, and I'll randomly accept the level 3 answer.

*I think I can answer the characteristic 3 questions too. But to avoid accusations of self-abuse I'll refrain. And though I find the question on Jordan blocks very interesting (and similar questions attached to the other recursions should also be interesting), the thread has become long and so I've deleted that question.
 A: EDIT (11/25/16)
The earlier version of this answer is sketchy, and as I've put up a complete version on arXiv (1603.03910 [math.NT], "A characteristic 2 recurrence with a Hecke algebra application"), I'm replacing my answer with references to this preprint. The argument, culminating in Theorem 2.10, involves nothing more than algebra in a ring Z/2[r], but would be mysterious to someone without a knowledge of modular forms--see the remark preceding Definition 1.1.
The final sections of the preprint give an application of Theorem 2.10 to the space K consisting of the odd mod 2 modular forms of level Gamma_0 (3) that are
killed by I+U_3. Combining Theorem 2.10 with results from arXiv:1508.07523 [math.NT], "A Hecke algebra attached to mod 2 modular forms of level 3", I show that each formal Hecke operator T_p acting on K is (uniquely) a power series in T_7 and T_13.
A: A stronger property seems to hold: If $n$ fulfills the congruence condition such that $c(n)$ is expected to be a sum of $c(k)$'s with $k<n$, then the following greedy algorithm works (for both questions) up to $n=10000$: Start with $f=c(n)$. For $j$ running from $n-1$ down to $0$ replace $f$ with $f+c(j)$ whenever $f$ and $c(j)$ have the same degree. So the degree of the new $f$ drops in such a step. If we get $f=0$, then we have the requested sum. If we finish in $j=0$ and still $f\ne0$, then the algorithm fails.
A Sage code (for the second question) which checks the cases up to $n=10000$ within a few seconds is
K.<x> = GF(2)[]
l = [K(0), K(1), K(1), x, x^2, x^4+x^2+x]
n = len(l)
while n < 10001:
    f = l[-1] + (x^6+x^5+x^2+x)*l[-6]+x^(n-6)*(x+x^2)
    l.append(f)
    if n%6 in [0,2]:
        print n
        for j in range(n-1,0,-1):
            if f.degree() == l[j].degree():
                f += l[j]
                if f == 0:
                    break
        else:
            print "FAIL"
            break
    n += 1

A: EDIT (12/7/16)
This answer deals with the "VARIATIONS ON A THEME". Again my earlier answer was sketchy, and I'm replacing it by references to my arXiv preprint (1612.01599 [math.NT], "A characteristic 2 recurrence attached to U_5 with a Hecke algebra application"). The entirely elementary (but seemingly mysterious) argument takes place in the few pages between Definition 1.1 and Theorem 2.11 of that note. Looking at the material preceding Definition 1.1 will help in understanding the mysteries.
The rest of the note uses Theorem 2.11 (slightly strengthened) to study the Hecke operators T_p acting on a space, K, consisting of the mod 2 modular forms of level Gamma_0 (5) annihilated by U_5+I. It's shown that each T_p, p>5, is (uniquely) in its action on K a power series with zero constant term in T_3 and T_7.
