Simplify $\sum_{k=0}$ $n−2k \choose k$ Simplify $$\sum_{k=0} \binom{n−2k}  k$$ Or alternatively, show that it can't be simplified any more.
I tried Hockey stick identity but I had issues with the fact that the top had a -2k term. I then tried using $\binom {n+1}{k+1}$ = $\binom{n}{k} + \binom{n}{k+1}$, but again the -2k term means you can't add consecutive terms. Some values I calculated are
3 for n=4
4 for n=5
6 for n =6
9 for n=7.
There doesn't seem to be a pattern.
 A: We have that $\binom{n-2k}{k}=\binom{n-2k-1}{k-1}+\binom{n-2k-1}{k}$. Hence,
$$\sum_{k=0} \binom{n-2k}{k}=\sum_{k=0}\binom{(n-1)-2k}{k-1}+\sum_{k=0} \binom{(n-1)-2k}{k}$$
If $a_n=\sum_{k=0} \binom{n-2k}{k}$, then we have
$$a_n=a_{n-1}+\sum_{k=0} \binom{(n-1)-2k}{k-1}$$
$$a_n=a_{n-1}+\sum_{k=0} \binom{(n-1)-2(k-1)-2}{k-1}$$
$$a_n=a_{n-1}+\sum_{k=0} \binom{(n-3)-2(k-1)}{k-1}$$
Shifting the indices of this summation gives us
$$a_n=a_{n-1}+\sum_{k=0} \binom{(n-3)-2k}{k}$$
$$a_n=a_{n-1}+a_{n-3}$$
The characteristic equation of this linear recurrence is
$$x^3-x^2-1=0$$
Wolfram Alpha says that the roots of this equation are very complex. One could possibly solve for the explicit equation for the recurrence using the roots $r_1,r_2,r_3$. However, it would be tedious to find the values of constants $u,v,w$ that satisfy the initial conditions which yield
$$a_n=ur_1^n+vr_2^n+wr_3^n$$
A: This is only an alternative to find the recurrence relation above. The expression $\binom{n-k}{k}$ gives the number of solutions to the equation $n=\sum{x_{i}}\phantom{x}|\phantom{x}x_{i}\in\{1,3\}$ when there are $k$ threes. Therefore the following expression gives the number of possibilities to express $n$ as summation of ones and threes.
$$
a_{n}=\sum{\binom{n-2k}{k}}
$$
There are only two possibilities for $x_{1}$. If $x_{1}=1$ then the other $x_{i}$ are ones and threes that sum up to $n-1$. If $x_{1}=3$ then the other $x_{i}$ are ones and threes that sum up to $n-3$. Hence the following recurrence relation:
$$
a_{n}=a_{n-1}+a_{n-3}
$$
A: Maybe expressing this sum using the Generalized Hypergeometric function may form a starting point for further simplifications:
$\binom{0}{\frac{n}{2}} \, _4F_3\left(\frac{1}{2},1,1,-\frac{n}{2};\frac{1}{3}-\frac{n}{6},\frac{2}{3}-\frac{n}{6},1-\frac{n}{6};-\frac{4}{27}\right)$
Hopefully there exist some identities or theorems (such as those from Saalschütz, Dixon or Dougall for example) that enable further simplifications.
