Prove that 1 + 3n≤ 4n, for every integern≥ 0.

Printable View

- Mar 13th 2010, 07:13 PMbearej50Mathematical InductionProve that 1 + 3
*n*≤ 4*n*, for every integer*n*≥ 0.

- Mar 13th 2010, 07:23 PMJhevon
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.