Otdfbt

Show that

$$2n choose n + 32n-1 choose n + 3^22n-2 choose n + cdots + 3^nn choose n \ = 2n+1 choose n+1 + 22n+1 choose n+2 + 2^22n+1 choose n+3 + cdots + 2^n2n+1 choose 2n+1$$

One way that I did it was to use the idea of generating functions.
For the left hand side expression, I can find 2 functions. Consider;

$$f_1 (x) = frac1(1-3x) \ = 1 + 3^1x + 3^2x^2 + 3^3x^3 + cdots + 3^nx^n + cdots \ f_2(x) = frac1(1-x)^n+1 \ = n choose n + n+1 choose nx + n+2 choose nx^2 + cdots + 2n-1 choose nx^n-1 + 2n choose nx^n + cdots + $$

Consider the coefficient of $x^n$ in the expansion of $f_1 (x) . f_2 (x)$. Then the coefficient will be the expression on the left hand side.

Now we further consider 2 functions for the right-hand side expression.

Consider;

$$f_3 (x) = frac 1(1-2x) \ = 1 + 2^1x + 2^2x^2 + cdots + 2^n-1x^n-1 + 2^nx^n + cdots \ f_4 (x) = (1+x)^2n+1 \= 1 + 2n+1 choose 1x + cdots + 2n+1 choose n-1x^n-1 + 2n+1 choose nx^n +cdots + 2n+1 choose 0x^2n +1 \ = 2n+1 choose 2n+1 + 2n+1 choose 2nx + 2n+1 choose 2n-1x^2 + cdots + 2n+1 choose n+2x^n-1 + 2n+1 choose n+1x^n + \
+ 2n+1 choose nx^n+1 +cdots + 2n+1 choose 0x^2n +1$$

Hence the coefficient of $x^n$ is the coefficient of $x^n$ in the expansion of $f_3(x) . f_4(x)$

This is what I managed to do so far. I'm not sure if $f_1(x) .f_2(x) = f_3(x).f_4(x)$. If the two functions are indeed equal, then I can conclude that their coefficient of $x^n$ must be equal, which will immediately answer the question. If they are equal, how do I show that they are?

If the two functions are not equal? How do I proceed to show this question?

Edit: It might not be true that the product of the two functions are equal. I tried substituting $x=0.1, n=1$. Seems like the two values are not equal. How do I proceed with this question?

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 $binomkn3^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 $binom2n+1j$ 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 $binom2n+1j2^j-(n+1)$ ways to do this, then sum over $j$.

We seek to show that

$$sum_q=0^n 2n-qchoose n 3^q
= sum_q=0^n 2n+1choose n+1+q 2^q.$$

We have for the LHS

$$sum_q=0^n 2n-qchoose 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_qge 0 3^q z^q (1+z)^-q
= [z^n] (1+z)^2n frac11-3z/(1+z)
\ = [z^n] (1+z)^2n+1 frac11-2z.$$

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

$$sum_q=0^n 2n+1choose 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_qge 0 2^q z^q
= [z^n] (1+z)^2n+1 frac11-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 frac1(1-frac13)^n+1 = frac32 (frac92)^n\ = n choose n3^n + n+1 choose n3^n-1 + cdots + 2n choose n + colorred 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+12^n + 2n+1 choose 2n2^n-1 + cdots + 2n+1 choose n+1 + colorred 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^infty2n +k choose n 3^-k = sum_k=1^n+12n +1 choose n+1-k 2^-k
$$