# Binary recurrence from general recurrence

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?

• Please explain what these sequences are, beyond a reference to their OEIS numbers. Jun 9 '21 at 13:06
• @SamHopkins, done. Jun 9 '21 at 13:33

## 1 Answer

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 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) and it is given that $$b(2m+1)=b(m)$$. Hence, proved by induction.