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!

  • 2
    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.2012-12-03
  • 0
    Possible duplicate of [Prove that $ n < 2^{n}$ for all natural numbers $n$.](https://math.stackexchange.com/questions/449672/prove-that-n-2n-for-all-natural-numbers-n)2018-05-11
  • 0
    @B.Mehta This one is earlier than the linked post.2018-05-11
  • 0
    @GNUSupporter forgive my ignorance, but surely a more popular post with a more diverse range of answers is better?2018-05-11
  • 0
    @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"](https://math.meta.stackexchange.com/questions/12936/moderators-please-straighten-out-loop-in-duplicate-of-graph#comment50836_12936).2018-05-11
  • 0
    @GNUSupporter Ah, okay2018-05-11

3 Answers 3

2

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.

6

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

  • 1
    I'm not sure to understand where the $2^{k}$ + 1 < $2^{k}$ + $2^{k}$ comes from.2012-12-03
2

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).