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?

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

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)$.


[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.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.