MHB Evaluating $(-1)^k {3n \choose k}$ Sums

[lfdahl]

Evaluate the sum:

$$S_n =\sum_{k=0}^{n}(-1)^k{3n \choose k}, \;\;\;n=1,2,...$$

 

[lfdahl]

Hint:

Spoiler

Use Pascal´s triangle.

 

[lfdahl]

Binomial Sum

Suggested solution:

Spoiler

Pascal´s triangle is constructed by the relation:

\[\binom{n}{k} = \binom{n-1}{k-1}+\binom{n-1}{k}\]

Using this in our expression yields a telescoping sum:

\[S_n = \sum_{k=0}^{n}(-1)^k\left ( \binom{3n-1}{k-1}+\binom{3n-1}{k} \right ) \\\\ =\binom{3n-1}{-1}+\binom{3n-1}{0}-\binom{3n-1}{0}-\binom{3n-1}{1}+\binom{3n-1}{1}+...+(-1)^n\binom{3n-1}{n} \\\\ = (-1)^n\binom{3n-1}{n}\]

- where I have used the definition \[\binom{m}{-1} = 0, \forall m \in \mathbb{Z}.\] for the first term in the sum.