Can I get a light hint for this binomial proof?

Question

Consider the geometric series

$$S=1+(1+x)+(1+x)^2+\dots+(1+x)^n$$

(a) Show that $$S=\frac{(1+x)^{n+1}-1}{x}$$

(b) Hence show that

$$S={n+1\choose1}+{n+1\choose2}x+\dots+{n+1\choose r+1}x^r+\dots+{n+1\choose n+1}x^n$$

(c) Hence prove that

$${n\choose r}+{n-1\choose r}+\dots+{r\choose r}={n+1\choose r+1}$$

I have successfully solved parts a) and b). However, I am struggling with c). I can tell it's the hockey stick identity but the thing that's getting me is the hence. How can I use the previous parts to prove it? I just need a little push. Perhaps it has to be a specific binomials relationship. I tried using the definition of symmetry but that didn't work.

Answer 1

Hint: What is the coefficient of $ x^r$ in $S$?
Answer that in 2 different ways using part b.

Answer 2

Another way to do: Note $$S=1+(1+x)+(1+x)^2+\dots+(1+x)^n. \tag1$$ Multiplying (1) by $1+x$ gives $$(1+x)S=(1+x)+(1+x)^2+(1+x)^3+\dots+(1+x)^{n+1}.\tag2$$ Now using (1) to subtract (2) will give the answer.

Answer 3

(A) Ok so from $S=1+(1+x)+(1+x)^2+\dots+(1+x)^n$, consider the coefficient of $x^r$, which gives the following ways: ${ 0 \choose r} + { 1 \choose r } + { 2 \choose r} + \ldots { n \choose r} = 0 + 0 + ... + 0 + { r \choose r } + { r+1 \choose r } + { r+2 \choose r} + \ldots + { n \choose r }$ ie. the LHS of what we want to prove in part (c).

(B) Also, the coefficient of $x^r$ from $ S={n+1\choose1}+{n+1\choose2}x+\dots+{n+1\choose r+1}x^r+\dots+{n+1\choose n+1}x^n $ gives ${n+1\choose r+1}$. Equating coeffiecnts with (A) gives $ {n\choose r}+{n-1\choose r}+\dots+{r\choose r}={n+1\choose r+1} $

Calvin's edit: This is exactly it. However, you have skipped several steps (of which were listed out in the problem), so I still am unable to fully determine if you truly understand what is happening, or have skipped through those parts.

---

(C) OR the part which I am getting wrong: from $ S=\frac{(1+x)^{n+1}-1}{x} $ to get the coefficient of $x^r$ consider $(1+x)^{n+1}-1$. It would be ${n+1\choose {r}}x^r -1$. But since there is and $x$ in the denominator, it needs to be $ \frac{{n+1\choose {r+1}}x^{r+1} -1}{x} = {n+1\choose {r+1}}x^{r} - x^{-1}$. Then equating coefficients of $x^r$ from (A) also gives $ {n\choose r}+{n-1\choose r}+\dots+{r\choose r}={n+1\choose r+1} $

Calvin's edit: This part has several errors in logic / reasoning, or at least errors in not writing up exactly what you meant. E.g. to get the coefficient of $x^r$, we would want the coefficient of $ x^{r+1}$ in the numerator.

(C)$_2$: Consider $(1+x)^{n+1}-1$. The general term is ${{n+1}\choose{k}}x^k$ and we want it to be $x^r$. But we can't sub that in straight away since the full statement is $S=\frac{(1+x)^{n+1}-1}{x}$. Therefore from ${{n+1}\choose{k}}x^k$

${{n+1}\choose{k}}x^k$ --> ${{n+1}\choose{k}}x^k -1$ --> $\frac{{{n+1}\choose{k}}x^k -1}{x}$ --> ${{n+1}\choose{k}}x^{k-1} - x^{-1}$

and then $k - 1 = r$ so ${n+1\choose r+1}x^r - x^{-1}$

Calvin's edit:

• No, the general term is not ${n+1 \choose k } x^k$. Check $k= 0 $.
• I do not know what you mean by "we want (the general term) to be $x^r$". AFAIK "We want to find the coefficient of the $x^r$ term". This is a distinction that you don't seem to be making.
• You seem to be claiming that $(1+x)^{n+1} - 1 = {n+1 \choose k } x^k -1$. This is not true. Please explain what you are thinking.
• The goal of this part is to show that the coefficient of $ \frac{ ( 1 + x) ^ {r+1} - 1 }{ x} $ is ${n+1 \choose r+1}$. You skipped showing in part (B), and claimed that you know why it's true.