$S_{n}$ is the sum of every third element in the $n$th row of the Pascal triangle, beginning on the left with the second element. Find $S_{100}$.

Question

Problem:

Let $S_{n}$ be the sum of every third element in the $n$th row of the Pascal triangle, beginning on the left with the second element. Find the value of $S_{100}$.

My work:

For brevity, I worded the problem differently but it is the same as the one discussed in this question, however, my doubt is not the same. I understood the problem and I was able to conjecture that $$S_{100} = \frac{2^{100} - 1}{3}$$ Then, the author of the book where I found the problem says that this can be easily proved through induction but I can't figure out how and would appreciate any help.

Thanks in advance.

Edit: Huge thanks to Rob Pratt for his solution, but I finally came up with the proof by induction I was looking for. I am posting it here in case anyone ever has the same doubt I had.

Assume that for all $k \le n$ such that $k \equiv 4 \mod{6}$ (As well, assume $n \equiv 4 \mod{6}$) $$S_{k,0} = S_{k,1} = S_{k,2} - 1 \text{ and } S_{k,1} = \frac{2^k - 1}{3}$$ Now, the following facts follow from the definition of the Pascal triangle, for any $m \in \mathbb{N}$ $$\begin{array} SS_{m,0} = S_{m-1,0} + S_{m-1,2} \\ S_{m,1} = S_{m-1,0} + S_{m-1,1} \\ S_{m,2} = S_{m-1,1} + S_{m-1,2} \end{array}$$ Knowing the above we can deduce the following $$S_{n+6,1} = S_{n+5,0} + S_{n+5,1} = S_{n+4,0} + S_{n+4,2} + S_{n+4,0} + S_{n+4,1} = 2(S_{n+3, 0} + S_{n+3,2}) + S_{n+3,1} + S_{n+3,2} + S_{n+3,0} + S_{n+3,1} = 3(S_{n+2,0}+S_{n+2,2}) + 2(S_{n+2,0}+S_{n+2,1}) + 3(S_{n+2,1} + S_{n+2,2}) = 5(S_{n+1,0}+S_{n+1,2}) + 6(S_{n+1,1} + S_{n+1,2}) + 5(S_{n+1,0}+S_{n+1,1}) = 10(S_{n,0} + S_{n,2}) + 11(S_{n,1} + S_{n,2}) + 11(S_{n,0} + S_{n,1}) = 21S_{n,0} + 22S_{n,1} + 21S_{n,2}$$

Now let's use our induction hypothesis,

$$S_{n+6,1} = 21S_{n,0} + 22S_{n,1} + 21S_{n,2} = 21S_{n,1}+ 22S_{n,1}+21(S_{n,1} + 1) = 64S_{n} + 21 = \frac{2^{n+6} - 64}{3} + 21 = \frac{2^{n+6}-1}{3}$$

So our proof is concluded.

Answer 1

Let $\omega =\exp(2\pi i/3)$ be the primitive cube root of unity. Because $$\frac{1+\omega^k+\omega^{2k}}{3}=\begin{cases}1&\text{if $3 \mid k$}\\0&\text{otherwise}\end{cases}$$ we have $$\sum_k a_{3k} = \sum_k a_k \frac{1+\omega^k+\omega^{2k}}{3}.$$ Now take $$a_k=\binom{n}{k+1}$$ and apply the binomial theorem to each of the resulting three sums to obtain \begin{align} S_n &= \sum_{k \ge 0} \binom{n}{3k+1} \\ &= \sum_{k \ge 0} \binom{n}{k+1}\frac{1+\omega^k+\omega^{2k}}{3} \\ &= \frac{1}{3}\sum_{k \ge 0} \binom{n}{k+1} + \frac{1}{3}\sum_{k \ge 0}\binom{n}{k+1} \omega^k + \frac{1}{3}\sum_{k \ge 0}\binom{n}{k+1} \omega^{2k} \\ &= \frac{1}{3}\sum_{k \ge 1} \binom{n}{k} + \frac{1}{3\omega}\sum_{k \ge 1} \binom{n}{k}\omega^k + \frac{1}{3\omega^2}\sum_{k \ge 1} \binom{n}{k}(\omega^2)^k \\ &= \frac{1}{3}(2^n-1) + \frac{1}{3\omega}((1+\omega)^n-1) + \frac{1}{3\omega^2}((1+\omega^2)^n-1) \\ &= \frac{1}{3}(2^n-1) + \frac{\omega^2}{3}((-\omega^2)^n-1) + \frac{\omega}{3}((-\omega)^n-1). \end{align} The last two terms cancel when $n\equiv 4 \pmod6$, leaving $(2^n-1)/3$.