0

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)$?

Fabius Wiesner
  • 2,573
  • 1
    Binomial transforms transform the generating functions along very simple substitutions, see e.g. equations (1) and (2) in https://dx.doi.org/10.1016/0024-3795(94)00245-9 . So obviously one gets https://oeis.org/A069705 in this case. – R. J. Mathar Aug 28 '23 at 11:22

1 Answers1

1

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.

lulu
  • 70,402