How to show that this binomial sum satisfies the Fibonacci relation? 
The binomial sum
  $$s_n=\binom{n+1}{0}+\binom{n}{1}+\binom{n-1}{2}+\cdots$$
  satisfies the Fibonacci relation.

I failed to prove that $\binom{n-k+1}{k}=\binom{n-k}{k}+\binom{n-k-1}{k}$... Any hints or suggestions?
 A: $\newcommand{\angles}[1]{\left\langle\, #1 \,\right\rangle}
 \newcommand{\braces}[1]{\left\lbrace\, #1 \,\right\rbrace}
 \newcommand{\bracks}[1]{\left\lbrack\, #1 \,\right\rbrack}
 \newcommand{\ceil}[1]{\,\left\lceil\, #1 \,\right\rceil\,}
 \newcommand{\dd}{{\rm d}}
 \newcommand{\ds}[1]{\displaystyle{#1}}
 \newcommand{\dsc}[1]{\displaystyle{\color{red}{#1}}}
 \newcommand{\expo}[1]{\,{\rm e}^{#1}\,}
 \newcommand{\fermi}{\,{\rm f}}
 \newcommand{\floor}[1]{\,\left\lfloor #1 \right\rfloor\,}
 \newcommand{\half}{{1 \over 2}}
 \newcommand{\ic}{{\rm i}}
 \newcommand{\iff}{\Longleftrightarrow}
 \newcommand{\imp}{\Longrightarrow}
 \newcommand{\Li}[1]{\,{\rm Li}_{#1}}
 \newcommand{\norm}[1]{\left\vert\left\vert\, #1\,\right\vert\right\vert}
 \newcommand{\pars}[1]{\left(\, #1 \,\right)}
 \newcommand{\partiald}[3][]{\frac{\partial^{#1} #2}{\partial #3^{#1}}}
 \newcommand{\pp}{{\cal P}}
 \newcommand{\root}[2][]{\,\sqrt[#1]{\vphantom{\large A}\,#2\,}\,}
 \newcommand{\sech}{\,{\rm sech}}
 \newcommand{\sgn}{\,{\rm sgn}}
 \newcommand{\totald}[3][]{\frac{{\rm d}^{#1} #2}{{\rm d} #3^{#1}}}
 \newcommand{\ul}[1]{\underline{#1}}
 \newcommand{\verts}[1]{\left\vert\, #1 \,\right\vert}$
\begin{align}\color{#66f}{\large s_{n}}&
={n+1 \choose 0} + {n \choose 1} + {n - 1 \choose 2} + \cdots
=\sum_{k\ =\ 0}^{\infty}{n + 1 - k \choose k}
\\[5mm]&=\sum_{k\ =\ 0}^{\infty}\ \overbrace{\oint_{\verts{z}\ =\ \varphi^{+}}
{\pars{1 + z}^{n + 1 - k} \over z^{k + 1}}\,{\dd z \over 2\pi\ic}}
^{\ds{=\ \dsc{n + 1 - k \choose k}}}
\end{align}

where $\ds{\varphi \equiv {1 + \root{5} \over 2}}$ is the
  Golden Ratio.
  Then,

\begin{align}
\color{#66f}{\large s_{n}}&
=\oint_{\verts{z}\ =\ \varphi^{+}}{\pars{1 + z}^{n + 1} \over z}
\sum_{k\ =\ 0}^{\infty}\bracks{1 \over z\pars{1 + z}}^{k}\,{\dd z \over 2\pi\ic}
\\[5mm]&=\oint_{\verts{z}\ =\ \varphi^{+}}{\pars{1 + z}^{n + 1} \over z}
{1 \over 1 - 1/\bracks{z\pars{1 + z}}}\,{\dd z \over 2\pi\ic}
=\oint_{\verts{z}\ =\ \varphi^{+}}{\pars{1 + z}^{n + 2} \over z^{2} + z - 1}
\,{\dd z \over 2\pi\ic}
\\[5mm]&=\oint_{\verts{z}\ =\ \varphi^{+}}
{\pars{1 + z}^{n + 2} \over \pars{z + \varphi}\pars{z - \varphi^{-1}}}
\,{\dd z \over 2\pi\ic}
={\pars{1 - \varphi}^{n + 2} \over -\varphi - \varphi^{-1}}
+{\pars{1 + \varphi^{-1}}^{n + 2} \over \varphi^{-1} + \varphi}
\end{align}

However,
  $\ds{\quad\varphi + \varphi^{-1}=\root{5}\,,\quad 1 + \varphi^{-1}=\varphi\quad}$ such that

$$
\color{#66f}{\large s_{n}}
={\varphi^{n + 2} - \pars{1 - \varphi}^{n + 2} \over \root{5}}
=\color{#66f}{\large F_{n + 2}}
$$

where $\ds{F_{m}}$ is a
  Fibonacci Number.

A: The problem with proving $\binom{n-k+1}k=\binom{n-k}k+\binom{n-k-1}k$ is that it is not true (try $k=0$ for starters). However for $n\geq1$ one has
$$\begin{aligned}
  s_{n-1}&=\sum_{k=0}^{\lfloor\frac n2\rfloor}\binom{n-k}k\\
 &= 1+\sum_{k=1}^{\lfloor\frac n2\rfloor}(\binom{n-1-k}k+\binom{n-1-k}{k-1})\\
 &= 1+\sum_{k=1}^{\lfloor\frac {n-1}2\rfloor}\binom{n-1-k}k
     +\sum_{k=1}^{\lfloor\frac n2\rfloor}\binom{n-1-k}{k-1}\\
 &= s_{n-2}+\sum_{k=0}^{\lfloor\frac n2\rfloor-1}\binom{n-2-k}k\\
 &= s_{n-2}+s_{n-3},\\
 \end{aligned}
$$
so that the sequence $(s_n)_{n\geq-1}$ satisfies the Fibonacci recurrence (with $s_{-1}=\binom00=1$ by the same definition as $s_n$ for $n\in\mathbf N$). Since moreover $s_{-1}=s_0=1$ one has $s_n=F_{n+2}$ for all $n\geq-1$.
One wonders what is the point of starting the defining expression for $s_n$ with $\binom{n+1}0$, as the "$+1$" only increases the shift with respect to the Fibonacci sequence. To resume, one has
$$ F_n=\sum_{k=0}^{\lfloor\frac{n-1}2\rfloor}\binom{n-1-k}k
  \qquad\text{for }n\geq1.
$$
Added: although the summation runs into terms $0$ once $k>n/2$ (this is implicitly used in the argument above where we dropped the final term from the first summation in the third line), it should not be written as an unbounded (therefore infinite) summation: when one gets to terms for $k>n$, the terms are again nonzero, by the usual convention for binomial coefficients with negative upper index. This point should have been made clearer in the question. 
A: We begin with the identity:
$$
\binom{n+1}{k+1} = \binom{n}{k+1} + \binom{n}{k}.
$$
We apply the identity to 
$$
s_n=\binom{n+1}{0}+\binom{n}{1}+\binom{n-1}{2}+\cdots
$$
to get
$$
s_n= \underbrace{\color{blue}{\binom{n}{0}} + \color{grey}{\binom{n}{-1}}}_{\text{first term}} + \underbrace{\color{blue}{\binom{n-1}{1}} + \color{brown}{\binom{n-1}{0}}}_{2\text{nd term}} +
\underbrace{\color{blue}{\binom{n-2}{2}} + \color{brown}{\binom{n-2}{1}} }_{3\text{rd term}} + \cdots 
$$
Notice that the terms in are $\color{blue}{s_{n-1}}$ and those in brown/red $\color{brown}{s_{n-2}}$. (I had to work out what $s_{n-1}$ and $s_{n-2}$ was in order to catch the pattern, in case you're wondering how I knew). And so we have our fibonacci relation
$$
s_n = \color{blue}{s_{n-1}} + \color{brown}{s_{n-2}}
$$
As for the $\binom{n}{-1}$ term, just define it to be $0$...If that's not allowed, then wave your hands and mumble something.
A: Consider the words of length $n+1$ with letters 0,1 and no two consecutive 1s.
Prove that they are counted by the Fibonacci numbers.
Now count the same kind of words that contain exactly $k$ letters 1.
A: This approach was explained in the above comments by N.S and 
and
Henning

We can show $$\sum_{k\ge0} \binom{n-k}k=F_{n+1}$$
by induction.
Note that I did not specify the range for $k$. I am using the usual convention that $\binom pq$ is considered zero whenever $q<0$ or $q>p$. EDIT: After reading Marc van Leeuwen's answer I've realized, that this is true for non-negative $q$ only, so I've change range to $k\ge0$.
$1^\circ$ We can verify $n=-1,0,1,2$ by hand.
$2^\circ$ Inductive step: Suppose $n>1$. We want to show that this is true for $n+1$ and assume validity of the formula for $0,1,\dots,n$.
$$\sum_{k\ge0} \binom{n+1-k}k=\sum_{k\ge0} \binom{n-k}k + \sum_{k\ge0} \binom{n-k}{k-1}=
\sum_{k\ge0} \binom{n-k}k + \sum_{k\ge0} \binom{n-1-(k-1)}{k-1}=
\sum_{k\ge0} \binom{n-k}k + \sum_{j\ge0} \binom{n-1-j}{j}= F_{n+1}+F_n = F_{n+2}.$$

This proof can be visualized as follows: We are computing the sums of terms in Pascal triangle along diagonals.
It suffices to notice that each element on $k$-th diagonal is a sum of an element from $(k-1)$-th diagonal and $(k-2)$-th diagonal.
(I've taken the picture from thesis of my student I supervised some time ago.
I am not sure whether she made the picture herself or found it somewhere on the Internet.)

