Recurrence relation of binomial sum. I'm trying to find a closed-form solution to the sum
$$
a(n):= \sum_{k=0}^{\lfloor n/3 \rfloor} \binom{n}{3k}.
$$
In my attempt, I found the first few values of $a(n)$ and entered them into the OEIS and got a hit for sequence A024493. In the notes there I saw that there was a recurrence relation given, namely
$$
a(n) = 3a(n-1)-3a(n-2)+2a(n-3)
$$
or perhaps more illuminatingly
$$
a(n)-3a(n-1)+3a(n-2)-a(n-3) = a(n-3)
$$
where we can see that the coefficients on the right hand side are $(-1)^i \binom{3}{i}$ for $0\leq i \leq 3$.
I've tried proving this relation by induction, but the result seems to depend on the value of
$n\mod 3$ more than on the previous terms.
Any thoughts on how I can prove that $a(n)$ satisfies the given recursion?
 A: Bearing in mind that for $ k > n$ or $ k < 0$, ${ n \choose k } =0 $, we can write $a_n = \sum_{k= - \infty } ^\infty { n \choose 3k}$. This allows us to avoid the "have to consider $n \pmod{3}$ cases".
Then use the identity $ { n\choose k } = { n-1 \choose k-1  } + { n - 1 \choose k }$ (which is still true when $k > n$ or $k < 0$) to iteratively reduce $a_n - 3 a_{n-1} + 3a_{n-2} + 2 a_{n-3}$, IE
$= \left[ \sum_{k} { n \choose 3k} \right] - 3 a_{n-1} + 3a_{n-2} - 2 a_{n-3}    $
$ = \left[ \sum_{k} { n-1 \choose 3k-1}  + {n-1 \choose 3k }\right] - 3 a_{n-1} + 3a_{n-2} - 2 a_{n-3}$
$ = \left[ \sum_{k} { n-1 \choose 3k-1}  - 2 {n-1 \choose 3k }\right]   + 3a_{n-2} - 2 a_{n-3}$
$ = \ldots $
Can you complete this to show that it equals 0?
A: By binomial theorem:
$$(1+x)^n={n \choose 0}+ {n \choose 1} x+ {n \choose 2} x^2+{ n\choose 3} x^3+{n \choose 4} x^4+....+{n \choose n}x^n~~~~(1)$$
Let us put $x=1,w,w^2$ whgere $w$ is cube root of unity such that $w^3=1$ and $1+w+w^2=0$.
We get $$2^n={n \choose 0}+ {n \choose 1} + {n \choose 2}+{ n\choose 3}+{n \choose 4}+....+{n \choose n}.~~~~(2)$$
$$(1+w)^n={n \choose 0}+ {n \choose 1} w+ {n \choose 2} w^2+{ n\choose 3} w^3+{n \choose 4} w^4+....+{n \choose n}w^n~~~~(3)$$
$$(1+w^2)^n={n \choose 0}+ {n \choose 1}w^2 + {n \choose 2} w+{ n\choose 3}w^6+{n \choose 4}w^2+....+{n \choose n}w^{2n}.~~~~(4)$$
Adding (1-3) abd sing the property that $1+w+w^2=0$, we get
$$A_n=\sum_{k=0}^{[n/3]} {n \choose 3k}=\frac{1}{3}(2^n+(-1)^n[e^{4i\pi n/3}+e^{2i\pi n/3}])=\frac{1}{3}[2^n+2\cos(\pi n/3)]$$
One can check that both $2^n$ and $\cos(\pi n/3)$ both combined or separately satisfy the claimed recurrence relation that
$$A_n-3A_{n-1}+3A_{n-2}-2A_{n-3}=0,$$
because $-3A_{n-1}+3A_{n-2}=-3\cos(n \pi/3)$ and $A_n-2A_{n-3}=3 \cos (n\pi/3)$
A: Snake oil simultaneously discovers and proves the recurrence:
\begin{align}
\sum_{n \ge 0} a_n z^n
&=\sum_{n \ge 0} \sum_{k=0}^{\lfloor n/3 \rfloor} \binom{n}{3k} z^n \\
&= \sum_{k\ge 0} \sum_{n \ge 3k} \binom{n}{3k} z^n \\
&= \sum_{k\ge 0} \frac{z^{3k}}{(1-z)^{3k+1}} \\
&= \frac{1}{(1-z)} \sum_{k\ge 0} \left[\left(\frac{z}{1-z}\right)^3\right]^k \\
&= \frac{1}{(1-z)} \cdot \frac{1}{1-\left(\frac{z}{1-z}\right)^3} \\
&= \frac{(1 - z)^2}{(1 - 2 z) (1 -z + z^2)} \\
&= \frac{(1 - z)^2}{1 - 3 z + 3 z^2 - 2 z^3}
\end{align}
The denominator immediately implies that $$a_n=3 a_{n-1} - 3 a_{n-2} + 2 a_{n-3}.$$
