"I think it would be worthwhile to explicitly ca..."


by Eric Rogstad Jul 18 2016

We'll do an example to build our intuition before giving the proper definition of the principle\. We'll provide yet another proof that $$~$ 1 + 2 + \\cdots + n \= \\frac{n(n+1)}{2}$~$$ for all integers $~$n \\ge 1$~$\. First, let's check the base case, where $~$n\=1$~$: $$~$ 1 \= \\frac{1(1+1)}{2} \= \\frac{2}{2} \= 1.$~$$ This is \(fairly obviously\) true, so we can move forward with the inductive step\. The inductive step includes an assumption, namely that the statement is true for some integer $~$k$~$ that is larger than the base integer\. For our example, if $~$k\\ge1$~$, we assume that $$~$1 + 2 + \\cdots + k \= \\frac{k(k+1)}{2}$~$$ and try to prove that $$~$ 1 + 2 + \\cdots + k + (k+1) \= \\frac{(k+1)(\[k+1\]+1)}{2}.$~$$ Take our assumption and add $~$k+1$~$ to both sides: $$~$1+2+\\cdots + k + (k+1) \= \\frac{k(k+1)}{2} + k + 1.$~$$ Now the left\-hand sides of what we know and what we want are the same\. Hopefully the right\-hand side will shake out to be the same\. Get common denominators so that the right\-hand side of the above equation is $$~$\\frac{k(k+1)}{2} + \\frac{2(k+1)}{2} \= \\frac{(k+2)(k+1)}{2} \= \\frac{(k+1)(\[k+1\]+1)}{2}.$~$$ Therefore, $$~$ 1 + 2 + \\cdots + k + (k+1) \= \\frac{(k+1)(\[k+1\]+1)}{2}$~$$ as desired\.

I think it would be worthwhile to explicitly call out that what's happening here is that we're replacing $~$n$~$ in the original equation with $~$k+1$~$.