When is it "appropriate" to prove a statement using induction?

Question

I know the question is broad, but I am just starting to get my hands dirty with mathematical proofs. I understand that in some cases, a "direct" proof may be appropriate if we are simply going step-by-step in a definition-type question.

In other cases, I've found that that proofs by contradiction may be the "easiest" way to go, such as in some linear algebra proofs I've seen.

However, I'm now looking at combinatorial proofs, and notice that something relatively simple such as the proof that $1+2+3+...+n=\frac{(n)(n+1)}{2}$ uses induction - where if we show that it holds when $n=1$, and we assume that it holds when $n=k$, we can reach the desired result.

My question is as follows - is this considered a "weak" argument by any means because of the fact that we are assuming some fact to be true? I still have in my mind the old adage "You know what happens when you assume.." Does this same concern generally hold for mathematical proofs?

Answer 1

Three points:

1. As Matthew L. says, there is no such thing as "the" proof of your equation -- it is provable in many ways. Here's a non-inductive one: consider $$\ 1\ \ \ +\ \ 2 \ \ \ +\ \ \ 3\ \quad+ \ldots + n$$ $$n + (n-1) + (n-2) + \ldots + 1$$ Add those two vertically and we get $$(n +1) + (n +1) + (n +1) + \ldots + (n +1)$$ So twice the sum of the first $n$ numbers is, trivially, $n(n + 1)$. QED
2. Suppose you want to prove by induction that (C) for all $n$, $Pn$ (for some numerical property $P$). This involves proving that (A) $P1$ (usually trivial) and proving that (B), for any $j$, if $Pj$ then $P(j + 1)$ (or, if you like, proving that if we assume $Pj$ we can deduce $P(j + 1)$). There are no undischarged mere assumptions here!
3. For more on induction and why (A) and (B) give you a proof of (C) -- and for much more on how to start getting your hands dirty with mathematical proofs -- it is difficult to recommend the following too highly, which you should find in any library:

   Daniel J. Velleman How to Prove It (CUP)