Sequence derived from transform of a given vector (with Fibonacci as partial sums)

Question

• Let F_n be A000045 (i.e., Fibonacci numbers). Here

$$ F_n = F_{n-1} + F_{n-2}, \\ F_0 = 0, F_1 = 1 $$

• Let $\operatorname{wt}(n)$ be A000120 (i.e., number of ones in the binary expansion of $n$). Here

$$ \operatorname{wt}(2n+1)=\operatorname{wt}(n) + 1, \\ \operatorname{wt}(2n) = \operatorname{wt}(n), \\ \operatorname{wt}(0)=0 $$

Let $\nu_2(n)$ be A007814 (i.e., number of trailing zeros in the binary expansion of $n$). Here

$$ \nu_2(2n+1)=0, \\ \nu_2(2n) = \nu_2(n) + 1 $$

• Let $T(n,k)$ be an integer coefficients such that

$$ T(n,k) = [T(n,k-1)>0]\left\lfloor\frac{T(n,k-1)}{2^{\nu_2(T(n,k-1))+1}}\right\rfloor, \\ T(n,0) = n $$

• Let $b(n)$ be an integer sequence such that we start with a vector $\nu$ length $\operatorname{wt}(n)$ with elements $\nu_i = \operatorname{wt}(n) - i + 1$ and then for $i$ from $1$ to $\operatorname{wt}(n) - 1$ and for $j$ from $1$ to $\operatorname{wt}(n)-i$ consecutively apply

$$\nu_j = (\nu_2(T(n, i)) + 1)(\operatorname{wt}(n) - i - j + 1)(\nu_j - \nu_{j+1})$$

Then $b(n)=\nu_1$ after the whole transformation.

• Let $s(n)$ be an integer sequence such that

$$ s(n) = \sum\limits_{i=1}^{2^n}b(2^n + i - 1) $$

I conjecture that $$s(n)=F_{2n+1}.$$

Here is the PARI/GP program to check it numerically:

b(n) = my(A = n, B, C, v1, v2); v1 = []; while(A > 0, B = valuation(A, 2); v1 = concat(v1, B+1); A \= 2^(B+1)); A = #v1; v2 = vector(A, i, A - i + 1); for(i = 1, A-1, for(j=1, A-i, v2[j]=v1[i+1]*(A - i - j + 1)*(v2[j] - v2[j+1]))); v2[1]
s(n) = my(A = 1 << n); sum(i=1, A, b(A + i - 1))
test(n) = s(n) == fibonacci(2*n+1)

What do you think about

$$ R(n,k)=\sum\limits_{i=1}^{2^n}[b(2^n + i - 1)=k] $$

for $k$ fixed and $n$ variable?

Here square bracket denotes Iverson bracket.

Also $R(n,k)$ begins with

[2]
[3,   1]
[4,   3,  1]
[5,   6,  3,   2]
[6,  10,  6,   7,  1,   2]
[7,  15, 10,  16,  3,   9,  0,   3,  1]
[8,  21, 15,  30,  6,  23,  1,  13,  4,  2, 0,   5]
[9,  28, 21,  50, 10,  46,  3,  36, 10,  8, 0,  25, 0, 0,  2,  5, 0,  3]
[10, 36, 28,  77, 15,  80,  6,  78, 21, 20, 0,  73, 0, 2,  8, 25, 0, 17, 0,  5, 0, 0, 0, 10, 0, 0, 1]
[11, 45, 36, 112, 21, 127, 10, 146, 38, 41, 0, 165, 0, 8, 20, 78, 0, 53, 0, 23, 2, 0, 0, 59, 1, 0, 5, 0, 0, 6, 0, 8, 0, 0, 0, 9]

Is there a way to prove it? Is there a simple formula for $R(n,k)$?

Answer 1

Not a complete answer, but too long for a comment and addressing the conjecture which I take to be the most important part of the question.

The double-loop transformation process seems familiar to me from preliminary analysis of another of your questions which I didn't make enough progress with to answer, so I think it's worth at least addressing that it can be eliminated. I'm avoiding $\nu$ because $\nu_2$ means two different things in the question, so I shall focus instead on this reworded process:

We start with a vector $x$ length $\ell$ with elements $x_i = \ell - i + 1$ and then for $i$ from $1$ to $\ell - 1$ and for $j$ from $1$ to $\ell-i$ consecutively apply

$$x_j = a_i(\ell - i - j + 1)(x_j - x_{j+1})$$

After executing that process, $x_j = \prod_{m=1}^{\ell-j} a_m$. For clarity I'm going to add another index indicating how many times the outer loop has been executed.

Let $$x_{i,j} = \begin{cases} \ell-j+1 & \textrm{if } i = 0 \\ x_{i-1,j} & \textrm{if } j > \ell - i \\ a_i(\ell - i - j + 1)(x_{i-1,j} - x_{i-1,j+1}) & \textrm{otherwise} \end{cases}$$

Then we prove this stronger statement by induction on $i$:

Let $$y_{i,j} = \begin{cases} \prod_{m=1}^{\ell-j} a_m & \textrm{if } i + j > \ell \\ (\ell-i-j+1) \prod_{m=1}^i a_m & \textrm{otherwise} \end{cases}$$ Then $x_{i,j} = y_{i,j}$ for all $i, j \in [\ell]$.

When $i=0$ we have $x_{0,j} = y_{0,j} = \ell - j + 1$.

For the inductive step, we have three cases:

• $i + j > \ell + 1$. Then $x_{i,j} = x_{i-1,j}$ by definition, $x_{i-1,j} = y_{i-1,j}$ by inductive hypothesis, and both $y_{i,j}$ and $y_{i-1,j}$ are $\prod_{m=1}^{\ell-j} a_m$ by the first case of the definition of $y$.
• $i + j = \ell + 1$. Then $x_{i,j} = x_{i-1,j}$ by definition, $x_{i-1,j} = y_{i-1,j}$ by inductive hypothesis, and $y_{i-1,j} = (\ell-(i-1)-j+1) \prod_{m=1}^{i-1} a_m$ by the second case of the definition of $y$. Substituting $i-1 = \ell - j$ we get $y_{i-1,j} = \prod_{m=1}^{\ell - j} a_m$. On the other hand, $y_{i,j} = \prod_{m=1}^{\ell-j} a_m$ by the first case of the definition of $y$.
• $i + j \le \ell$. Then $$\begin{eqnarray*}x_{i,j} &=& a_i(\ell - i - j + 1)(x_{i-1,j} - x_{i-1,j+1}) \\ &=& a_i(\ell - i - j + 1)(y_{i-1,j} - y_{i-1,j+1}) \\ &=& a_i(\ell - i - j + 1)((\ell-(i-1)-j+1) \prod_{m=1}^{i-1} a_m - (\ell-(i-1)-(j+1)+1) \prod_{m=1}^{i-1} a_m) \\ &=& (\ell - i - j + 1)\prod_{m=1}^i a_m \\ &=& y_{i,j} \end{eqnarray*}$$

---

Thus $b(n)$ in the question can be expressed as $$b(n) = \prod_{i=1}^{\operatorname{wt}(n)-1} (\nu_2(T(n, i)) + 1)$$

Therefore $s(n)$ is effectively summing over all compositions of numbers $m = 0$ to $n$ the product of the elements of the composition, and the conjecture follows from the following observation in OEIS:

Sum of the products of the elements in the compositions of n (example for n=3: the compositions are 1+1+1, 1+2, 2+1, and 3; a(3) = 1*1*1 + 1*2 + 2*1 + 3 = 8). - Dylon Hamilton, Jun 20 2010, Geoffrey Critzer, Joerg Arndt, Dec 06 2010