I found the bit count of Lucas sequence $U_n(x,1)$ over the field GF(2) is Stern's diatomic series, I want to know the reason?
https://oeis.org/A002487 : Stern's diatomic series
https://oeis.org/A168081 : Lucas sequence $U_n(x,1)$ over the field GF(2)
I always work mod 2. Let $f(n)$ be the bit count (number of nonzero coefficients) of $U_n(x,1)$. $U_n(x,1)$ satisfies $$ U_{2n}(x,1) = xU_n(x,1)^2 $$ $$ U_{2n+1}(x,1) = (U_n(x,1)+U_{n+1}(x,1))^2. $$ From the first equation $f(2n)=f(n)$, and only odd powers of $x$ can have nonzero coefficients. From the second equation, only even powers of $U_{2n+1}$ can have nonzero coefficients. Hence no cancellation occurs when we add $U_n(x,1)$ and $U_{n+1}(x,1)$, so $f(2n+1)=f(n)+f(2n+1)$. Thus $f(n)$ satisfies the same recurrence and same initial conditions $f(0)=0$ and $f(1)=1$ as Stern's diatomic sequence.
Addendum. The two formulas above can be proved by induction on $n$. Namely, writing just $U_n$ for $U_n(x,1)$, $$ U_{2n}=xU_{2n-1}+U_{2n-2} = x(U_{n-1}+U_n)^2+xU_{n-1}^2 =xU_n^2 $$ and $$ U_{2n+1} = xU_{2n}+U_{2n-1} = x^2U_n^2+(U_{n-1}+U_n)^2 =U_n^2+(xU_n+U_{n-1})^2=U_n^2+U_{n+1}^2. $$
