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

• 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)


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

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