<s>[INST] Is there a way to rewrite this expression as a sum of the previous two terms? 
The context of this question:

Consider for ${n \in \mathbb{N}, n\geq 0}$ a rectangular board divided into a ${2 \times n}$ square grid.
A ${2 \times 1}$ domino can cover any two horizontally or vertically adjacent squares. Prove by induction that there are exactly $F_{n+1}$ different ways to cover every square of the board with no two dominoes overlapping, where ${F_{n+1} 
 = F_{n} + F_{n-1}, F_{0}=0, F_{1}=1}$.

The (unfinished) answer so far:

A ${2 \times 2}$ "pair" in this answer is a pair of adjacent horizontal dominoes that take up a ${2 \times 2}$ space on the ${2 \times n}$ grid.
Take ${n}$ to be the length of the grid's rows. The number of ways of arranging non-overlapping ${2 \times 1}$ dominoes on a ${2 \times n}$ grid is equal to the number of ways some ${2 \times 2}$ "pairs" fit on a ${2 \times n}$ grid.
For example, for ${n=3}$, there is one way of fitting zero ${2 \times 2}$ "pairs" on a ${2 \times n}$ grid (all dominoes are placed vertically), and there are two ways of fitting one ${2 \times 2}$ "pair" on a ${2 \times n}$ grid i.e. the first arrangement has a ${2 \times 1}$ domino on its leftmost column with a ${2 \times 2}$ "pair" to its right and the second arrangement has a ${2 \times 1}$ domino on its rightmost column with a ${2 \times 2}$ "pair" to its left.
A ${2 \times 2 }$ "pair" takes up two of the ${n}$ columns. This means that the maximum number of "pairs" that can fit on a ${2 \times n}$ grid is ${\frac{n-1}{2}}$ if ${n}$ is odd and ${\frac{n}{2}}$ if n is even. Combining this into one formula gives:
${M}$, The maximum number of "pairs" for a given ${n}$, ${ = \frac{n+\frac{1}{2}((-1)^n-\frac{1}{2})}{2} = \frac{1}{4}{(2n+(-1)^{n}-1)}}$
The number of "pairs" ${k}$ on a ${2 \times n}$ grid is therefore ${0 \leq k \leq M}$. A "pair" takes up two columns, so the number of columns available after ${k}$ "pairs" have been placed for any given ${k}$ is equal to ${n-2k}$. When ${k}$ "pairs" have been placed, there are ${k}$ ${2 \times 2}$ "spaces" each taken up by a "pair" and ${n-2k}$ ${2 \times 1}$ "spaces" taken up by single vertical dominos, which means ${k+(n-2k)=n-k}$ total "spaces" filled. The number of ways of arranging these ${k}$ "pairs" on a ${2 \times n}$ grid is therefore given by ${n-k \choose k}$. For example, for ${n=5, k=2}$, placing ${k=2}$ "pairs" on the grid means there is ${n-2k=1}$ column left and so ${k+(n-2k)=n-k=3}$ "spaces" (two ${2 \times 2}$ spaces each taken up by a "pair" and one ${2 \times 1}$ space taken up by a single domino). Given that ${k}$ of these "spaces" are taken up by "pairs", the number of possible arrangements of these "pairs" within the "spaces" is ${{n-k \choose k} = {3 \choose 2} = 3}$.
All the ways of arranging these ${k}$ "pairs" (${\forall k}$ where ${0 \leq k \leq M}$) for a given ${n}$, is given by:
${A_n={\sum \limits_{k=0}^{k=M}} {n-k \choose k}}$
To get the ${M}$ values for ${n-1}$ and ${n-2}$, i.e. the maximum value for ${k}$ (number of ${2 \times 2}$ "pairs" that can fit on a ${2 \times n}$ grid) for ${n-1}$ and ${n-2}$, first consider when ${n}$ is odd. When ${n}$ is odd, the maximum number of "pairs" is the same as the maximum number of "pairs" for ${n-1}$. When ${n}$ is even, the maximum number of "pairs" for ${n-1}$ is one less than the maximum number of "pairs" for ${n}$. So this number, ${M_{n-1}}$, is given by
${M_{n-1}=M-(\frac{1}{2}(-1)^{n}+\frac{1}{2})}$.
Substituting in ${M}$, rearranging, and using the fact that ${(-1)=(-1)^{-1}}$ gives
${M_{n-1}=\frac{1}{4}{(2(n-1)+(-1)^{n-1}-1)}}$
which is the maximum value of ${k}$ for the case ${n-1}$. To get the ${M}$ value for ${n-2}$, ${M_{n-2}}$, the value ${M-1}$ is considered:
${M_{n-2}=M-1=\frac{1}{4}{(2n+(-1)^{n}-1)}-1}$
$=$ ...
${ = \frac{1}{4}{(2(n-2)+(-1)^{n-2}-1)}}$.
What's left to consider is the possible relation between
${A_n={\sum \limits_{k=0}^{k=M}} {n-k \choose k}}$ and the two formulas
${M_{n-1}=\frac{1}{4}{(2(n-1)+(-1)^{n-1}-1)}}$ and
${M_{n-2}=\frac{1}{4}{(2(n-2)+(-1)^{n-2}-1)}}$ to give the inductive step of this answer.

The question given the above context:
Is there a way to rewrite the expression ${{\sum \limits_{k=0}^{k=M}} {n-k \choose k}}$
as ${{\sum \limits_{k=0}^{k=M_{n-1}}} {n-1-k \choose k}} + {{\sum \limits_{k=0}^{k=M_{n-2}}} {n-2-k \choose k}}$, where
${M=\frac{1}{4}(2n + (-1)^n - 1)}$
${M_{n-1}=\frac{1}{4}(2(n-1) + (-1)^{n-1} - 1)}$
${M_{n-2}=}{\frac{1}{4}(2(n-2) + (-1)^{n-2} - 1)}$
$n \in \mathbb{N},\forall n \ge 0$?
 [/INST] One thing to do in a situation like this (especially with such a very complicated chain of reasoning) is to check the results for some small input values.
For example, if $n = 6,$ then
$M = \frac14(2(6) + (-1)^6 - 1) = 3,$ and
\begin{align}
 \sum_{k=0}^{k=M} \binom{n-k}{k} &= \sum_{k=0}^{k=3} \binom{6-k}{k}\\
 &= \binom60 + \binom51 + \binom42 + \binom33 \\
 &= 1 + 5 + 6 + 1 \\
 &= 13.
\end{align}
For the first few values of $n$:
\begin{align}
A_0 &= \binom00 \\
A_1 &= \binom10 \\
A_2 &= \binom20 + \binom11 \\
A_3 &= \binom30 + \binom21 \\
A_4 &= \binom40 + \binom31 + \binom22 \\
A_5 &= \binom50 + \binom41 + \binom32 \\
A_6 &= \binom60 + \binom51 + \binom42 + \binom33 \\
A_6 &= \binom70 + \binom61 + \binom52 + \binom43 \\
\end{align}
For $n$ even, write the sum
\begin{align}
A_{n-2} + A_{n-1}
&= \left(\binom{n-2}0 + \binom{n-3}1 + \cdots
         + \binom{n/2}{(n/2) - 2} + \binom{(n/2) - 1}{(n/2) - 1}\right) \\
  & \qquad + \left(\binom{n-1}0 + \binom{n-2}1 + \binom{n-3}2 + \cdots
                  + \binom{n/2}{(n/2) - 1}\right) \\
&= \binom{n-1}0 + \left(\binom{n-2}0 + \binom{n-2}1\right)
      + \left(\binom{n-3}1 + \binom{n-3}2\right) \\
  & \qquad + \cdots + \left(\binom{n/2}{(n/2) - 2} + \binom{n/2}{(n/2) - 1}\right)
         + \binom{(n/2) - 1}{(n/2) - 1} \\
&= \binom n0 + \binom{n-1}1 + \binom{n-2}2 + \cdots +
      \binom{(n/2) + 1}{(n/2) - 1} + \binom{n/2}{n/2}
\end{align}
using the identity $$\binom{p - 1}{q - 1} + \binom{p - 1}q = \binom pq.$$
In short, we interleave the terms, carry the first and last term down individually,
and add the other terms in pairs.
The sum for odd $n$ is similar except that it has an odd number of terms in the intermediate sums, carrying down the first term and adding the rest in pairs.
This is still a somewhat informal proof due to all the "$\cdots$" parts.
To eliminate those I think you would need double induction.
On the other hand, as hinted in comments, there is a much simpler
inductive proof if you can find it.
It has been written up on this site before if you want to go looking for a spoiler,
but here's a hint: consider what you might find in the last column of two squares on the right.
</s>