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$
  • $\begingroup$ For some basic information about writing math at this site see e.g. here, here, here and here. $\endgroup$ – user137731 Nov 16 '14 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$ – Mike Nov 16 '14 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$ – user137731 Nov 16 '14 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$ – Mike Nov 16 '14 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$ – Mike Nov 16 '14 at 19:48
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$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.