4 Example 1

This is a somewhat trivial example. Nonetheless, I hope it helps to illustrate proof by induction. You can find this proof by a search engine.

The predicate, $P(x)$, states that $\sum_{i=1}^{n} i = \frac{n(n+1)}{2}$.

The base case is $P(1)$. $\sum_{i=1}^{1} i = 1$, but $\frac{1(1+1)}{2} = 1$. Therefore, the base case is proven.

Note that our $a = b = 1$ in this case. In other words, we only have one base case.

Next, we need to show that $\forall k \in I: (\forall i \in I: (1 \le i < k) \rightarrow P(i)) \rightarrow P(k)$. In other words, for all $n > 1$, if we know that $P(1), P(2), \cdots P(n-1)$, how can we show that $P(n)$?

Well, $P(n-1)$ means that $\sum_{i=1}^{n-1} i = \frac{(n-1)n}{2}$. Then, we can add $n$ to both sides so that we have $\sum_{i=1}^{n} i = n+\frac{n-1)n}{2}$. The right hand side can be transformed as follows:

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

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

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

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

As a result, $P(n)$ is true.

Note that we only had to make use of the fact that $P(n-1)$ in order to prove that $P(n)$. In other words, we only made use of ordinary induction, but not strong induction.