I'm doing Pascal's Triangle and there are a ton of questions related to Pascal and the Fibonacci numbers embedded in the triangle, but I have a question about combinatorics which is most likely a very simple and trivial question. I derived the Fibonacci numbers using the triangle and combination notation and figured out that $$F_n=\sum_{k=0}^{\left\lfloor \frac{n}{2} \right\rfloor}\binom{n-k}{k}$$ But all other formulae I see just replaces my upper bound with $n$. And thus, a much nicer formula is $$F_n=\sum_{k=0}^n\binom{n-k}{k}$$ Ultimately this happens because at some point, $n-k \lt k$ and so you can't have say, 3 choose 4. Or can you? Is it really as simple as saying "there are $0$ ways to choose $4$ from $3$" and thus, whenever $n-k \lt k$, $\binom{n-k}{k}=0$? I always thought that it was undefined, but never really pondered it, or checked old texts to see if this situation was even mentioned. I thought my "floored" upper bound was neat because it removes the cases mentioned above, but I suppose it's cleaner with just $n$...

  • $\begingroup$ 1. Please check your formulas, the binomials appear incorrect. 2. It is common to extend ${n\choose k}$ to be zero if $k<0$. 3. It is definitely true that ${n\choose k}=0$ if $n,k$ are integers with $k>n$. $\endgroup$ – vadim123 Dec 18 '13 at 4:01
  • $\begingroup$ Oh, the bottom should be $k$, not $n$. I'll fix it. $\endgroup$ – Eleven-Eleven Dec 18 '13 at 4:03

It’s quite customary to define $\binom{m}k=0$ for $k>m$ and for $k<0$, so you could in fact just as well say simply


all of the unwanted terms are $0$ anyway. Some define $\binom{m}k$ only for non-negative integers $k$, and then you do have to impose the lower limit of $0$ and the upper limit of $n$ on the summation.

| cite | improve this answer | |
  • $\begingroup$ For your last comment, yeah, it's late and definitely a typo...i fixed it. Thanks for the clarification. $\endgroup$ – Eleven-Eleven Dec 18 '13 at 4:04
  • $\begingroup$ @Christopher: You’re welcome. (Comment removed now.) $\endgroup$ – Brian M. Scott Dec 18 '13 at 4:05

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.