# Asymptotics for sum of binomial coefficients

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$$

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}$$
• @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. – Brian M. Scott Oct 28 '12 at 2:10