How do I prove this combinatorial identity

Here is a combinatorial proof. Both sides of the equation answer the following question:

How many sequences are there of length $2n+1$, with entries in $\{0,1,2\}$, such that

• at least one of the entries is a $2$, and
• there are exactly $n$ zeroes to the left of the leftmost $2$?

LHS:

Suppose the leftmost $2$ occurs in spot $k+1$. Among the $k$ spots before hand, you must choose $n$ of the entries to be zero. The $2n+1-(k+1)=2n-k$ spots afterward can be anything. There are $\binom{k}n3^{2n-k}$ ways to do this. Then sum over $k$.

RHS:

Suppose there are $j$ entries which are equal to $0$ or $2$. Choose those entries which are equal to $0$ or $2$ in $\binom{2n+1}j$ ways. The leftmost $n$ of these entries must be zero, the $(n+1)^{st}$ entry must be two, then the remaining $j-(n+1)$ entries can be chosen freely among $0$ and $2$. There are $\binom{2n+1}{j}2^{j-(n+1)}$ ways to do this, then sum over $j$.

We seek to show that

$$\sum_{q=0}^n {2n-q\choose n} 3^q = \sum_{q=0}^n {2n+1\choose n+1+q} 2^q.$$

We have for the LHS

$$\sum_{q=0}^n {2n-q\choose n-q} 3^q = \sum_{q=0}^n 3^q [z^{n-q}] (1+z)^{2n-q} \\ = [z^n] (1+z)^{2n} \sum_{q=0}^n 3^q z^q (1+z)^{-q}.$$

The coefficient extractor controls the range and we obtain

$$[z^n] (1+z)^{2n} \sum_{q\ge 0} 3^q z^q (1+z)^{-q} = [z^n] (1+z)^{2n} \frac{1}{1-3z/(1+z)} \\ = [z^n] (1+z)^{2n+1} \frac{1}{1-2z}.$$

We could conclude at this point by inspection. Continuing anyway we get for the RHS

$$\sum_{q=0}^n {2n+1\choose n-q} 2^q = \sum_{q=0}^n 2^q [z^{n-q}] (1+z)^{2n+1} \\ = [z^n] (1+z)^{2n+1} \sum_{q=0}^n 2^q z^q.$$

The coefficient extractor once more controls the range and we obtain

$$[z^n] (1+z)^{2n+1} \sum_{q\ge 0} 2^q z^q = [z^n] (1+z)^{2n+1} \frac{1}{1-2z}.$$

The two generating functions are the same and we have equality for LHS and RHS.

Using your functions, consider $$ 3^n f_2(\frac13) = 3^n \frac{1}{(1-\frac13)^{n+1}} = \frac32 (\frac92)^n\\ = {n \choose n}3^n + {n+1 \choose n}3^{n-1} + \cdots + {2n \choose n} + {\color{red}{ {2n +1 \choose n} 3^{-1}+ \cdots}} $$ and further $$ 2^n f_4 (\frac12) = 2^n (\frac32)^{2n+1} = \frac32 (\frac92)^n \\= {2n+1 \choose 2n+1}2^n + {2n+1 \choose 2n}2^{n-1} + \cdots + {2n+1 \choose n+1} + {\color{red}{ {2n +1 \choose n} 2^{-1}+ \cdots + {2n +1 \choose 0} 2^{-n-1}}} $$ The two expressions both equal $\frac32 (\frac92)^n$, and the first $n+1$ many terms represent the LHS and RHS of the original question. The terms in red are extra terms: once it is established that these terms also equal, the questions is solved. That is, show that $$ \sum_{k=1}^{\infty}{2n +k \choose n} 3^{-k} = \sum_{k=1}^{n+1}{2n +1 \choose n+1-k} 2^{-k} $$