How to show that this binomial sum satisfies the Fibonacci relation?

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.

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

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.