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
    Thanks. Are there any common way to solve such kind of problems? Any good reading?2012-10-28
  • 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