5
$\begingroup$

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.

$\endgroup$
2
  • $\begingroup$ I don't know how the a constant $(n+1)$ from the combinations summation in part b) changes to a descending $n, n-1, n-2...$ $\endgroup$
    – user71207
    Jan 9, 2021 at 13:06
  • $\begingroup$ For future questions, consider writing the problem using MathJax instead of pasting a screenshot. $\endgroup$ Jan 9, 2021 at 13:19

3 Answers 3

5
$\begingroup$

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

$\endgroup$
23
  • 1
    $\begingroup$ What is the coefficient of $x^r$ via the original definition (first equation)? $\endgroup$
    – Calvin Lin
    Jan 10, 2021 at 4:09
  • 2
    $\begingroup$ Looks to me that you're completely missing it. Let me break it down further. What is the coefficient of $x^r$ from $ (1+x)^n$? From $(1+x)^{n-1}$? From $(1+x)^r$? From $(1+x)$? From $1$? Hence, what is the coefficient of $x^r$ in $ S = 1 + (1+x) + \ldots + (1+x)^n$? $\endgroup$
    – Calvin Lin
    Jan 10, 2021 at 4:36
  • 2
    $\begingroup$ You're right that the coefficient is $ { 1 \choose r }$. Recall that for integers $ a < b$, $ { a \choose b } = 0 $ is the way to extend the definition. IE The binomial theorem holds for $ ( x +1) ^n = \sum_{r=0}^\infty { n \choose r } x^r$. In this case, they just dropped those terms. $\endgroup$
    – Calvin Lin
    Jan 10, 2021 at 4:42
  • 2
    $\begingroup$ Do you agree that the coefficient of $x^r$ in $S = 1 + (1+x) + ... $ is $ { 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 } = $ LHS of c)? $\endgroup$
    – Calvin Lin
    Jan 10, 2021 at 4:54
  • 2
    $\begingroup$ A) We're focused on the $ x^r$ term, not the $x^{-1}$ coefficient. B) But even then,What is the constant term in the numerator? Hint: Set $ x = 0 $. $\endgroup$
    – Calvin Lin
    Jan 10, 2021 at 6:01
3
$\begingroup$

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.

$\endgroup$
3
  • $\begingroup$ ahh this also works $\endgroup$
    – user71207
    Jan 10, 2021 at 0:17
  • $\begingroup$ Wait I am confused: I have $xS = (1+x)^{n+1} -1$. Also, $x𝑆=x+x(1+𝑥)+x(1+𝑥)^2+⋯+x(1+𝑥)^𝑛$. Now the coefficient of $x^{r+1}$ of the RHS gives the RHS of what we want to prove in (c). But I'm unable to create a proper series regarding the coefficients on the LHS to match the LHS in (c). $\endgroup$
    – user71207
    Jan 10, 2021 at 9:53
  • $\begingroup$ Compare the coefficients of $x^r$ of $S=\cdots$. $\endgroup$
    – xpaul
    Jan 10, 2021 at 13:19
0
$\begingroup$

(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.
$\endgroup$
6
  • 1
    $\begingroup$ I've left comments in the writeup. In addition, please explain the first sentence of (C) in full gory detail, with as much details as you can add, instead of just presenting your condensed summary of what you're thinking. This is the part that's tripping you up, and you're not correctly keeping tracking of stuff. So, be extremely explicit about what you're doing and why. EG, to get the coefficient of $x^r$, we would actually want the coefficient of $ x^{r+1}$ in the numerator right? $\endgroup$
    – Calvin Lin
    Jan 11, 2021 at 2:36
  • $\begingroup$ Ok I understand the proof regarding (A) and (B) and the steps I skipped were basically what was fleshed out in the comments. Glad that's sorted out. I think the entire time, I was confused as to whether you were proving the RHS by using the part (B) or part (C) method. Now, for (C), I am asking is this a secondary method to complete the proof, or is it redundant. Also, you kept on saying "what is the constant term in the numerator". Why do we care about this if we want it to be the term $x^r$??? Constant term is $x^0$. And I will add some more information $\endgroup$
    – user71207
    Jan 11, 2021 at 2:48
  • 1
    $\begingroup$ I've added comments. Your (A) + (B) is part (c) of the problem, and that's all that is needed. That's exactly what my solution hint was about. $\quad$ Your (C) and (C)2 arise from your confusion. It is not "a secondary method to complete the proof". I believe the error is that you are not truly finding the coefficient of the $x^r$ term (or at least, you may think that you're doing that, but you are not exactly doing it, resulting in errors that are confusing you.) $\endgroup$
    – Calvin Lin
    Jan 11, 2021 at 4:43
  • $\begingroup$ Ah yes "we want (the general term) to be $𝑥^𝑟$. AFAIK We want to find the coefficient of the $𝑥^𝑟$ term" this must have been my mistake. I see that there is no way to prove ${{n+1}\choose{r+1}}$ using$ S=\frac{(1+x)^{n+1}-1}{x} $. Thanks for all your edits, comments, and patience again. (Also sorry I just realized I should've put my working out in my question, not as a separate answer - I forgot about that, silly me!) $\endgroup$
    – user71207
    Jan 12, 2021 at 3:24
  • 2
    $\begingroup$ I disagree with "there is no way to prove ...." -> You "did" this in part (B), BUT skipped stating it (hence my comment). IE The coefficient of $ x^r$ in $ [ ( 1 + x) ^{n+1} - 1 ] / x $ is the coefficient of $x^{r+1} $ in $ ( 1+x)^{n+1} - 1 $. The corresponding term is $ {n+1 \choose r+1 } x^{r+1}$ (NO -1 constant term, we want the $x^{r+1}$ term), so the coefficient is ${n+1 \choose r+1}$. This is why I keep on requesting that you write things out properly and in full, with the hope that you can spot the error in your reasoning. $\endgroup$
    – Calvin Lin
    Jan 13, 2021 at 16:06

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.