The pattern in mathematical induction proofs

Question

When given a statement to be proven by mathmatical induction the statement tends to look like this

$1 + 2 + 3 + \dots + n = \frac{n(n+1)}{2}$

so going about the proof.

1) Prove the base case

$\frac{1\times(1+1)}{2} = 1$

2) Prove the inductive case

Assume

$1 + 2 + 3 + \dots + n = \frac{n(n+1)}{2}$

Now add $n+1$ to both sides of the equation.

\begin{align} 1 + 2 + 3 + \dots + n + (n + 1) & = \frac{n(n+1)}{2} + (n + 1) \\ & = \frac{n(n+1)}{2} + \frac{2(n+1)}{2} \\ & = \frac{(n + 1)(n + 2)}{2} \\ & = \frac{(n + 1)((n + 1) + 1)}{2} \end{align}

Thus the proof is complete. Now my question is, can we just remove the $1 + 2 + 3 + \dots + n$ side of the equation, and put anything there? for example, if we used $f(n)$, Then the proof would look like this.

1) Prove the base case

$f(1) = \frac{1\times(1+1)}{2} = 1$

2) Prove the inductive case

Assume

$f(n) = \frac{n(n+1)}{2}$

Now add $n+1$ to both sides of the equation.

\begin{align} f(n) + (n + 1) & = \frac{n(n+1)}{2} + (n + 1) \\ & = \frac{n(n+1)}{2} + \frac{2(n+1)}{2} \\ & = \frac{(n + 1)(n + 2)}{2} \\ & = \frac{(n + 1)((n + 1) + 1)}{2} \end{align}

Thus we now know $f(n) = \frac{n(n+1)}{2}$. But what pattern represents $f(n)$? it's not immediately obvious that $f(n)$ is the sum of the first $n$ positive integers.

Answer 1

You are making the assumption that $f(n) = \text{ sum of the first } $n$ \text{ integers}$ during your induction. When you evaluate $f(1)$ you make this assumption in how you evaluate. And in your induction step you mean to assert: $$f(n+1) = f(n) + (n+1)$$

before going on with your proof. Implicit in this assumption is a recursive definition of $f$ that forces $f$ to be the sum of the first $n$ integers. That is, there is exactly one function on the natural numbers such that $f(1) = 1$ and $f(n+1) = f(n) + (n+1)$, and that function is the one that sums the first $n$ integers. Indeed there are many ways to define this function, i.e. $f(n) = n(n+1)/2$, but you can prove that they are all the same function.

Answer 2

The general theorem of mathematical induction goes like this:

Suppose that "$\Phi$" is a proposition involving the variable "n". Actually let's call the proposition $\Phi(n)$, and agree that whenever we write "$\Phi(\text{something})$" the reader is meant to substitute the "something" in for $n$. If $\Phi(0)$ holds, and if $\Phi(n+1)$ holds whenever $\Phi(n)$ holds, then we may conclude that $\Phi(n)$ holds for all $n$.

We can express this more precisely using quantifiers. With the same setup, here is what induction says: $$ \Phi(0)\text{ and }(\forall k\in\mathbb{N}\ |\ \Phi(k)\Rightarrow \Phi(k+1))\ \ \ \ \Longrightarrow\ \ \ \ \ (\forall n\in\mathbb{N}\ |\ \Phi(n))\ . $$ (The $k$ could just as well be an $n$, but sometimes changing variable naming inside quantifiers helps to avoid confusion).

In the example with which you began your post, the proposition $\Phi(n)$ is $$ 1+2+3+\cdots+n=n(n+1)/2\ . $$ The proposition you do your induction on can really be any proposition! It doesn't need to be an equality.