# prove by induction...alittle lost

Printable View

• Sep 10th 2008, 10:23 AM
jonbob81
prove by induction...alittle lost
hi,

can anyone explain these steps to me? im abit lost? especially step 2 and 3

Exercise 4(c) To prove that 3^n > n^2, i.e., 3^n − n^2 > 0, using proof
by induction, we first check it for n = 1: i.e., 3^1 = 3 > 1^2 = 1 . X
Inductive step: now assume it is true for n = k, i.e.,

solution
assume that
3k − k^2 > 0. For n = k + 1

3^k+1 − (k + 1)^2 = 3 × 3^k − (k + 1)^2

= 3(3^k − k^2 + k^2) − (k + 1)^2 [2]

= 3(3^k − k^2) + 3k^2 − k2 − 2k − 1 [3]

= 3(3^k − k^2) + k^2 + k^2 − 2k − 1

= 3(3^k − k^2) + k^2 + (k − 1)2 − 2
• Sep 10th 2008, 10:30 AM
Plato
Assume that $k > 1\,\& \,3^k > k^2$.
Then $3^{k + 1} = \left( 3 \right)3^k > 3k^2 \ge k^2 + 2k + 1 = \left( {k + 1} \right)^2$
• Sep 10th 2008, 02:05 PM
jonbob81
hey Plato,

thanks for the reply,

one thing on line [2] how does

3x3^k become 3(3^k − k^2 + k^2) ??
• Sep 10th 2008, 02:22 PM
Plato
Quote:

Originally Posted by jonbob81
3x3^k become 3(3^k + k^2 + k^2) ??

$k > 1\,\& \,2k^2 > 2k + 1$
$3k^3 = k^3 + 2k^3 > k^3 + 2k^2 > k^2 + 2k + 1$