# How to approach the inductive step in proving statements like $k! \geq 3^{k-2}$

I am having a really hard time grasping proof by induction and struggling to write consitent thorough proofs which use induction.

For example, proving the following

$k! \geq 3^{k-2}$

Now I understand that we first test the base case $k=1$, and see that it holds and then assume that it is true for any $k$, and if we can show it holds for $k+1$, then we would have proven it for all $k>1$.

However, I am really struggling with the inductive step, someone suggested multiplying both sides by $k+1$ leaving $(k+1)! \geq 3^{k-2}(k+1)$ but I still don't see how it helps, surely we should be putting in $k+1$ instead of $k$?

If anyone has any texts I can read or articles I can read to help improve my skills with proof by induction I would really appreciate it, I'm really struggling with it.

• For some basic information about writing math at this site see e.g. here, here, here and here. – user137731 Nov 16 '14 at 19:36
• rb20, I've edited your text so that the formulas come out properly. Click on "edit" to have a look at the source text I entered and see how it's done. Also, you can correct any mistakes I made in editing. However, it will take some time for the edits I made to be approved, so they won't appear immediately for you. – Mike Nov 16 '14 at 19:40
• HINT#1: Your proof of the inductive step should start with "Assume that $k! \ge 3^{k-2}$ for some $k \in \Bbb N$" and should end with "Therefore $(k+1)!\ge 3^{(k+1)-2}$." HINT#2: For proofs of inequalities, instead of trying to get $P_{n+1} \ge Q_{n+1}$, you often just need to get $P_{n+1} \ge \text{something} \ge Q_{n+1}$. – user137731 Nov 16 '14 at 19:42
• In this case, it doesn't work nicely to take $k = 1$ as your base case. You should check it for $k= 1$ and $k = 2$ separately, and then prove that if it's true for some $k \geq 2$, then it's true for $k + 1$. The point is that in this case $k + 1 \geq 3$, and you can use that in your inequality. – Mike Nov 16 '14 at 19:43
• rb20, here is a suggestion. Write down explicitly what you know at level $k$, and what you're trying to prove at level $k + 1$. You can edit that into the question at the bottom, after your original text. – Mike Nov 16 '14 at 19:48

You can see that that the inequality holds for $k=1$. Now lets assume it holds true for some $k>1$.Thus we have $$k!>3^{k-2}$$ multiply both sides by $(k+1)$, $$(k+1)!>=3^{k-2}.(k+1)$$ we know $k>=2$ thus $k+1>=3$, so $3^{k-2}.(k+1)>=3^{k-2}.3=3^{k-1}$ so we get $(k+1)!>=3^{k-1}$.Thus relation holds true for $k+1$ also. As far as books are concerned you can look up the chapter about induction (chapter 2) in the book A Walk Through Combinatorics by Bona. It has examples plus a lot of solved exercises.