# A fun Pascal-like triangle

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.

-
This reminds me of the en.wikipedia.org/wiki/Stern-Brocot_tree –  John M Jul 27 '11 at 3:22
I really wish you'd use different delimiters; parentheses are so overloaded... –  Ｊ. Ｍ. Jul 27 '11 at 3:25
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? –  Srivatsan Jul 27 '11 at 3:51
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. –  anon Jul 27 '11 at 3:58
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}.$$ –  anon Jul 27 '11 at 4:37
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$