De Bruijn's sequence is odd iff $n=2^m-1$: Part I Among the families of sequences studied by Nicolaas de Bruijn (Asymptotic Methods in Analysis, 1958), let's focus on the (modified)
$$\hat{S}(4,n)=\frac1{n+1}\sum_{k=0}^{2n}(-1)^{n+k}\binom{2n}k^4.$$
An all-familiar fact states: the Catalan number $C_n=\frac1{n+1}\binom{2n}n$ is odd iff $n=2^m-1$. In the same tradition, I ask:

QUESTION. Is this true? $\hat{S}(4,n)$ is odd iff $n=2^m-1$ for some $m\in\mathbb{Z_{\geq0}}$.

POSTSCRIPT. This question has been extended to my other MO question.
 A: That's true. This follows easily from the formula
$$
\hat{S}(4,n)=\frac1{n+1}\binom{2n}n\sum_{k=0}^n (-1)^k\binom{2n+k}k^2\binom{2n}{n+k}.\quad\quad\quad\quad\quad(*)
$$
First of all, I prove your parity claim using $(*)$, and next prove $(*)$.
If $n+1$ is not a power of 2, then $C_n=\frac1{n+1}\binom{2n}n$ is even and so is RHS of $(*)$. If $n=2^m-1$, then $C_n$ is odd, the summand with $k=1$ in RHS of $(*)$ is odd and other summands are even: $\binom{2n+k}k=\frac{(2n+1)(2n+2)}{k(k-1)}\binom{2n+k}{k-2}$ is even for $k=2,3,\ldots,n$ since $k(k-1)$ is not divisible by $2^{m+1}=2n+2$.
Now the proof of $(*)$. For $C:=(-1)^n (n+1)\hat{S}(4,n)$ we have
$$C=[x^{2n}y^{2n}z^{2n}t^{2n}](x-y)^{2n}(y-z)^{2n}(z-t)^{2n}(x+t)^{2n}=[x^{2n}y^{2n}z^{2n}t^{2n}]F,$$
where $$F=\prod_{j=-(n-1)}^{n}(x-y-j)(z-y-j)(z-t-j)(x+t-2n-j).$$
Denote $A=\{0,1,\ldots,2n\}$ and express the coefficient $[x^{2n}y^{2n}z^{2n}t^{2n}]F$ via the values of $F$ on $A^4$ using this formula.
Look how $F(x,y,z,t)\ne 0$ may be possible when $x,y,z,t\in A$. We must have $|x-y|\geqslant n, |y-z|\geqslant n, |z-t|\geqslant n$ and $x-y\ne n$, $z-y\ne n$, $z-t\ne n$. If $y$ lies between $x$ and $z$, the conditions $|x-y|\geqslant n, |z-y|\geqslant n$ yield $y=n$, $\{x,z\}=\{0,n\}$, but then either $x-y$ or $z-y$ equals $n$; a contradiction. Analogously if $z$ lies between $y$ and $t$. Thus $x-y,z-y,z-t$ have equal sign. If they are positive, we get $2n\geqslant x\geqslant y+n+1\geqslant n+1$ and
$n-1\geqslant z-n-1\geqslant t\geqslant 0$, thus $x+t\in [n+1,3n-1]$ and therefore $F(x,y,z,t)=0$; a contradiction. So we must have $n\geqslant y-n\geqslant x\geqslant 0$,  $2n\geqslant t\geqslant z+n\geqslant n$ and $x+t\in [n,3n]$. Since $F(x,y,z,t)\ne 0$, we conclude that $x+t=n$, $x=0$, $t=n$, thus $z=0$ and $y\in [n,2n]$. Then the cited formula allows to rewrite $C$ as a sum over $y$ which simplifies as $(*)$.
A: I just wished to suggest an alternative (mechanical) proof whose details can be provided (using the WZ-method) for the identity
$$\sum_{k=0}^{2n}(-1)^{n+k}\binom{2n}k^4=\binom{2n}n\sum_{k=0}^n(-1)^k\binom{2n+k}k^2\binom{2n}{n+k}.\qquad \qquad (*)$$
The idea is: verify that both sides of $(*)$ satisfy the 2nd-order recurrence
\begin{align*}
A(n)a(n+2)- B(b)a(n+1) +C(n)a(n)=0 \end{align*}
with initial conditions $a(0)=1$ and $a(1)=14$; where
\begin{align*}
A(n)&=(2n + 3)(48n^2 + 66n + 23)(n + 2)^3 \\
B(n)&=13056n^6+ 96288n^5+ 289600n^4+ 453428n^3 + 388698n^2 + 172598n+31030 \\
C(n)&=4(n + 1)(48n^2 + 162n + 137)(2n + 1)^3. \end{align*}
