Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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.

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

1 Answer

up vote 19 down vote accepted

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$

share|improve this answer
    
Excellent proof! –  Bruno Joyal Jul 27 '11 at 6:05
    
Very nice! Thanks for your help. –  John M Jul 27 '11 at 6:07
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.