<s>[INST] $\sum_{k=\frac{n}{2}}^{n}\binom{k}{n-k}=F_n$? 
Is it true:
$$\sum_{k=\frac{n}{2}}^{n}\binom{k}{n-k}=F_n? $$ where $F_n$ is a
  Fibonacci number.

Wolfram alpha says that the answer must be $F_{n+1}$.
I've seen many posts with this question but none of them was helpful to me. And this time the sum is different. Can anybody give me a breath explanation how should I solve this equation?
Edit: $n \ge 0, \quad F_1=F_2=1$
 [/INST] It depends. If you assume that the Fibonacci numbers start with $F_1=1$ and $F_2=1$, then Wolfram alpha is correct, i.e.
$$
\sum_{k=\frac{n}{2}}^n \binom{k}{n-k}=F_{n+1}.
$$
If you assume that the Fibonacci numbers start with $F_1=0$ and $F_2=1$, then we have
$$
\sum_{k=\frac{n}{2}}^n \binom{k}{n-k}=F_{n}.
$$
Actually, with $F_1=F_2=1$, we have
$$
\sum_{k=\lceil\frac{n}{2}\rceil}^n \binom{k}{n-k}=F_{n+1}.
$$
Let
$$
y_n = \sum_{k=\lceil\frac{n}{2}\rceil}^n \binom{k}{n-k}.
$$
What I want to proof is that $y_n = y_{n-2}+y_{n-1}$. I will use the fact that $\binom{n}{k}=\binom{n-1}{k-1}+\binom{n-1}{k}$. First, I proof this for $n$ is even, such that I can use the fact that $\lceil \frac{n+1}{2} \rceil = \lceil \frac{n}{2} \rceil + 1$:
\begin{align}
y_n &= 1 + \sum_{k=\lceil\frac{n}{2}\rceil+1}^{n-1} \binom{k}{n-k} + 1 \\
&=\sum_{k=\lceil\frac{n}{2}\rceil+1}^{n-1} \binom{k-1}{n-k-1}+1 + \sum_{k=\lceil\frac{n}{2}\rceil+1}^{n-1} \binom{k-1}{n-k}+1 \\
&=\sum_{k=\lceil\frac{n}{2}\rceil+1}^{n-1} \binom{k-1}{n-2-(k-1)}+1 + \sum_{k=\lceil\frac{n+1}{2}\rceil}^{n-1} \binom{k-1}{n-1-(k-1)}+1 \\
&= \sum_{k=\lceil\frac{n-2}{2}\rceil+1}^{n-2} \binom{k}{n-2-k}+1 + \sum_{k=\lceil\frac{n-1}{2}\rceil}^{n-2} \binom{k}{n-1-k} + 1 \\
&= \sum_{k=\lceil\frac{n-2}{2}\rceil}^{n-2} \binom{k}{n-2-k} + \sum_{k=\lceil\frac{n-1}{2}\rceil}^{n-1} \binom{k}{n-1-k} \\
&=y_{n-2} + y_{n-1}.
\end{align}
Now we can do the same for $n$ being odd. I will assume that $\lceil\frac{n}{2}\rceil-1 = \lceil\frac{n-1}{2}\rceil$:
\begin{align}
y_n &= \sum_{k=\lceil\frac{n}{2}\rceil}^{n-1} \binom{k}{n-k} + 1 \\
&= \sum_{k=\lceil\frac{n}{2}\rceil}^{n-1} \binom{k-1}{n-k-1} + \sum_{k=\lceil\frac{n}{2}\rceil}^{n-1} \binom{k-1}{n-k} + 1 \\
&= \sum_{k=\lceil\frac{n}{2}\rceil}^{n-1} \binom{k-1}{n-2-(k-1)} + \sum_{k=\lceil\frac{n}{2}\rceil}^{n-1} \binom{k-1}{n-1-(k-1)} + 1 \\
&= \sum_{k=\lceil\frac{n-2}{2}\rceil}^{n-2} \binom{k}{n-2-k} + \sum_{k=\lceil\frac{n-1}{2}\rceil}^{n-2} \binom{k}{n-1-k}+1 \\
&= y_{n-2} + \sum_{k=\lceil\frac{n-1}{2}\rceil}^{n-1} \binom{k}{n-1-k} \\
&= y_{n-2} + y_{n-1}.
\end{align}
</s>