Binary recurrence from general recurrence

Question

We have general recurrence for A243499 (which is product of parts of integer partitions as enumerated in the table A125106) $$a(n)=(1+b(n))a(t(n)), a(0)=1$$ where $b(n)$ is A023416 (which is number of 0's in binary expansion of n) $$b(2n+1)=b(n), b(2n)=b(n)+1, b(0)=1, b(1)=0$$ and $t(n)$ is A053645 (which is distance to largest power of 2 less than or equal to n) $$t(n)=n-2^{\left\lfloor\log_2{n}\right\rfloor}$$ There exist binary recurrence $$a(2n+1)=a(n), a(2n)=a(n-2^{f(n)})+a(2n-2^{f(n)}), a(0)=1$$ where $f(n)$ is A007814 (which is exponent of highest power of 2 dividing n) $$f(2n+1)=0, f(2n)=f(n)+1$$ Is there proof of binary recurrence from general recurrence?

Answer 1

Let, $n=2^{r_m}+2^{r_{m-1}}+....+2^{r_1}$. Then using the given equation $a(n)=(1+b(n))a(t(n))$ we get the following representation for $a(n)$.

$a(n)=(r_m+2-m)(r_{m-1}+3-m)....(r_1+m+1-m)$.....$(1)$

[It can be seen that $t(n)=2^{r_{m-1}}+....+2^{r_1}$]

So, $$a(2n)=(r_m+3-m)(r_{m-1}+4-m)...(r_1+m+2-m)$$

Now, $n-2^{f(n)}=2^{r_m}+2^{r_{m-1}}+.....+2^{r_2}$ and $2n-2^{f(n)}=2^{r_m+1}+2^{r_{m-1}+1}+....2^{r_2+1}+2^{r_1}$, as $f(n)=r_1$.

Using $(1)$, we get $$a(n-2^{f(n)})=(r_m+3-m)(r_{m-1}+4-m)...(r_2+m+1-m)$$ ...(2) as here are $(m-1)$ $1$s

And, $$a(2n-2^{f(n)})=(r_m+3-m)(r_{m-1}+4-m)...(r_2+m+1-m)(r_1+m+1-m)$$...(3)

Adding (2) and (3) we get that $$a(n-2^{f(n)})+a(2n-2^{f(n)})=(r_m+3-m)(r_{m-1}+4-m)...(r_1+m+2-m)=a(2n)$$

While the relation $a(2n+1)=a(n)$ can be proved using induction as follows. Let, for all $n<m$ this happens. Then, $a(2m+1)=(1+b(2m+1))a(t(2m+1))$.

Now, $t(2n+1)=2t(n)+1 \rightarrow a(t(2n+1))=a(2t(n)+1)=a(t(n))$ as $t(n)<n$ and it is given that $b(2m+1)=b(m)$. Hence, proved by induction.