Let $f(n)$ be A053645, distance to largest power of $2$ less than or equal to $n$; write $n$ in binary, change the first digit to zero, and convert back to decimal.

Let $g(n)$ be A007814, the exponent of the highest power of $2$ dividing $n$, a.k.a. the binary carry sequence, the ruler sequence, or the $2$-adic valuation of $n$.

Then we have a pair of an integer sequences given by \begin{align} a_1(0)=a_1(1)&=1\\ a_1(2n)& = a_1(n)+a_1(2n-2^{g(n)})\\ a_1(2n+1) &= a_1(2f(n)) \end{align} and \begin{align} a_2(0)=a_2(1)&=1\\ a_2(2n)& = a_2(n)+a_2(n-2^{g(n)})+a_2(2n-2^{g(n)})\\ a_2(2n+1) &= a_2(2f(n)) \end{align} Let $$s_k(n)=\sum\limits_{j=0}^{2^n-1}a_k(j)$$ then I conjecture that $$s_1(n)=1 + \sum\limits_{i=0}^{n} i(i+1)^{n-i}$$ and $$s_2(n)=(n+1)s_2(n-1)-(n-2)s_2(n-2), s_2(0)=1, s_2(1)=2$$ where $s_1(n)$ is A047970 and $s_2(n)$ is A006183.

Is there a way to prove it?

Similar questions:


1 Answer 1


As proved in this answer, for $n=2^tk$ with $2\nmid k$, we have $$a_1(n)=\sum_{i=0}^t \binom{t}{i} a_1(2^i(k-1)+1).$$

Then for $n=2^{t_1}(1+2^{t_2}(1+\dots(1+2^{t_m}))\dots)$ with $t_1\geq 0$ and $t_j\geq 1$ for $j\geq 2$, we have \begin{split} a_1(n) &= \sum_{i_1=0}^{t_1} \binom{t_1}{i_1} \sum_{i_2=0}^{t_2+i_1} \binom{t_2+i_1}{i_2} \sum_{i_3=0}^{t_3+i_2} \dots \sum_{i_\ell=0}^{t_\ell+i_{\ell-1}} \binom{t_\ell+i_{\ell-1}}{i_\ell} \\ &=\prod_{j=1}^\ell (\ell+2-j)^{t_j}, \end{split} where $\ell := \lfloor (m+1)/2\rfloor$.

Correspondingly, \begin{split} s_1(n) &= \sum_{m=0}^{n} \sum_{t_1+t_2+\dots+t_{m}\leq n-1}\ \prod_{j=1}^\ell (\ell+2-j)^{t_j}\\ &= \sum_{m=0}^n\ \sum_{t_1+t_2+\dots+t_{m}+t_{m+1} = n}\ \prod_{j=1}^{\ell+1} (\ell+2-j)^{t_j}\\ &=\sum_{m=0}^n [x^{n-m}]\ \ell! \left(\frac{1}{1-x}\right)^{m-\ell}\prod_{j=1}^{\ell+1} \frac1{1-jx} \\ &=\sum_{m=0}^n [x^{n-m}]\ \ell! \left(\frac{1}{1-x}\right)^{m-\ell}\sum_{q\geq \ell+1} S(q,\ell+1) x^{q-\ell-1}\\ &=\sum_{m=0}^n \ell! \sum_{q\geq l+1} S(q,\ell+1) \binom{n-q}{n-q-m+\ell+1}. \end{split}

Then grouping terms $m=2\ell-1$ and $2\ell$ we have \begin{split} s_1(n)&=\sum_{\ell\geq 0} \ell! \sum_{q\geq l+1} S(q,\ell+1) \binom{n-q+1}{n-q-\ell+2} \\ &=1 + \sum_{\ell\geq 0} \ell \sum_{q= l+1}^{n+1} S(q,\ell+1) (n-q+1)_{l-1}\\ &=1 + \sum_{q=1}^{n+1} \sum_{\ell\geq 0} \ell S(q,\ell+1) (n-q+1)_{l-1}\\ &=1 + \sum_{q=1}^{n+1} \sum_{\ell\geq 0} (S(q+1,\ell+1) - S(q,\ell+1) - S(q,\ell)) (n-q+1)_{l-1} \\ &=1 + \sum_{q=1}^{n+1} \left(\frac{(n-q+3)^q}{n-q+2} - \frac{(n-q+3)^{q-1}}{n-q+2} - (n-q+2)^{q-1}\right) \\ &=1 + \sum_{q=1}^{n+1} \left((n-q+3)^{q-1} - (n-q+2)^{q-1}\right) \\ &=1 + \sum_{i=0}^{n} i(i+1)^{n-i}. \end{split}

$s_2(n)$ can be treated similarly.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

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