Closed form representation for $\sum_{k=0}^{\lfloor n/2 \rfloor} \binom{n-k}k$

Question

Answering some other question, I stumbled upon the following relationship:

For $n\in\Bbb N$ let $$p_n = \sum_{k=0}^{\lfloor n/2 \rfloor} \binom{n-k}k$$ and let

$$a_n = p_n+p_{n-2}\quad \text{ if } n \geqslant 2; \qquad (a_1,a_2) = (1,3)$$ then $a_n = L_n$ where $L_n$ is the $n$-th Lucas number.

Question: Lucas numbers can be represented in closed form as $L_n=\varphi^n+(-\varphi)^{-n}$ where $\varphi$ is the Golden ratio. Does this also yield a closed form for $p_n$ as defined above? Using the definition of $a_n$ will only yield $p_n$ as an alternating sum over $a_n$'s like $$ a_n-a_{n-2}+a_{n-4}-\cdots \quad=\quad p_n\pm p_{n\text{ mod 2}} $$ etc. but not a neat closed formula. Intuitively, the $p_n$ have the same exponential growth like $\varphi^n$, but that's not enough to find a closed form.

Answer 1

$p_n=\sum_{k=0}^{[n/2]}{n-k\choose k}=\sum_{k=0}^{[n/2]}{n-k-1\choose k}+\sum_{k=0}^{[n/2]}{n-k-1\choose k-1}$

$\implies p_n=\sum_{k=0}^{[(n-1)/2]}{n-k-1\choose k}+\sum_{j=0}^{[(n-2 )/2]}{n-j-2\choose j}+{[n/2]-1 \choose [n/2]}$

$\implies p_n=p_{n-1}+p_{n-2}.$ $p_n$ are Fibonacci numbers. Hence

Answer 2

Through Cauchy's integral theorem

$$p_{2n}=\sum_{k=0}^{n}\binom{2n-k}{k}=\sum_{k=0}^{n}[x^k](1+x)^{2n-k}=\frac{1}{2\pi i}\sum_{k=0}^{n}\oint_{|x|=\varepsilon}\frac{(1+x)^{2n}}{(1+x)^k x^{k+1}}\,dx $$ equals $$ \frac{1}{2\pi i}\oint_{|x|=\varepsilon}\frac{(1+x)^{2n+1}-x^{-n-1}(1+x)^{n}}{-1+x+x^2}\,dx=\frac{1}{2\pi i}\oint_{|x|=\varepsilon}\frac{(1+x)^n}{(1-x-x^2)x^{n+1}}\,dx$$ or $$ \operatorname*{Res}_{x=0}\frac{(1+x)^n}{(1-x-x^2)x^n}. $$ For any $n\in\mathbb{N}$ the meromorphic function $\frac{(1+x)^n}{(1-x-x^2)x^n}$ has simple poles at $\frac{-1+\sqrt{5}}{2}$ and $\frac{-1-\sqrt{5}}{2}$ and a pole with order $n$ at the origin. Since the sum of the residues equal zero, a closed form for $p_n$ can be deduced by computing the residues at $\frac{-1\pm \sqrt{5}}{2}$, leading to $p_{2n}=F_{2n+1}$. With minor adjustments this also proves that $p_{2n-1}=F_{2n}$.