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

$\endgroup$
2
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ Thanks. Are there any common way to solve such kind of problems? Any good reading? $\endgroup$ – aam Oct 28 '12 at 2:05
  • $\begingroup$ @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. $\endgroup$ – Brian M. Scott Oct 28 '12 at 2:10

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.