# Mathematical Induction

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

• March 13th 2010, 08: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 $P(n)$ by $P(n):~~1 + 3n \le 4n$ for all integers $n \ge 1$

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

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

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

Note that,

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

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