1
$\begingroup$

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.

$\endgroup$
6
  • $\begingroup$ For some basic information about writing math at this site see e.g. here, here, here and here. $\endgroup$ Commented Nov 16, 2014 at 19:36
  • $\begingroup$ 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. $\endgroup$ Commented Nov 16, 2014 at 19:40
  • 1
    $\begingroup$ 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}$. $\endgroup$ Commented Nov 16, 2014 at 19:42
  • 1
    $\begingroup$ 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. $\endgroup$ Commented Nov 16, 2014 at 19:43
  • 1
    $\begingroup$ 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. $\endgroup$ Commented Nov 16, 2014 at 19:48

1 Answer 1

Reset to default
1
$\begingroup$

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.

$\endgroup$
0

You must log in to answer this question.

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.