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