A characteristic 2 polynomial recursion

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