Proof of Sum of Trinomial Coeffs = $3^n$

Question

I'm trying to prove that the sum of trinomial coeffs $\sum_{l+k+m=n}^n \binom{n}{l,k,m} = 3^n$.
I tried by induction and got the step as follows:

$$ \begin{split} \sum_{l+k+m=n+1}^{n+1} \binom{n+1}{l,k,m} &= \sum_{l+k+m=n+1}^{n+1}\left[\binom{n}{l-1,k,m} +\binom{n}{l,k-1,m} +\binom{n+1}{l,k,m-1} \right]\\ &= 3^n+3^n+\sum_{l+k+m=n+1}^{n+1} \binom{n}{l,k,m-1}(n+1) \\ &= 3^n+3^n+3^n(n+1) \end{split} $$ Clearly this doesn't add up. I'm not sure if I'm going in the right direction or if the last step with the trinomial is even correct.

In addition, is it correct to even say $\sum_{l+k+m=n+1}^{n+1}\binom{n}{l-1,k,m}=3^n$, I thought so because it is equivalent to choosing three numbers whose sum is n.
Edit: My problem with the last equation is that $0 \leq k,l,m \leq n+1$, which means that $k-1, l-1, m-1$ may be equal to $-1$, which -I assume- will disturb the sum.

Answer 1

Your $\binom{n+1}{l,k,m-1}$ should instead be $\binom{n}{l,k,m-1}$. After you correct that, you end up with $3^n+3^n+3^n=3^{n+1}$, as desired.

---

The induction hypothesis is $$\sum_{\substack{k \ge 0, l \ge 0, m \ge 0:\\ k+l+m=n}} \binom{n}{k,l,m} = 3^n$$ Now \begin{align} \sum_{\substack{k \ge 0, l \ge 0, m \ge 0:\\ k+l+m=n+1}} \binom{n+1}{k,l,m} &= \sum_{\substack{k \ge 0, l \ge 0, m \ge 0:\\ k+l+m=n+1}} \left( \binom{n}{k-1,l,m} +\binom{n}{k,l-1,m} +\binom{n}{k,l,m-1} \right) \\ &= 3 \sum_{\substack{k \ge 0, l \ge 0, m \ge 0:\\ k+l+m=n+1}} \binom{n}{k-1,l,m} \\ &= 3 \sum_{\substack{k \ge 1, l \ge 0, m \ge 0:\\ k+l+m=n+1}} \binom{n}{k-1,l,m} \\ &= 3 \sum_{\substack{k-1 \ge 0, l \ge 0, m \ge 0:\\ k-1+l+m=n}} \binom{n}{k-1,l,m} \\ &= 3 \sum_{\substack{j \ge 0, l \ge 0, m \ge 0:\\ j+l+m=n}} \binom{n}{j,l,m} \\ &= 3 \cdot 3^n \\ &= 3^{n+1} \end{align}

Answer 2

The standard proof for binomial coefficients is to consider $(1 + 1)^n$.

First, see the start of this article.

Then, simply consider $(1 + 1 + 1)^n.$