# Induction help

• Jun 22nd 2010, 11: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.

$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) $k + 1 <= 3^k +1$
is the equation $3^k + 3^k$ a simplification of the RHS of the above equation (1)?
how do we get $3^k + 3^k$ from $3^k +1$ ??

thanks for any help.
• Jun 22nd 2010, 11: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.

$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) $k + 1 <= 3^k +1$
is the equation $3^k + 3^k$ a simplification of the RHS of the above equation (1)?
how do we get $3^k + 3^k$ from $3^k +1$ ??

thanks for any help.

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

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