Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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

share|cite|improve this question
up vote 2 down vote accepted

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.

share|cite|improve this answer
Thanks. Are there any common way to solve such kind of problems? Any good reading? – aam Oct 28 '12 at 2:05
@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

Your Answer


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.