Computing a special case of a question by another user, I have noticed that apparently the OEIS A202349 sequence can be expressed as:
$$a(n)=\sum_{k=0}^{n}{\binom{n}{k}(2^k \bmod 7)} \tag{1}$$
This formula is not at OEIS, while there are there a recurrence for $n>2$:
$$a(n) = 3a(n-1) – 3a(n-2) + 2a(n-3) \tag{2}$$
and a generating function:
$$\frac{x(1 + 3x^2) }{ (1 – 2x)(1 – x + x^2)}. \tag{3}$$
The factor $2^k \bmod 7$, starting from $k=0$, is just $1,2,4,1,2,4,1,2,4,\ldots$
Any hint for proving that $(1)$ satisfies $(2)$ and/or has generating function $(3)$?
Best Answer
Sketch:
Write your $a_n$ as a weighted sum of sums of binomial coefficients. Thus: $$a_n=\sum_{k=0}^n \binom nk +\sum_{k\equiv 1 \pmod 3}^n\binom nk+\,\,3\times \sum_{k\equiv 2 \pmod 3}^n\binom nk$$
where it is understood that, in each sum, $k$ runs from $0$ to $n$, satisfying the desired congruence if one is specified.
The first sum is, of course, just $2^n$ and it is easily confirmed that this satisfies the desired recursion.
The other two sums also satisfy the desired recursion, see A024495 and A024494, which proves that your $a_n$ also satisfies the desired recursion.