2
$\begingroup$

One of the topics of my algebra subject is Proof by Induction. When it comes to proving equalities, whether they are a series, factorial or other types I had no problem doing so. But when it came to doing the same for inequalities I got stuck. I tried to watch videos on its proving process, read the answers I could find in this site, but there's something I'm not grasping as I'm not capable of finishing the proof I'm working on.

That's the following, given: $$ 2^n > n^2 + 4n + 5 \ for \ n > 6 \ where \ n \in \Bbb N $$

First, I compacted the expression to this: $ 2^n > (n + 2)^2 + 1 $

Then, I did the: $ \pmb{Base \ Case}: $ $$ P(7): 2^7 > (7 + 2)^2 + 1 = 128 > 82 $$

Which results to be True.

Then I established the following $\pmb{assumption} $ to be True for $ n = k $: $$ P(k): 2^k > (k+2)^2 + 1 \ where \ n > 6 $$

And went on to $\pmb{prove}$ for $ n = k + 1 $: $$ P(k + 1): 2^{k+1} > ((k+1)+2)^2 + 1 $$

So here started with the $ LHS = 2^{k+1} = 2(2^k)$

Then proceeded with the $ RHS = ((k+1)+2)^2 + 1 = (k+3)^2 + 1 $

But, as all the explanation I got about the Induction principle has been about its generic steps and using equalities, I don't really know how to proceed or what steps to follow to accomplish the proof nor what to do with the expressions I have.

So what I ask for is an explanation of how should I proceed when I encounter an equality like the one I'm stuck with, because If I only get the answer now, later on, I'll be equally stuck.

$\endgroup$
  • 1
    $\begingroup$ To show the inequality for $P(k+1)$, you want to somehow use $P(k)$. A natural thing to do could be to start with $P(k)$ (which we assume is true) and multiply both sides by $2$ (since this makes the LHS become $2^{k+1}$, so it resembles the $P(k+1)$). Then try and simplify the RHS down to what is desired. $\endgroup$ – Minus One-Twelfth Mar 6 '19 at 11:30
  • $\begingroup$ Thanks, @MinusOne-Twelfth, this helped. That's a great piece of advice. That's the kind of thing I'm looking for. The set of things that would be considered "natural" on resolving this kind of problems. $\endgroup$ – Power_of_zero Mar 6 '19 at 13:19
1
$\begingroup$

We have $$2^n>n^2+4n+5$$ and we must prove that $$2^{n+1}>(n+1)^2+4(n+1)+5$$ multiplying our first inequality by $2$ we get $$2^{n+1}>2n^2+8n+10$$ so it remains to prove that $$2n^2+8n+10>(n+1)^2+4(n+1)+5$$ This is true, since we get $$n(n+2)>0$$

$\endgroup$
  • 1
    $\begingroup$ Thanks! Combining your answer with the comment in the question, I see how you got where you got. This helped me in resolving the problem, but, as I already did in a comment above, I would kindly ask for some set of thoughts or ideas to keep in mind when encountering this kind of problems. $\endgroup$ – Power_of_zero Mar 6 '19 at 13:21

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.