Skip to main content
added 533 characters in body
Source Link
Peter Taylor
  • 7.2k
  • 1
  • 21
  • 29

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

Not a complete answer, but too long for a comment.

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

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

Source Link
Peter Taylor
  • 7.2k
  • 1
  • 21
  • 29

Not a complete answer, but too long for a comment.

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