5

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.

Jean-Claude Arbaut
  • 23,277
user71207
  • 1,543

3 Answers3

5

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

Calvin Lin
  • 68,864
  • Hmmm so I see the coefficient of $x^r$ is $n+1\choose{r+1}$. This is the right-hand side of what we want to prove. What is the second way? I considered $(x+1)^{n+1}$ and realize that you can split this up into $(x+1)^{n}(x+1)^{1} = (x+1)^{n-1}(x+1)^{2}=...=(x+1)^{n+1}(x+1)^{0}$. This would work, but I don't know where the last $r\choose{r}$ could come from. Is this what you intended? – user71207 Jan 10 '21 at 04:08
  • 1
    What is the coefficient of $x^r$ via the original definition (first equation)? – Calvin Lin Jan 10 '21 at 04:09
  • Oh that would just be $(1+x)^r$ so for coefficient $x^r$ --> $r\choose{r}$. But that's only for $r\choose{r}$?... Perhaps I am a bit confused. What equation are you looking at? The very first ie at the top or the first as in from part a) (first part) – user71207 Jan 10 '21 at 04:18
  • 1
    What is the coefficient of $ x^r$ in $S=1+(1+x)+(1+x)^2+\dots+(1+x)^n$? Which terms would contribute to $x^r$? Sum it up across all such terms. – Calvin Lin Jan 10 '21 at 04:20
  • Would it not be... all the powers from $n$ to $r$? Well, that solves the left-hand side. For the RHS do I use the definition form part a)? By the way, I thought "hence" in part c) meant that I was to use part b) to solve it. Looks like that is not the case – user71207 Jan 10 '21 at 04:32
  • 2
    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$? – Calvin Lin Jan 10 '21 at 04:36
  • Hmm seems so. Thanks for your patience. How can $(1+)$ and $1$ have a coefficient of $x^r$? There is no general term. Even for $(1+)$ it would have to be $1\choose{r}$ which implies that $r≤1$ – user71207 Jan 10 '21 at 04:40
  • 2
    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. – Calvin Lin Jan 10 '21 at 04:42
  • But how does $1\choose{r}$ relate to part c) at all? – user71207 Jan 10 '21 at 04:43
  • 2
    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)? – Calvin Lin Jan 10 '21 at 04:54
  • Oh I see. Yes (I thought $a\choose{b}$ when $a<b$ was undefined but I guess it makes sense that it equals zero. Yes, I see what you are doing now. Then finally you can use the definition in part (a). However, you get ${n+1\choose{r+1}}x^r - x^{-1}$ What shall we do with the $x^{-1}$? – user71207 Jan 10 '21 at 05:14
  • 2
    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 $. – Calvin Lin Jan 10 '21 at 06:01
  • Ahh I see. A) Solved (forgot you could just ignore the rest if you're equating coefficients) B) What? the constant term is zero. What is the significance of the "constant term in the numerator"? – user71207 Jan 10 '21 at 06:14
  • 1
    You are claiming that there is a $x^{-1}$ term. I'm telling you that there isn't. If you think that there is one, please demonstrate why there is one. – Calvin Lin Jan 10 '21 at 12:44
  • Oh. So this was my algebra: for $x^r$, $\frac{{{n+1}\choose{r+1}}x^{r+1} - 1}{x} = {{n+1}\choose{r+1}}x^{r} - x^{-1}$

    Since there is an $x$ in the denominator, we need $r+1$ for the general term to get $x^r$. But then there's also a $x^{-1}$ left?

     – user71207 Jan 10 '21 at 12:49
  • 1
    Read my comments again. A) Why are you bringing $-1 / x$? Or, going back even further, remember that we are comparing coefficients of $x^r$ only. B) What is the constant term of the numerator? Are you sure it is $-1$? Where are you getting that from? – Calvin Lin Jan 10 '21 at 12:51
  • Ok I understand how you went about with the LHS but how did you deal with the RHS? Why are you considering the constant term? How is that related? A) I am just trying to find $x^r$ from
    $S=\frac{(1+x)^{n+1}-1}{x}$ as required for the RHS     – user71207 Jan 10 '21 at 12:58
  • 1
    A) Let me reference your first comment of "Hmmm so I see the coefficient of $x^r$ is ${ n+1 \choose r+1}$. This is the right-hand side of what we want to prove. What is the second way? " B) Again, read my comments. We're focused on the $x^r$ term. What is the constant term of the numerator? Are you sure it is −1? Hint: Set $ x = 0$. – Calvin Lin Jan 10 '21 at 13:00
  • "Hmmm so I see the coefficient of $^$ is ${+1}\choose{+1}$. This is the right-hand side of what we want to prove." Oh that's right. This is the coefficient when you compare $x^r$. Why do we need a second way then? Also when did I say that the constant term of the numerator is $-1$. It would be $0$ – user71207 Jan 10 '21 at 13:09
  • 1
    A) The second way is to give you the LHS of c), which is what we've been talking about. B) You are obsessed over " $({ n+1 \choose r+1} x^ {r+1} - 1 ) / x$. I've been trying to get you to explain where the $-1$ comes from. So, is there a $-1$ term in the numerator if the constant term is 0? C) Please explicitly show your work / thinking, otherwise I can only guess at what's tripping you up, which results mostly in repeating things that I've said till you properly process it. – Calvin Lin Jan 10 '21 at 13:12
  • Ok so all the above comments successfully prove the LHS of (c) right? I follow that. Now I want to prove the RHS. Perhaps my method is wrong: I am taking the definition of $S=\frac{(1+x)^{n+1}-1}{x}$ to find $S = ... x^r$ ie. S = coefficient of $x^r$. A) the $-1$ is right there in the definition. I first considered $(1+x)^{n+1}$ then worked towards$\frac{(1+x)^{n+1}-1}{x}$ which gives me $({ n+1 \choose r+1} x^ {r+1} - 1 ) / x $ – user71207 Jan 10 '21 at 13:23
  • Can you write up exactly what you have in a separate solution, so that I can make edits/references to it? A ) READ ... We're looking for the $x^r$ term. You have given the $x^r$ term in $(1+x)^r$, THEN the $1$ term in $-1$. WHY? If you're concerned about the $1$ term in the numerator, well, what is the $1$ term in the entire numerator? You already told me it is 0 ..... So, from my POV, you have what you need (which is what the hint is meant to do), you just need to ensure you put it correctly together, hence please write up your solution / whatever you have. Otherwise, I'm out of here. – Calvin Lin Jan 10 '21 at 13:29
  • Ok @Calvin Lin I wrote up my working out in a separate answer ( its hard to format in the comments ) – user71207 Jan 11 '21 at 02:08
3

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.

xpaul
  • 44,000
  • ahh this also works – user71207 Jan 10 '21 at 00:17
  • 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). – user71207 Jan 10 '21 at 09:53
  • Compare the coefficients of $x^r$ of $S=\cdots$. – xpaul Jan 10 '21 at 13:19
0

(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.
Calvin Lin
  • 68,864
user71207
  • 1,543
  • 1
    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? – Calvin Lin Jan 11 '21 at 02:36
  • 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 – user71207 Jan 11 '21 at 02:48
  • 1
    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.) – Calvin Lin Jan 11 '21 at 04:43
  • 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!) – user71207 Jan 12 '21 at 03:24
  • 2
    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. – Calvin Lin Jan 13 '21 at 16:06
  • Ahhh that statement clicked for me. Finding the coefficient of $^$ in [(1+)+1−1]/ is the same as finding eh coefficient of $^{+1}$ in$ (1+)^{+1}−1$. I missed that, hence that's why I was erroneously producing a $x^{-1}$ – user71207 Jan 14 '21 at 04:44