# Pascal/Fibonacci and Combinatorics notation

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

• 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$. – vadim123 Dec 18 '13 at 4:01
• Oh, the bottom should be $k$, not $n$. I'll fix it. – 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
$$F_n=\sum_k\binom{n-k}k\;:$$
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.