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**:

 1. I've checked that this holds up to $n=64$.
 2. 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.

<HR> 
**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$?

 1. I've checked that this holds through n=44.
 2. 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 (9/5/15)

1.  By combining my answer to the initial recursion with the results of my arXiv note 1508.07523 I can show the following: Let K consist of those mod 2 modular forms of level Gamma_0 (3) that are killed by the maps f-->U_2(f) and f-->f+U_3(f). When one completes the shallow Hecke algebra acting on K at the maximal ideal generated by the T_p with p> 3, one gets a power series ring in T_7 and T_13.

2.  My answer to the variation on a theme question should lead to a similar result in level Gamma_0 (5), but I'd first need level 5 analogs to the results of the arXiv note, and this may not be entirely straightforward.

3.  Despite the lack of response to my answers (I don't think I'd have found the answers if I hadn't posted the questions here) I find them elegant. Since no elementary answers have been found, and in view of 1. , I'll accept my first.

4.  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.