Please help me understand this proof by induction

[bushra1175]

I don't understand where the circled part came from or how it fits into the proof. its probably really obvious.

 

[pka]

The meaning of the inductive step is this: we assume that for \(k>1\) we know that \(3^k>k\) is true.
So look at, \(3^{k+1}=3\cdot 3^k>3\cdot k=k+k+k>k+1\) because we know that \(k>1\).
So \(3^{k+1}>k+2\)

 

[Dr.Peterson]

I don't understand where the circled part came from or how it fits into the proof. its probably really obvious.

View attachment 23648

To put that part into words: We want at this point to show that [MATH]3^k+1<3^{k+1}[/MATH] in order to prove [MATH]P(k+1)[/MATH]. So we look for a way to relate them. We see that [MATH]3^{k+1} = 3\cdot 3^k[/MATH]; and that is [MATH]3^k+3^k+3^k[/MATH]. So as long as [MATH]1<3^k+3^k[/MATH], we're good. But that is true as long as [MATH]k\ge 0[/MATH], which is true by assumption.

This is typical of induction proofs: You look for a way to relate what you know, P(k), to what you want to show, P(k+1), and if one thing doesn't work, you try another. (Often this will just be a very sloppy approximation!) It isn't generally obvious until after you've written it. The trick is to see that it's true at that point.

 

[JeffM]

I dislike disagreeing with pka, but it is necessary to assume that k is an integer greater than or equal to 1. Otherwise the proposition is left unproved if n = 2.