# Mathematical Induction

• Mar 13th 2010, 07:13 PM
bearej50
Mathematical Induction
Prove that 1 + 3n ≤ 4n , for every integer n ≥ 0.

• Mar 13th 2010, 07:23 PM
Jhevon
Quote:

Originally Posted by bearej50
Prove that 1 + 3n ≤ 4n , for every integer n ≥ 0.

Where did you get stuck? This one was not that difficult. I'll just give the solution. It doesn't work for zero, you can check this.

Define a statement $\displaystyle P(n)$ by $\displaystyle P(n):~~1 + 3n \le 4n$ for all integers $\displaystyle n \ge 1$

We show that $\displaystyle P(n)$ is true using mathematical induction.

Since $\displaystyle 1 + 3(1) = 4 \le 4(1)$, we have that $\displaystyle P(1)$ is true.

Assume that $\displaystyle P(n)$ is true, we show that $\displaystyle P(n + 1)$ holds also.

Note that,

$\displaystyle \begin{array}{rcl} 1 + 3(n + 1) & = & 1 + 3n + 3 \\ & \le & 4n + 3 \\ & \le & 4n + 4 \\ & = & 4(n + 1) \end{array}$

So that $\displaystyle 1 + 3(n + 1) \le 4(n + 1)$, which is $\displaystyle P(n + 1)$. Thus, $\displaystyle P(n)$ holds by induction.