# The pattern in mathematical induction proofs

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}$

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.

• Your question is very unclear (at least to me). What would be a possible answer to "what pattern represents $f(n)$"? – Matt Samuel Aug 21 '15 at 1:37
• I think it is dangerous of you to assume that any time induction is performed it tends to look like anything. It can take many forms, but at the core is proving a property to exist for an infinite set of objects. – Paddling Ghost Aug 21 '15 at 2:05

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.

• Right. The OP claims we can put any function on the left side, but then puts the same function there and claims it now holds for all functions. – Paddling Ghost Aug 21 '15 at 1:53
• Ok, so $1 + 2 + 3 + \dots + n$ is essentially a different way of expressing the recursive function you mentioned. – Tony Johnson Aug 21 '15 at 2:38

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.