5
$\begingroup$

I want to find for what positive integers n, the statement $11n+17 \leq 2^n$ is true.

I then want to prove that this is true with induction. The problem I see here, is that to prove it, I need to find P(1), which gives $11+17\leq2$, which is false.

5 Answers 5

6

Induction works with any starting point, it doesn't need to start at $n=1$. If you prove that a statement $P(n)$ is true for $n=k$, and that $P(n)\Rightarrow P(n+1)$ for any integer $n$, then you have proven $P(n)$ to be true for all integers $n\geq k$. So find the first value of $n$ for which $11n+17\leq 2^n$, and start from there.

  • 0
    @Zev: The definition of an inductive set is such set $A$ of natural numbers that $0\in A$ and if $n\in A$ then $n+1\in A$. That is $A=\mathbb N$. This implies that $A=\{x\in\mathbb N\mid x\ge 7\}$ is **not** an inductive set. However the set $A' = \{x\in\mathbb N\mid x+7\in A\}$ *is* an inductive set. It is a small point when being completely formal, and although it has no practical difference, I think that a mathematician should be aware to this "modification". I hope it illuminates my answer on this page in a new light for you. :-)2011-06-22
6

Suppose you want to prove by induction that for all $n$ some property $P(n)$ holds.

However the property fails for all $n for some fixed $k$, and from $n\ge k$ the property holds.

You can prove by induction as usual that $P(n+k)$ holds for all $n\in\mathbb N$ instead.

As Zev says, this is just proving the induction is true from some number onwards. The rest of the numbers you may either check by hand, by computer (when possible) or show that the claim is not true in general for $n.

In your case, $P(n)$ is $11n+17\le 2^n$, and it is false for $n<7$ but $P(n+7)$ is true for all $n$.

(Note: I am assuming $0$ is a natural number as well)

Appendix A: A small skeleton for proving that $P(n+7)$ holds for all $n$

  • Base, $n=0$ we have that $11\cdot 7+17 = 94 < 128 = 2^7$.
  • Step, assume it is true for $n$, then $11(n+7)+17\le 2^{n+7}$.
    $\begin{align} 2^{n+1+7} =& 2\cdot 2^{7+n} >&\text{ (by the induction hypothesis)}\\ &2\big(11(n+7)+17\big) =&\\ &11(n+7)+17+11(n+7)+17>&\\ &11(n+7)+17+11=&\\ &11(n+1+7)+17 \end{align}$ Which proves the property for $n+1$ as needed.
  • 0
    @Asaf...not a problem!2011-06-21
5

I think that in this problem it is instructive to do the induction step first. Now admittedly this is not following the most standard recipe for induction proofs, and we certainly need to analyze base cases at some point, but doing it this way will answer an important implicit question: how do we know that there is some $N$ such that for all $n \geq N$ we have $11n + 17 \leq 2^n$? (Well, we should know this from calculus, but how do we see it in this framework?)

For a positive integer $N$, let $P(N)$ be the assertion $11N + 17 \leq 2^N$.

Step 1 (Induction Step): Suppose that $P(N)$ holds for some $N$. Now we try to prove $P(N+1): 11(N+1) + 17 \leq 2^{N+1}$.

Note $2^{N+1} = 2 \cdot 2^N = 2^N + 2^N \geq 2^N + 11N + 17$;

the last inequality used our induction hypothesis $P(N)$. Since $11(N+1) + 17 = (11N+17) + 11$, we will have $2^N + 11N + 17 \geq 11(N+1) + 17$ as long as $2^N \geq 11$. In turn, this inequality is true for all $N \geq 4$, so if $N \geq 4$ then

$2^{N+1} \geq 2^N + 2^N \geq 11 + (11N + 17) = 11(N+1) + 17$.

What have we shown? This:

If if for some $N_0 \geq 4$ we have $11N_0 + 17 \leq 2^{N_0}$, then for all $n \geq N_0$ we have $11n + 17 \leq 2^n$.

Step 2 (Base Cases): checking small positive integers $n$ one finds that $11n + 7 > 2^n$ for $1 \leq n \leq 6$ but $11 \cdot 7 + 7 = 84 < 128 = 2^7$.

Conclusion: For a positive integer $n$, $11n + 7 \leq 2^n$ iff $n \geq 7$.

A comment: what I didn't fully like about some of the other answers was the part where they said: keep trying values of $n$ until you find one for which the inequality holds, then prove by induction that it holds for all greater values of $n$. This happens to holds here, but it need not hold for other, similar problems. In fact, compare this to Proposition 6 in these notes (on induction, from a sophomore level class on proof techniques) in which one is looking at the inequality $2^n \geq n^3$ on the natural numbers. This holds for $n = 0,1$, then fails for $n = 2$ through $9$, then holds again for all integers $n \geq 10$. On the other hand, the analysis using the induction step shows that if the inequality holds for any $n \geq 4$ then it holds for all larger values of $n$. In this problem as well it would be more efficient to do the induction step first: otherwise one would have to look at several more individual cases to build up confidence that one has the correct minimal value $N_0$ such that the inequality holds for all $n \geq N_0$. (I confess though that in my writeup of this problem I do not do the induction step first. I wanted to stick to the standard recipe as much as possible.)

3

You are not being asked to prove that the inequality holds from $n=1$ on.

What I would do is to fool around until I found an $n$ for which the inequality works, and such that the inequality does not work at $n-1$.

Playing a bit, you will find that the inequality works at $n=7$, but not at $n=6$.

Now the induction argument goes like this:

$1$. Check that the inequality holds at $n=7$. You have already done that.

$2$. Show that for any $n \ge 7$, if the inequality holds at $n$ it holds at $n+1$.

Together, these two steps show that the inequality holds for all $n \ge 7$.

Finally, you might want to check whether for some $n$ smaller than $7$, the inequality holds "by accident." For example, look at $36n-35$. This is $< 2^n$ at $n=1$, then greater for a while, then permanently less.

2

This would be true for all $n \geq 7$, hence the basis of induction would be $n=7$ and not $n=1$

  • 1
    Actually, it isn't that difficult to do it in your mind since every mathematician should know (a reasonable amount of) the powers of $2$ by heart. :-)2011-06-21