How do I proof this combinatorial identity
5
1
$begingroup$
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) ...