I am doing problem 3d in the Prologue of Spivak:

Prove $(a+b)^n = a^n + {n\choose1}a^{n-1}b + {n\choose2}a^{n-2}b^2 + ... + {n\choose n-1}ab^{n-1} + b^n$

I feel like my proof could pass off as acceptable in a number of situations. I am using induction:

Base case 0. $(a+b)^0$ = $1$ which is true.

Now I assume it holds for an arbitrary $k$ the statement will be true if it holds for $k+1$. This is where I have problems because I feel like I'm proving it because the homework says it's true:

$$(a+b)^{n+1} = (a+b)^{n}(a+b)$$ $$(a^n + {n\choose1}a^{n-1}b + {n\choose2}a^{n-2}b^2 + ... + {n\choose n-1}ab^{n-1} + b^n)\times (a+b)$$ (The next step I am only assuming that the statement is true because it was stated in the problem.) $$a^{n+1} + {n+1\choose1}a^{n}b + {n+1\choose2}a^{n-1}b^2 + ... + {n+1\choose n}ab^{n} + b^{n+1}$$

This is what we want hence the statement is true.

Although I feel like depending who I talk to this could be a good enough proof. Is there another way I can represent the series that clearly demonstrates the step I'm "handwaving" is true? (Or at least can I have a hint?)

  • 1
    $\begingroup$ What is "proof by homework", and what do the words " I feel like I'm proving it because the homework says it's true " mean? $\endgroup$ – zyx Apr 11 '14 at 4:04
  • $\begingroup$ @zyx: Proof by homework is when you say: "Theorem X is true because the question says it is." When I put the step about multiplying (a^n + ... b^n) * (a + b) I made it equal to the correct thing. Sure my "proof" is correct, but it was not thorough and I was left unconvinced that multiplying (a^n + ... b^n) by (a + b) actually resulted in a correct expression. $\endgroup$ – Dair Apr 11 '14 at 4:45
  • 3
    $\begingroup$ Hint: the statement is about binomial coefficients $\binom nk$, and obviously cannot remain true is you replace them by some other random set of coefficients. Therefore any proof must use a property of binomial coefficients that sets them apart. Your proposed proof does not, so it cannot be complete. When doing grading, the principle that essential hypotheses must be used somewhere is an easy way to detect bogus proofs without having to go through their (often incomprehensible, though this is not your case) details. $\endgroup$ – Marc van Leeuwen Apr 11 '14 at 6:49
  • $\begingroup$ Sure my "proof" is correct, but it was not thorough Your "proof" is not correct because it depends on the false statement (anything stated as problem is true). $\endgroup$ – Cthulhu Apr 11 '14 at 10:19

You are missing steps. Your last expression is your goal. You need to first distribution $(a+b)$ in the expression before it, collect appropriate terms, and then use an identity to get to the last expression.

(Hint: Use ${n \choose k} + {n \choose k-1} = {n+1 \choose k}$. Make sure to prove this or give a reference to it in your textbook.)

| cite | improve this answer | |
  • $\begingroup$ Ahhh, thanks for reminding me of that fact, yes I did prove it in previous answers. I ended up using a combination of both yours and David's answers. $\endgroup$ – Dair Apr 11 '14 at 2:31

Not entirely clear, but I think that you have just written down the last displayed equation (the one starting with $a^{n+1}$) rather than proving it. You need to explain on the basis of your previous assumptions why this equation is true. Here is one possibility: multiply out to get $$\eqalign{\left(a^n + {n\choose1}a^{n-1}b\right.&\left.{} + {n\choose2}a^{n-2}b^2 + \cdots + {n\choose n-1}ab^{n-1} + b^n\right)(a+b)\cr &=a^{n+1}+\cdots+\left[{n\choose k}+{n\choose k-1}\right]a^{n+1-k}b^k+\cdots+b^{n+1}\cr}$$ and then explain why the term in square brackets is equal to $${n+1\choose k}\ .$$ Good luck!

| cite | improve this answer | |
  • $\begingroup$ Thanks! I wish I could accept both yours and mayrb's answer. :( $\endgroup$ – Dair Apr 11 '14 at 2:32
  • $\begingroup$ Accept one and upvote the other (if you can). $\endgroup$ – marty cohen Apr 11 '14 at 3:17

There is a more basic problem than how to do the induction, which is what definition of $n \choose k$ is used.

It is almost a tautology that the expansion of $(a+b)^n$ is formed by the same rules as Pascal's triangle. If the definition of $n \choose k$ is to take the number at that location in the triangle, the only additional thing to prove is that Pascal's triangle is well defined, which for most purposes is so obvious as to "fly under the radar".

If $n \choose k$ is defined using factorials, all the work is in proving that this matches Pascal's triangle. Then apply the previous paragraph.

If $n \choose k$ is defined as the number of $k$-subsets of an $n$ element set, there is no need for an explicit induction, since there is a natural one-to-one correspondence between terms in the expansion of $(a+b)^n$ and the subsets. The correspondence is easily described and "obviously works" within the discourse conventions of human mathematical communication and proof. In a formal proof system on a computer it might require an overt induction.

| cite | improve this answer | |

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.