1
$\begingroup$

Prove that if $h > -1$, then $1 + nh ≤ (1+h^n)$ for all nonnegative integers $n$.

I've read several solutions and I'm still totally lost on how to go about this.

I have the inductive hypothesis: $1+kh ≤ (1+h)^{k}$.

And that we want to prove: $1+(k+1)h ≤ (1+h)^{k+1}$.


From here, I found various first steps that I don't understand. Examples:

  1. $(1+h)(1+kh) ≤ (1+h)^k(1+h)$. How did they get the left side?

  2. $1 + kh + h ≤ (1 + h)(k + kh)$. How did they arrive at the right side?

$\endgroup$

2 Answers 2

1
$\begingroup$

Note:

An inductive proof is given as an answer by David W.Farlow.


Explanations of some steps and flaws in your inductive argument:

  • We get $(1)$ from the inductive hypothesis (which is assumed to be true.) $$(1+kh) \leq (1+h)^k \Rightarrow (1+h)(1+kh) \leq (1+h)^k(1+h)=(1+h)^{k+1}$$ as $h >-1 \Rightarrow h+1>0$ and so multiplication of both sides of an inequality with a non-negative number doesn't change the inequality.

  • Here, $(2)$ is false because $$1+k+kh \leq (1+h)(k+kh)=k+2hk+h^2k \Rightarrow 1 \leq hk+h^2k=hk(h+1)$$ In this case, $h>-1$ but the other factors are non-negative; so it can't be true when $-1<h<0$.

  • So, $(2)$ should be $$1+k+kh \leq (1+h)(1+kh)=1+h+kh+kh^2$$ which is true because $h^2k \geq 0$


Now, why do we do $(1)$ and $(2)$ and how do we get the LHS or RHS in various inequalities?

This is done because to prove $a \leq b$, if we get $a \leq c$ and $c \leq b$, then we get the required inequality. Accordingly we can choose the required value of $c$ which not only makes this task possible but also easy.

$\endgroup$
0
$\begingroup$

First of all, why have you been reading a bunch of solutions? I suggest you make a serious attempt at the problem yourself and only then look to other solutions to bridge whatever gap that exists in your reasoning (looking up a solution should be the very last resort). To that end, note that the inequality is trivial for when $n=0,1$. Thus, consider the following statement of your problem (which I will provide a proof for afterwards):

Problem: For any non-zero real number $x$ with $x>-1$, prove by induction that for each $n\geq2$, $$(1+x)^n>1+nx.$$

Proof. Fix $x\in\mathbb{R}_{>-1}$, where $x\neq0$, and let $S(n)$ denote the statement $S(n) : (1+x)^n>1+nx$. Because $x\neq0$, we know that $x^2>0$, and hence $(1+x)^2=1+2x+x^2>1+2x$, whereby we see that $S(2)$, the base case, holds. Now, fix $k\geq2$, and assume that $S(k)$ holds. Then \begin{align} (1+x)^{k+1}&=(1+x)(1+x)^k\tag{$x>-1$; exponent law}\\[1em] &> (1+x)(1+kx)\tag{by $S(k)$, then ind. hyp.}\\[1em] &= 1+kx+x+kx^2\tag{expand}\\[1em] &> 1+kx+x\tag{since $kx^2>0$}\\[1em] &= 1+(k+1)x.\tag{factor} \end{align} Thus, $S(k+1)$ is also true, completing the inductive step. $\blacksquare$


Does it all make sense now? The margin notes for the proof should help a great deal (indeed, they should answer both of the questions you had about different points in other proofs). Regardless, always try as many approaches as possible and only then (after numerous fruitless attempts) give recourse to an externally produced solution.

$\endgroup$
6
  • $\begingroup$ I read solutions because I was stuck. Okay, I see I might've made a dumb mistake. $(1+x)^k$ was substituted for the inductive hypothesis. I didn't realize that was happening and didn't think I could do that because of the inequality (guessing it doesn't matter as long as there's an "or equals"?). Also, why is $kx^2$ removed? $\endgroup$ Jul 18, 2016 at 4:57
  • $\begingroup$ Why do you think the $kx^2$ is removed? $\endgroup$ Jul 18, 2016 at 5:14
  • $\begingroup$ Looks like if $x > 0$ and $k ≥ 2$, both sides equal, so you remove $kx^2$ so that the LHS is bigger than the right? $\endgroup$ Jul 22, 2016 at 0:25
  • $\begingroup$ Yes, $1+kx+x+kx^2>1+kx+x$ really because $kx^2>0$. This lets us "remove it" to suit our purposes. $\endgroup$ Jul 22, 2016 at 0:28
  • $\begingroup$ I've never seen that and would never have thought to remove it! Would it still be possible to solve if we left it? $\endgroup$ Jul 22, 2016 at 2:31

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .