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.

  • 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
    Very nice! Thanks for your help.2011-07-27