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)



How to prove the relationship between Stern's diatomic series and 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. $$


