Skip to main content
added 36 characters in body
Source Link
Pietro Majer
  • 60.5k
  • 4
  • 122
  • 269

Given the structure of these sequences, it seems convenient to describe them as integer valued functions of binary strings rather than of natural numbers. This way, the recursions from $b$ and $c$ appear to be recursive ways of computing a quantity of a string $x$, starting from the left, resp. from the right.

Specifically, for a binary string $x:=x_r\dots x_1x_0$ of finite length $r>0$ and $m=\sum_{i=0}^rx_i2^i$, we write $f(x)$ instead of $f(m)$ for $f\in\{a,b,c\}.$ Then the recursionrecursions translate into: $$ a(x00)=a(x01)=a(x0) ,\\ a(x10)=a(x)+1,\\ a(x11)=a(x)=a(0x),\\ a(0)=0; $$

$$ b(1x)=\big(1+a(1x)\big)b(x),\\ b(0)=1. $$

In the recursionequations for $c$, it is convenient to write $$2^{2m+1}(2k+1)+\frac23(4^{m+1}-1)=$$$$=2^{2m+2}(k+1)+\frac23(4^m-1),$$ and $$2^{2m+1}k+\frac23(4^{m+1}-1)=$$$$= 2^{2m+1}(k+1)+\frac23(4^m-1),$$ so that there is nothing to be carried in the binary representation of the sum. Thus

$$ c((10)^n)=(n+1)!,\\ c(x1(10)^n)=(n+1)c(x(10)^n),\\ c(x00(10)^n)=c(x0(10)^n),\\ c(0)=1. $$ Finally, we may add to these $f(0x)=f(x)$ for $f\in\{a,b,c\},$ since the value of $f(x)$ only depends on the numerical value of the string.

Note that $a(x11)=a(x)$ and $a(x01)=a(x0)$ together imply $a(x1^{2p})=a(x)$ and $a(x01^{2p+1})=a(x0)$, so that in the argument of $a$, every initial block of $1$’s on the right can be removed, and in particular $a(x1)=a(x)$.

The analogous relation $b(x1)=b(x)$ then follows by induction, since it is true for $x=0$. Also, $c(x1)=c(x)$ for $c$ is a particular case of the second equation for $c$, with $n=0$. Therefore for the sake of notation we may and do prove the equality $b(x)=c(x)$ for binary strings of odd numbers.

Every such string $x$ (after dropping initial $0$’s from the left), can be written uniquely as $$x=1^{p_n}0^{q_n}\dots 1^{p_1}0^{q_1}1^{p_0},$$ with $n\ge1$ and positive integer exponents $q_i,$ $p_i$.

In this notation, $a(x)=n$, the number of blocks of $0$’s. It then immediately follows by induction that

$$ b(1^{p_n}0^{q_n}\dots 1^{p_1}0^{q_1}1^{p_0})=\prod_{i=1}^n(1+i)^{p_i}.$$

Using the relations for $c$, we can reduce the computation of $c(x)$ to the known value $c((10)^n)=(n+1)!$, extracting in order from the right to the left $p_i-1$ of the(i.e. for $i$ from $0$ to $n$) all $0$’s but one from the block $0^{p_i}$, with no effect on the value of $c$, and $q_i-1$ of theall $1$’s but one from the block $1^{q_i}$, withmultiplying by a factor $(1+i)^{p_i}$. In conclusion $$ c(1^{p_n}0^{q_n}\dots 1^{p_1}0^{q_1}1^{p_0})=\prod_{i=1}^n(1+i)^{p_i},$$ as we wished to prove.

Given the structure of these sequences, it seems convenient to describe them as integer valued functions of binary strings rather than of natural numbers. This way, the recursions from $b$ and $c$ appear to be recursive ways of computing a quantity of a string $x$, starting from the left, resp. from the right.

Specifically, for a binary string $x:=x_r\dots x_1x_0$ of finite length $r>0$ and $m=\sum_{i=0}^rx_i2^i$, we write $f(x)$ instead of $f(m)$ for $f\in\{a,b,c\}.$ Then the recursion translate into: $$ a(x00)=a(x01)=a(x0) ,\\ a(x10)=a(x)+1,\\ a(x11)=a(x)=a(0x),\\ a(0)=0; $$

$$ b(1x)=\big(1+a(1x)\big)b(x),\\ b(0)=1. $$

In the recursion for $c$, it is convenient to write $$2^{2m+1}(2k+1)+\frac23(4^{m+1}-1)=$$$$=2^{2m+2}(k+1)+\frac23(4^m-1),$$ and $$2^{2m+1}k+\frac23(4^{m+1}-1)=$$$$= 2^{2m+1}(k+1)+\frac23(4^m-1),$$ so that there is nothing to be carried in the binary representation of the sum. Thus

$$ c((10)^n)=(n+1)!,\\ c(x1(10)^n)=(n+1)c(x(10)^n),\\ c(x00(10)^n)=c(x0(10)^n),\\ c(0)=1. $$ Finally, we may add to these $f(0x)=f(x)$ for $f\in\{a,b,c\},$ since the value of $f(x)$ only depends on the numerical value of the string.

Note that $a(x11)=a(x)$ and $a(x01)=a(x0)$ together imply $a(x1^{2p})=a(x)$ and $a(x01^{2p+1})=a(x0)$, so that in the argument of $a$, every initial block of $1$’s on the right can be removed, and in particular $a(x1)=a(x)$.

The analogous relation $b(x1)=b(x)$ then follows by induction, since it is true for $x=0$. Also, $c(x1)=c(x)$ for $c$ is a particular case of the second equation for $c$, with $n=0$. Therefore for the sake of notation we may and do prove the equality $b(x)=c(x)$ for binary strings of odd numbers.

Every such string $x$ (after dropping initial $0$’s from the left), can be written uniquely as $$x=1^{p_n}0^{q_n}\dots 1^{p_1}0^{q_1}1^{p_0},$$ with $n\ge1$ and positive integer exponents $q_i,$ $p_i$.

In this notation, $a(x)=n$, the number of blocks of $0$’s. It then immediately follows by induction that

$$ b(1^{p_n}0^{q_n}\dots 1^{p_1}0^{q_1}1^{p_0})=\prod_{i=1}^n(1+i)^{p_i}.$$

Using the relations for $c$, we can reduce the computation of $c(x)$ to the known value $c((10)^n)=(n+1)!$, extracting in order from the right to the left $p_i-1$ of the $0$’s from the block $0^{p_i}$, with no effect on the value of $c$, and $q_i-1$ of the $1$’s from the block $1^{q_i}$, with a factor $(1+i)^{p_i}$. In conclusion $$ c(1^{p_n}0^{q_n}\dots 1^{p_1}0^{q_1}1^{p_0})=\prod_{i=1}^n(1+i)^{p_i},$$ as we wished to prove.

Given the structure of these sequences, it seems convenient to describe them as integer valued functions of binary strings rather than of natural numbers. This way, the recursions from $b$ and $c$ appear to be recursive ways of computing a quantity of a string $x$, starting from the left, resp. from the right.

Specifically, for a binary string $x:=x_r\dots x_1x_0$ of finite length $r>0$ and $m=\sum_{i=0}^rx_i2^i$, we write $f(x)$ instead of $f(m)$ for $f\in\{a,b,c\}.$ Then the recursions translate into: $$ a(x00)=a(x01)=a(x0) ,\\ a(x10)=a(x)+1,\\ a(x11)=a(x)=a(0x),\\ a(0)=0; $$

$$ b(1x)=\big(1+a(1x)\big)b(x),\\ b(0)=1. $$

In the equations for $c$, it is convenient to write $$2^{2m+1}(2k+1)+\frac23(4^{m+1}-1)=$$$$=2^{2m+2}(k+1)+\frac23(4^m-1),$$ and $$2^{2m+1}k+\frac23(4^{m+1}-1)=$$$$= 2^{2m+1}(k+1)+\frac23(4^m-1),$$ so that there is nothing to be carried in the binary representation of the sum. Thus

$$ c((10)^n)=(n+1)!,\\ c(x1(10)^n)=(n+1)c(x(10)^n),\\ c(x00(10)^n)=c(x0(10)^n),\\ c(0)=1. $$ Finally, we may add to these $f(0x)=f(x)$ for $f\in\{a,b,c\},$ since the value of $f(x)$ only depends on the numerical value of the string.

Note that $a(x11)=a(x)$ and $a(x01)=a(x0)$ together imply $a(x1^{2p})=a(x)$ and $a(x01^{2p+1})=a(x0)$, so that in the argument of $a$, every initial block of $1$’s on the right can be removed, and in particular $a(x1)=a(x)$.

The analogous relation $b(x1)=b(x)$ then follows by induction, since it is true for $x=0$. Also, $c(x1)=c(x)$ for $c$ is a particular case of the second equation for $c$, with $n=0$. Therefore for the sake of notation we may and do prove the equality $b(x)=c(x)$ for binary strings of odd numbers.

Every such string $x$ (after dropping initial $0$’s from the left), can be written uniquely as $$x=1^{p_n}0^{q_n}\dots 1^{p_1}0^{q_1}1^{p_0},$$ with $n\ge1$ and positive integer exponents $q_i,$ $p_i$.

In this notation, $a(x)=n$, the number of blocks of $0$’s. It then immediately follows by induction that

$$ b(1^{p_n}0^{q_n}\dots 1^{p_1}0^{q_1}1^{p_0})=\prod_{i=1}^n(1+i)^{p_i}.$$

Using the relations for $c$, we can reduce the computation of $c(x)$ to the known value $c((10)^n)=(n+1)!$, extracting in order from the right to the left (i.e. for $i$ from $0$ to $n$) all $0$’s but one from the block $0^{p_i}$, with no effect on the value of $c$, and all $1$’s but one from the block $1^{q_i}$, multiplying by a factor $(1+i)^{p_i}$. In conclusion $$ c(1^{p_n}0^{q_n}\dots 1^{p_1}0^{q_1}1^{p_0})=\prod_{i=1}^n(1+i)^{p_i},$$ as we wished to prove.

Source Link
Pietro Majer
  • 60.5k
  • 4
  • 122
  • 269

Given the structure of these sequences, it seems convenient to describe them as integer valued functions of binary strings rather than of natural numbers. This way, the recursions from $b$ and $c$ appear to be recursive ways of computing a quantity of a string $x$, starting from the left, resp. from the right.

Specifically, for a binary string $x:=x_r\dots x_1x_0$ of finite length $r>0$ and $m=\sum_{i=0}^rx_i2^i$, we write $f(x)$ instead of $f(m)$ for $f\in\{a,b,c\}.$ Then the recursion translate into: $$ a(x00)=a(x01)=a(x0) ,\\ a(x10)=a(x)+1,\\ a(x11)=a(x)=a(0x),\\ a(0)=0; $$

$$ b(1x)=\big(1+a(1x)\big)b(x),\\ b(0)=1. $$

In the recursion for $c$, it is convenient to write $$2^{2m+1}(2k+1)+\frac23(4^{m+1}-1)=$$$$=2^{2m+2}(k+1)+\frac23(4^m-1),$$ and $$2^{2m+1}k+\frac23(4^{m+1}-1)=$$$$= 2^{2m+1}(k+1)+\frac23(4^m-1),$$ so that there is nothing to be carried in the binary representation of the sum. Thus

$$ c((10)^n)=(n+1)!,\\ c(x1(10)^n)=(n+1)c(x(10)^n),\\ c(x00(10)^n)=c(x0(10)^n),\\ c(0)=1. $$ Finally, we may add to these $f(0x)=f(x)$ for $f\in\{a,b,c\},$ since the value of $f(x)$ only depends on the numerical value of the string.

Note that $a(x11)=a(x)$ and $a(x01)=a(x0)$ together imply $a(x1^{2p})=a(x)$ and $a(x01^{2p+1})=a(x0)$, so that in the argument of $a$, every initial block of $1$’s on the right can be removed, and in particular $a(x1)=a(x)$.

The analogous relation $b(x1)=b(x)$ then follows by induction, since it is true for $x=0$. Also, $c(x1)=c(x)$ for $c$ is a particular case of the second equation for $c$, with $n=0$. Therefore for the sake of notation we may and do prove the equality $b(x)=c(x)$ for binary strings of odd numbers.

Every such string $x$ (after dropping initial $0$’s from the left), can be written uniquely as $$x=1^{p_n}0^{q_n}\dots 1^{p_1}0^{q_1}1^{p_0},$$ with $n\ge1$ and positive integer exponents $q_i,$ $p_i$.

In this notation, $a(x)=n$, the number of blocks of $0$’s. It then immediately follows by induction that

$$ b(1^{p_n}0^{q_n}\dots 1^{p_1}0^{q_1}1^{p_0})=\prod_{i=1}^n(1+i)^{p_i}.$$

Using the relations for $c$, we can reduce the computation of $c(x)$ to the known value $c((10)^n)=(n+1)!$, extracting in order from the right to the left $p_i-1$ of the $0$’s from the block $0^{p_i}$, with no effect on the value of $c$, and $q_i-1$ of the $1$’s from the block $1^{q_i}$, with a factor $(1+i)^{p_i}$. In conclusion $$ c(1^{p_n}0^{q_n}\dots 1^{p_1}0^{q_1}1^{p_0})=\prod_{i=1}^n(1+i)^{p_i},$$ as we wished to prove.