all!
I have recently begun my studies in an upper-level discrete mathematics course. So far, I have quite enjoyed all of the lectures.
I recently came across an exercise on a supplemental homework requesting me to compute a trio of three binomial sums containing floor functions:
$$\sum_{k=0}^{\left\lfloor\frac{n}{3}\right\rfloor} {n \choose 3k}$$ $$\sum_{k=0}^{\left\lfloor\frac{n}{3}\right\rfloor} {n \choose 3k+1}$$ $$\sum_{k=0}^{\left\lfloor\frac{n}{3}\right\rfloor} {n \choose 3k+2}$$
About an hour ago, I had not even heard of ceiling and floor functions.
I have tried to work the first sum out, but I really am not sure how to continue with these floor functions, nor am I sure how to truly approach these sums.
Any and all help would be greatly appreciated! Thank you all for taking the time to read my post.
Hint: Let $a_n$ be your first summation, and $b_n,c_n$ be the second and third. Start by computing these exactly for small values of $n$. You should start to notice a general pattern emerging. Describe the pattern exactly, then prove that it holds in general using induction on $n$. Use the base cases $$ a_0 = 1, b_0=0,c_0=0 $$ and the rules $$ a_{n+1}=a_n+c_n,\qquad b_{n+1}=b_n+a_n,\qquad c_{n+1}=c_n+b_n $$ The rule $a_{n+1}=a_n+c_n$ can be proven by applying Pascal's identity to each summand in $a_{n+1}$, and then splitting into two summations, which will be exactly $a_n$ and $c_n$.