Is there some way to prove $n\binom nr=(r+1)\binom n{r+1}+r\binom nr$ using generating functions?

Question

I have to prove that $$n{n\choose{r}}=(r+1){n\choose{r+1}}+r{n\choose{r}}$$ I can prove this combinatorially as follows, we have $n$ people, we want to choose $r$ people and a leader who could be within the $r$-group or outside the $r$-group but among the $n$ people. The number of such possible groups is obviously $n{n\choose{r}}$. Or we could simply choose $r+1$ people for the case when the leader is not within the group and then among them I can choose one of those $(r+1)$ to be the leader (which accounts for the $(r+1){n\choose{r+1}}$) and for the cases when the leader is withing the group, I choose $r$ people and then among those $r$ people I choose one of them as the leader (which accounts for the $r{n\choose{r}}$). But I am curious if there is a proof using generating functions. I am new to using generating functions and even a hint would help (if the solution is possible) because I am just not getting how to begin.

Answer 1

Another variation with generating functions is based upon the coefficient of operator $[x^r]$ which denotes the coefficient of $x^r$ of a series. This way we can write for instance \begin{align*} \binom{n}{r}=[x^r](1+x)^n\tag{1} \end{align*} Given a generating function $A(x)$ we have \begin{align*} A(x)&=\sum_{j=0}^\infty a_j x^j\qquad\qquad A^{\prime}(x)=\sum_{j=0}^\infty ja_jx^{j-1} \end{align*} from which we derive by comparing coefficients \begin{align*} r a_r&=\color{blue}{r[x^r]A(x)=[x^{r-1}]A^{\prime}(x)}\tag{2} \end{align*}

Equipped with (1) and (2) we obtain starting with the right-hand side of OPs identity \begin{align*} \color{blue}{(r+1)}&\color{blue}{\binom{n}{r+1}+r\binom{n}{r}}\\ &=(r+1)[x^{r+1}](1+x)^n+r[x^r](1+x)^n\tag{3}\\ &=[x^r]n(1+x)^{n-1}+[x^{r-1}]n(1+x)^{n-1}\tag{4}\\ &=[x^r]n(1+x)^{n-1}+[x^r]xn(1+x)^{n-1}\tag{5}\\ &=n[x^r](1+x)^{n-1}(1+x)\tag{6}\\ &=n[x^r](1+x)^n\\ &\,\,\color{blue}{=n\binom{n}{r}}\tag{7} \end{align*} and the claim follows.

Comment:

• In (3) we apply (1) twice.

• In (4) we apply (2) twice.

• In (5) we use the rule $[x^p]x^qA(x)=[x^{p-q}]A(x)$.

• In (6) we use the linearity of the coefficient of operator.

• In (7) we select the coefficient of $x^r$.

Note: When looking for an algebraic proof besides the combinatorial one which you already gave, we can also go the easy way by recalling the binomial identity \begin{align*} \color{blue}{(r+1)\binom{n}{r+1}}&=(r+1)\frac{n(n-1)\cdots(n-r+1)(n-r)}{(r+1)r\cdots 2\cdot 1}\\ &=\frac{n(n-1)\cdots(n-r+1)}{r(r-1)\cdots2\cdot 1}(n-r)\\ &\,\,\color{blue}{=\binom{n}{r}(n-r)} \end{align*} to derive \begin{align*} (r+1)\binom{n}{r+1}+r\binom{n}{r}=(n-r)\binom{n}{r}+r\binom{n}{r}=n\binom{n}{r} \end{align*}

Answer 2

There are several generating function approaches.

We could take the generating function of both sides with respect to $r$, and try to prove that $$ \sum_{r \ge 0} \left(n \binom nr\right) x^r = \sum_{r \ge 0} \left((r+1) \binom{n}{r+1} + r \binom nr\right)x^r. $$ To prove this, we want closed forms for both sides, which start with the generating function $$ (1+x)^n = \sum_{r \ge 0} \binom nr x^r. $$ On the left, this generating function is only multiplied by a constant (independent of $r$); on the right, the $r^{\text{th}}$ term of the sum is multiplied by $r$, which requires taking some derivatives.

We could theoretically also take the generating function of both sides with respect to $n$, but that generating function doesn't have a nice closed form.

Finally, we could take the bivariate generating function of both sides with respect to $r$ and $n$. This requires starting with $$ \sum_{n \ge 0} \sum_{r\ge 0} \binom nr x^r y^n = \sum_{n \ge 0}(1+x)^n y^n = \frac{1}{1-(1+x)y}. $$ Then we need to take some derivatives with respect to $x$ or with respect to $y$ to transform this into the generating function for $n \binom nr$, or $r \binom nr$, or $(r+1)\binom n{r+1}$. Once we've done that, we can prove the identity you want by proving that it holds for the corresponding generating functions.