1
$\begingroup$

I am currently in the process of learning how to prove statements by induction. For the most part, I understand but I am at most clueless when it comes to prove some inequalities.

For example, I am having a hard time proving that:
$n < 2^n$ is true. (Even if it's clear that it is indeed true!)

In the induction step, I am stuck with:
$n + 1 < 2^{n + 1}$

I don't know what would be the assumption I should make from this statement.

Anyone could point me in the right direction? Thanks!

$\endgroup$
  • 2
    $\begingroup$ Internal monologue: How shall I use the assumption that $2^k \gt k$ to prove $2^{k+1}\gt k+1$. Well, $2^{k+1}=2\cdot 2^k$. If I know $2^k\gt k$, then I know $2^{k+1}\gt 2k$. Can I show that $2k\ge k+1$? That would do it. But of course $2k\ge k+1$ (if $k\ge 1$). OK, let's write it up. $\endgroup$ – André Nicolas Dec 3 '12 at 4:23
  • $\begingroup$ Possible duplicate of Prove that $ n &lt; 2^{n}$ for all natural numbers $n$. $\endgroup$ – B. Mehta May 11 '18 at 4:03
  • $\begingroup$ @B.Mehta This one is earlier than the linked post. $\endgroup$ – GNUSupporter 8964民主女神 地下教會 May 11 '18 at 19:09
  • $\begingroup$ @GNUSupporter forgive my ignorance, but surely a more popular post with a more diverse range of answers is better? $\endgroup$ – B. Mehta May 11 '18 at 19:16
  • $\begingroup$ @B.Mehta I've checked meta. It's ok to close an older question as a dupe of a newer one, but your linked post is marked as a dupe of the current one. I don't think that the system allows a "loop of dupes". $\endgroup$ – GNUSupporter 8964民主女神 地下教會 May 11 '18 at 19:25
2
$\begingroup$

Hint $\ $ First prove by induction this lemma: an increasing function stays $\ge$ its initial value, i.e. $\rm\:f(n\!+\!1)\ge f(n)\:\Rightarrow\:f(n)\ge f(0).$ Now apply this lemma to the function $\rm\:f(n) = 2^n\! - n,\:$ which is increasing by $\rm\:f(n\!+\!1)-f(n) = 2^n\!-1 \ge 0.\:$ Thus, by the lemma, $\rm\:f(n)\ge f(0) = 1,\:$ so $\rm\:2^n > n.$

Remark $\ $ Note that we reduce the proof to the same inequality as in Will's answer: $\rm\:2^n \ge 1$ (which, itself, may require an inductive proof, depending on the context). But here we've injected the additional insight that the inductive proof of the inequality can be viewed as a special case of the inductive proof of the inequality that an increasing function stays $\ge$ its initial value - which lends much conceptual insight into the induction process. Further, by abstracting out the lemma, we now have a tool that can be reused for analogous inductive proofs (and this simple tool often does the job - see my many prior posts on telescopy for further examples and discussion).

$\endgroup$
6
$\begingroup$

Let $P(n)$ be the statement that $n<2^n$. Since $1<2^1$, we have that $P(1)$ is true.

Suppose $P(k)$ is true for some positive integer $k$. Then $k<2^k$, so that $k+1<2^k+1<2^k+2^k=2^{k+1}$. Hence $P(k+1)$ is true.

It follows that $P(n)$ is true for all positive integers $n$.

$\endgroup$
  • 1
    $\begingroup$ I'm not sure to understand where the $2^{k}$ + 1 < $2^{k}$ + $2^{k}$ comes from. $\endgroup$ – wwwe Dec 3 '12 at 5:27
2
$\begingroup$

I apologize for digging this up. I just saw a nice combinatorial proof by AnotherJohnDoe in another thread, but for some reason, he deleted his answer, and that thread was locked. Here is the argument.

Consider a set $S$ of $n$ elements. Then, the number of subsets of $S$ equals $2^n$. This is greater than or equal to the number of single-element subsets plus the empty set.

$\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.