32
$\begingroup$

Inspired by Pascal, I put on some shackles and a thorny belt. Inspiration came pouring in, and I thought of the following triangle:

$$ \begin{array}{rcccccccccc} & & & & & 1\\\ & & & & 1 & & 1\\\ & & & 1 & & \frac{1}{2} & & 1\\\ & & 1 & & \frac{2}{3} & & \frac{2}{3} & & 1\\\ & 1 & & \frac{3}{5} & & \frac{3}{4} & & \frac{3}{5} & & 1\\\ 1 & & \frac{5}{8} & & \frac{20}{27} & & \frac{20}{27} & & \frac{5}{8} & & 1\\\ & ... & & & &... & & & & ... & \end{array} $$

Let's call the corresponding entry ${n \choose k}$ because there is clearly no danger of confusion. The construction rule is very simple. Instead of having $${n+1 \choose k} = {n \choose k-1} + {n \choose k},$$ as usual, we have $${n+1 \choose k} = \frac{1}{{n \choose k-1} + {n \choose k}}.$$

It's easy to see by induction that all entries of the triangle lie between $1/2$ and $1$. Also, for fixed $k$, ${n \choose k}$ converges to a limit $C_k$. For example, $C_1=1/\phi$, where $\phi$ is the golden ratio (this should be obvious! think of Fibonacci numbers...). We can determine easily $C_{k+1}$ in terms of $C_k$ by taking the limit in the construction rule, which yields $C_k=(C_{k-1}+C_k)^{-1}$. In particular, all of the $C_k$'s are algebraic numbers.

I would like to know if anybody here can prove interesting properties of this triangle, or of the numbers $C_k$.

Enjoy! I'm going to take off the shackles and belt now.

  • 6
    This reminds me of the http://en.wikipedia.org/wiki/Stern-Brocot_tree2011-07-27
  • 6
    I really wish you'd use different delimiters; parentheses are *so* overloaded...2011-07-27
  • 2
    I presume such a recurrence cannot be easily "solved". I tried to at least show that $C_k$ converges to a limit as $k \to \infty$. (The conjectured limit can be shown to be $1/\sqrt{2} = 0.707$ easily.) I couldn't; any help?2011-07-27
  • 1
    I agree with @Srivatsan; if for instance you look at the Stirling cycle numbers, the recursion relation is simple, but obtaining something "simpler" from that looks very unlikely.2011-07-27
  • 0
    Thank you Srivatsan. Have you tried taking the limit in the expression $C_k=(C_{k-1}+C_k)^{-1}$ ? (I presume that's what John did below.) I agree that there is probably no "easy" formula for the $C_k$'s, but there could still be many things to be said.2011-07-27
  • 3
    I wonder - if you plot the elements of row $n$, as $n\to\infty$, what distribution in $(1/2,1)$ the points might converge to.2011-07-27
  • 0
    That's a great question, anon. If I had better coding skills than I do, I would write up a quick program to check.2011-07-27
  • 1
    I think it would be worth checking out the continued fraction expansion of the $C_k$'s, too.2011-07-27
  • 0
    (Man, this is fun!) Bruno, I did take the limit in the recurrence for $C_k$. The only difficulty is that the limit need not exist :); if it exists, it is $1/\sqrt{2}$. I definitely think one can say many things about $C_k$, and doing so without a nice formula is, in fact, a bit of challenge.2011-07-27
  • 0
    If it's related to the Stern-Brocot tree, then what happened to the rationals less than $1/2$? Is this somehow only one half of the tree? Side question: does every rational in the $(.5, 1)$ range appear somewhere in the triangle?2011-07-27
  • 1
    @Bruno: You can see the CF expansion of $C_2$ [here](http://www.wolframalpha.com/input/?i=%28%281-Sqrt%5B5%5D%29%2F2%2BSqrt%5B%2811-Sqrt%5B5%5D%29%2F2%5D%29%2F2). Lots of $1$'s but otherwise I don't see anything. Srivatsan: Well $C_1$ exists, which probably can be used to show $C_2$ exists, and so on.2011-07-27
  • 1
    Actually should we prove that $n \choose k$ really has a limit as $n \rightarrow \infty$? That sequence is *not* monotonic!2011-07-27
  • 0
    @anon I meant to ask the limit of $C_k$ for large $k$ (I guess I am already assuming each $C_k$ exists). John has answered it now. Sorry if that wasn't clear. Bruno, $1/3$ is not in the range. But in any case, I doubt that all rationals will appear in the triangle.2011-07-27
  • 0
    @Srivatsan: Haha, indeed 1/3 < 1/2. Anyways, what I meant is just that the complexity of these fractions seems to grow too fast for all of them to be included eventually.2011-07-27
  • 0
    @John: Indeed, I swept that under the rug, didn't I?2011-07-27
  • 3
    I have a conjecture with notebook-empirical support. Let $D^n_k$ denote the Bruno coefficients, while $C^n_k$ are the binomial coefficients. Then: $$ \sum_{k=1}^n C^n_k D^n_k \sim 2^{n-1/2}.$$2011-07-27
  • 0
    @anon Let me write your conjecture as $\sum_{k} C^n_k \frac{D^n_k}{2^n} ~ 1/\sqrt{2}$. I wonder if this would follow from the fact that $C^n_k \to C_k$ for large $n$, and $C_k \to 1/\sqrt{2}$ for large $k$. Note that the binomial distribution $D^n_k/2^n$ puts exponentially small weight on the "small" values of $k$, so we can effectively ignore these initial terms.2011-07-27

1 Answers 1

20

The sequence $C_k$ is not monotonic as @JohnM originally claimed. Here's a quick but not so elegant proof of convergence of $C_k$. As a side effect, we'll also know that the sequence goes alternately above and below its limit, namely $1/\sqrt{2}$.

Solving for $C_{k+1}$ in terms of $C_k$, we get $C_{k+1} = \frac{\sqrt{C_k^2 + 4} - C_k}{2}$. I'll directly show that the difference sequence $|C_{k}-\frac{1}{\sqrt{2}}|$ is decreasing exponentially fast, which establishes the required convergence. I'll abbreviate $C_k$ by $c$ for convenience. We have: $$ \frac{C_{k+1} - \frac{1}{\sqrt{2}}}{C_{k} - \frac{1}{\sqrt{2}}} = \frac{\sqrt{c^2+4} - (c + \sqrt{2})}{2 (c - \frac{1}{\sqrt{2}})} = \frac{-\sqrt{2}}{\sqrt{c^2+4} + c + \sqrt{2}}, $$ after some straightforward rearrangement. (Notice the minus sign.) Finally, notice that the denominator is at least $2+\sqrt{2} \geq 2\sqrt{2}$ for $c \geq 0$. Hence the ratio is at most $1/2$ in magnitude. In particular, we have $|C_k - \frac{1}{\sqrt{2}}| \leq A 2^{-k}$ for some constant $A$, and we are done. The negative sign shows that the sequence is alternately above and below the limit. $\Box$

  • 0
    Excellent proof!2011-07-27
  • 0
    Very nice! Thanks for your help.2011-07-27