Let $m \in \mathbb{R}$.


Let $f(n)$ be [A007814](https://oeis.org/A007814), exponent of highest power of $2$ dividing $n$, a.k.a. the binary carry sequence, the ruler sequence, or the $2$-adic valuation of $n$.


Let $g(n)$ be [A129760](https://oeis.org/A129760), bitwise $\operatorname{AND}$ of binary representation of $n-1$ and $n$. Here
$$g(n) = n - 2^f(n)$$


Then we have a sequence


$$a(n) = \sum\limits\_{j=0}^{n}(\binom{n}{j}\operatorname{mod} 2)m^j$$


I conjecture that for $n>0$


$$a(n)=(m^{2^{f(n)}}+1)a(g(n))$$


Is there a way to prove it?



Modulo $2$ binomial transform of $m^n$
If $n\in \mathbb N$ has binary expansion $n=\sum\_{k\in S}2^k$ for a finite subset $S\subset \mathbb N$, then
$$ \sum\_{j=0}^n\Big[\big( {n \atop j}\big)\text{mod}\, 2 \Big]x^jy^{n-j}=\prod\_{k\in S} (x^{2^k}+y^{2^k})$$


More generally, but not needed here (see below): for sums of $r$ indeterminates $x\_i$, the binary coefficient homogeneous polynomial obtained as expansion of $\Big( \sum\_{i=1}^r x\_i\Big)^n$ with coefficients reduced $\text{mod}\,2$ has the factorisation (in $\mathbb Z[x\_1,\dots,x\_r]$)  

$$ \sum\_{\alpha\in\mathbb N^r,\, |\alpha|=n}\Big[\big( {n \atop \alpha }\big)\text{mod}\,2 \Big]x^\alpha=\prod\_{k\in S} \sum\_{i=1}^r x\_i^{2^k}. $$


In particular (for $x=1$ and $y=m$) by definition of $f$ and $g$, this implies immediately the relation $a(n)=(1+m^{2^f})a(g(n))$, just because $f\in S$ and $\{2^k\}\_{ k\in S\setminus\{f\}}$ are the powers of the binary expansion of $n-2^f$.


**Details** on the above factorization: immediately by induction on $k$ we have $$\Big( \sum\_{i=1}^r x\_i\Big)^{2^k}= \sum\_{i=1}^r x\_i^{2^k}\text{mod}\,2.$$ Then,
from $n=\sum\_{k\in S}2^k$ one has
$$\Big( \sum\_{i=1}^r x\_i\Big)^n=\Big( \sum\_{i=1}^r x\_i\Big)^{\sum\_{k\in S}2^k}= \prod\_{k\in S} \Big( \sum\_{i=1}^r x\_i\Big)^{2^k} = \prod\_{k\in S} \Big( \sum\_{i=1}^r x\_i^{2^k}\Big) \,\text{mod}\,2.$$


On the other hand, again by induction (on $|S|$) if we do the expansion $$\prod\_{k\in S}\sum\_{i\in [r]}c(k,i)=\sum\_{\iota\in [r]^S}\prod\_{k\in S}c(k,\iota(k))$$ for $\prod\_{k\in S} \Big( \sum\_{i=1}^r x\_i^{2^k}\Big)$, we see that all the $r^{|S|}$ terms of the expansion are different from each other, so that it is a $\{0,1\}$-coefficient polynomial, namely $\displaystyle \sum\_{\alpha\in\mathbb N^r,\, |\alpha|=n}\Big[\big( {n \atop \alpha }\big)\text{mod}\,2 \Big]x^\alpha$.


**Notation:** As usual, for $x=(x\_1,\dots,x\_r)\in \mathbb R^r$ and $\alpha=(\alpha\_1,\dots,\alpha\_r)\in \mathbb N^r$ we denote $x^\alpha:=x\_1^{\alpha\_1}\cdots x\_r^{\alpha\_r}$, $|\alpha|:=\alpha\_1+\dots+\alpha\_r$, and $\big({|\alpha| \atop \alpha }\big):=\frac{|\alpha|!}{\alpha\_1!\cdots\alpha\_r!}$.


