1
$\begingroup$

Let $a(n)$ be A007306, denominators of Farey tree fractions (i.e., the Stern-Brocot subtree in the range $[0,1]$).

Let $b(n)$ be A002487, Stern's diatomic series (or Stern-Brocot sequence): $b(0) = 0, b(1) = 1$; for $n > 0$: $b(2n) = b(n), b(2n+1) = b(n) + b(n+1)$.

Also $$a(n)=b(2n-1)$$

I conjecture that to generate these sequences we can start with $a(1)=b(1)=1$ and then apply $$a(n)=a(n-1)+b(n-1)-2(a(n-1)\operatorname{mod} b(n-1))$$ $$b(n)=a(n)-b(n-1)$$

Is there a way to prove it?

$\endgroup$

1 Answer 1

3
$\begingroup$

The second half is already given in the question, so really what you're asking is whether $$b(2n-1)=b(2n-3)+b(n-1)-2(b(2n-3)\bmod b(n-1))$$ But as noted in OEIS (quoted with relabelling),

Moshe Newman proved that the fraction b(n+1)/b(n+2) can be generated from the previous fraction b(n)/b(n+1) = x by 1/(2*floor(x) + 1 - x).

Or, in other words, $$\begin{eqnarray*}\frac{b(n+2)}{b(n+1)} &=& 2\left\lfloor \frac{b(n)}{b(n+1)} \right\rfloor + 1 - \frac{b(n)}{b(n+1)} \\ &=& 2\frac{b(n) - b(n) \bmod b(n+1)}{b(n+1)} + 1 - \frac{b(n)}{b(n+1)} \end{eqnarray*}$$

So $$b(n+2) = b(n) - 2b(n) \bmod b(n+1) + b(n+1)$$ and substituting $n = 2m-3$ and applying $b(2n) = b(n)$ gets us there.

$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .