Use a generating function to evaluate, in closed form, the sum $$ a_k=\sum_{j=\lceil k/2\rceil}^k {j \choose k-j}. $$ I wrote out that $G(x) = 1 + x + x^2 + 2x^3 + x^4 + 4x^5 + \dots$
I'm not sure where to go from here. I have a hint that I should be able switch summations and use the generating function of the Fibonacci sequence but I am not sure how that helps.
HINT: The generating function is
$$\sum_{k\ge 0}a_kx^k=\sum_{k\ge 0}\sum_{j=\lceil k/2\rceil}^k\binom{j}{k-j}x^k=\sum_{j\ge 0}\sum_{k=j}^{2j}\binom{j}{k-j}x^k\;,$$
where reversing the order of summation requires recognizing that $\left\lceil\frac{k}2\right\rceil\le j\le k$ if and only if $j\le k\le 2j$. Let $\ell=k-j$; then
$$\sum_{k=j}^{2j}\binom{j}{k-j}x^k=\sum_{\ell=0}^j\binom{j}\ell x^{j+\ell}=x^j\sum_{\ell=0}^j\binom{j}\ell x^\ell=x^j(x+1)^j$$
by the binomial theorem. Thus,
$$\sum_{k\ge 0}a_kx^k=\sum_{j\ge 0}x^j(x+1)^j\;.$$
This is a geometric series, so you can write down a closed form; compare that with the generating function for the Fibonacci sequence, and you should get the desired result.