2
$\begingroup$

Could you give me a hint how to find $c$ in the asymptotic for the sum: $ \sum_{k=0}^{\lfloor {n}/{2} \rfloor}\binom{n-k+1}{k}=(c+o(1))^n $ and for $ \max\limits_{a\leq n/2}\frac{\binom{n}{a}}{\sum_{k=0}^{a/2}\binom{n}{k}}=(c+o(1))^n $

1 Answers 1

2

HINT for the first problem: Note that $F_{n+1}=\sum_{k=0}^{\lceil n/2\rceil}\binom{n+1-k}k\;,$ where $F_n$ is the $n$-th Fibonacci number. (This can be proved without too much trouble by induction on $n$. Thus,

$\sum_{k=0}^{\lfloor n/2\rfloor}\binom{n-k+1}k=\begin{cases} F_{n+1},&\text{if }n\text{ is even}\\ F_{n+1}-\binom{(n+1)/2}{(n+1)/2}=F_{n+1}-1,&\text{if }n\text{ is odd}\;. \end{cases}$

You probably already know something about the asymptotics of the Fibonacci numbers.

For the second question see this answer.

  • 0
    @WickedSpirit: I’m not really the one to ask, I’m afraid: I’ve done very little along these lines. I just happened to recognize the first sequence as being very close to a standard identity involving binomial coefficients and Fibonacci numbers. By the way, I don’t know whether it will help, but the denominator in the other one simplifies to $\binom{n+1}{(a/2)+1}$ by another standard identity.2012-10-28