# Proof by Induction

One way to prove a statement is to check the validity of every  single possible case. We can show a proposition that has many cases to be true by exhausting each possible case. For example:

Proposition : $f(x) = x^2+3$ has no rational roots.

Proof: we can prove that there are no rational roots by using the rational root theorem. According to the theorem the polynomial will have four possible rational roots -1, 1, -3, 3 and we proceed to check all of them.

$f(-1)= -1^2+3 = 4 \neq 0$

$f(1)=1^2+3=4 \neq 0$

$f(-3) = (-3)^2 + 3 = 12 \neq 0$

$f(3) = 3^2 + 3 = 12 \neq 0$

Which means that $f(x) = x^2 + 3$ has no rational roots.

Now the problem with this are statements such as $1+2+3+...+x = \frac{x(x+1)}{2}$ is impossible to do with exhaustion. Although there is direct way of proving this, the fastest way is by induction.

Proof by induction works as follows. We start with statement $P(x)$ where $P$ is the statement and $x$ is the index used. What we do is we prove that $P(x)$ is true for the smallest possible $x$ value what isn’t too obvious. Once that is done we assume that we assume that $P(x)$ is true for $x = n$. $n$ is an arbitrary value. We now must show that $P(x)$ is true for $x = n+1$.

Filed under : Mathematics