Sum with Binomial Coefficients to Floor Function

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.

• The floors are not actually a problem here. What do you know about binomials ? do you know z-Transform ? – G Cab Jan 22 at 23:52

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$$.