Ttyjukl

Show that ${2n choose n} + 3{2n-1 choose n} + 3^2{2n-2 choose n} + cdots + 3^n{n choose n} \ = {2n+1 choose n+1} + 2{2n+1 choose n+2} + 2^2{2n+1 choose n+3} + cdots + 2^n{2n+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) = frac{1}{(1-3x)} \ = 1 + 3^1x + 3^2x^2 + 3^3x^3 + cdots + 3^nx^n + cdots \ f_2(x) = frac{1}{(1-x)^{n+1}} \ = {n choose n} + {n+1 choose n}x + {n+2 choose n}x^2 + cdots + {2n-1 choose n}x^{n-1} + {2n choose n}x^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-1}x^{n-1} + 2^nx^n + cdots \ f_4 (x) = (1+x)^{2n+1} \= 1 + {2n+1 choose 1}x + {2n+1 choose 2}x^2 + cdots + {2n+1 choose n-1}x^{n-1} + {2n+1 choose n}x^n \ = {2n+1 choose 2n+1} + {2n+1 choose 2n}x + {2n+1 choose 2n-1}x^2 + cdots + {2n+1 choose n+2}x^{n-1} + {2n+1 choose n+1}x^{n}$$

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 $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$.

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} + 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}
$$
The two are equal.