# How do I prove this combinatorial identity

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 + \cdots + {2n+1 \choose n-1}x^{n-1} + {2n+1 \choose n}x^n +\cdots + {2n+1 \choose 0}x^{2n +1} \\ = {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} + \\ + {2n+1 \choose n}x^{n+1} +\cdots + {2n+1 \choose 0}x^{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?

• The two functions are not equal. In general for rational expressions, ie fractions where numerator and denominator are polynomials, if $a(x)/b(x)=c(x)/d(x)$ for all $x$ (ie expressions are identical), then you must have the polynomial equality $a(x)d(x)=b(x)c(x)$ which is only true if the two products are the same polynomial. If both fractions, $a(x)/b(x)$ and $c(x)/d(x)$, are without common factors, this is only true if $a(x)=k\cdot c(x)$ and $b(x)=k\cdot d(x)$ for some constant $k$. – Einar Rødland Apr 25 '19 at 6:43
• Noted! Thanks for the explanation! – Icycarus Apr 25 '19 at 6:46

## 3 Answers

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

• How did you get to the process of the answer? The way that you thought of the answer is quite a unique way and I was wondering if you can share how you managed to think about this solution – Icycarus Apr 25 '19 at 6:42
• @Icycarus The LHS has a fixed lower index and changing upper index. This reminded me of the Hockey stick identity, whose proof involves conditioning on where the largest element of a subset lies. Since there was a $3^{i}$ afterwards, I figured ternary sequences had to be involved somehow. – Mike Earnest Apr 25 '19 at 6:47
• @Icycarus The method of counting combinatorial objects is called 'combinatrial proof'. Most of math taught in school is concerned with manipulating algebraic structures; combinatorial identities are actually intended to be mapped to ... let's say somewhat real-world arrangements of objects. And the kind of proof used here involves manipulation of those arrangements rather than straight algebra. You'll get the feel for it with some much more basic identity proofs. There's often an 'easy' map from algebraic op to combinatorial op. – Mitch Apr 25 '19 at 12:51

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