Preventing "proof by homework"?

Question

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?)

Answer 1

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.)

Answer 2

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!

Answer 3

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.