# Induction help

• Jun 22nd 2010, 10:00 PM
dunsta
Induction help
I understand the rules of prooving by induction, but I can't understand the math in this equation.
If someone could explain what is happening at each step I would be very thankful.

\$\displaystyle k + 1 <= 3^k +1 <= 3^k + 3^k = 2.3^k <= 3.3^k = 3^k^+^1\$

The way I do math is down the page not across
1)\$\displaystyle k + 1 <= 3^k +1\$
is the equation \$\displaystyle 3^k + 3^k\$ a simplification of the RHS of the above equation (1)?
how do we get \$\displaystyle 3^k + 3^k\$ from \$\displaystyle 3^k +1\$ ??

thanks for any help.
• Jun 22nd 2010, 10:33 PM
Hello dunsta
Quote:

Originally Posted by dunsta
I understand the rules of prooving by induction, but I can't understand the math in this equation.
If someone could explain what is happening at each step I would be very thankful.

\$\displaystyle k + 1 <= 3^k +1 <= 3^k + 3^k = 2.3^k <= 3.3^k = 3^k^+^1\$

The way I do math is down the page not across
1)\$\displaystyle k + 1 <= 3^k +1\$
is the equation \$\displaystyle 3^k + 3^k\$ a simplification of the RHS of the above equation (1)?
how do we get \$\displaystyle 3^k + 3^k\$ from \$\displaystyle 3^k +1\$ ??

thanks for any help.

If \$\displaystyle k\ge0\$, then:
\$\displaystyle 3^k \ge 1\$

\$\displaystyle \Rightarrow 1 \le 3^k\$
So if we add \$\displaystyle 3^k\$ to both sides of this inequality:
\$\displaystyle 3^k+1\le3^k+3^k\$
But
\$\displaystyle 3^k+3^k=2.3^k\$
So
\$\displaystyle 3^k+1\le2.3^k\$
And obviously
\$\displaystyle 2<3\$
So
\$\displaystyle 3^k+1\le3.3^k\$
And
\$\displaystyle 3.3^k=3^{k+1}\$
So
\$\displaystyle 3^k+1\le3^{k+1}\$
OK now?