# Proving with Induction When The Claim Fails For Several Numbers

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.

-

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.

-
At P(7), I get 94<=128, which is true. Now, for the inductive part, I would have one side be 2^(n+1). But what would the other side be? Is it 2^n + 1? –  Matt Jun 21 '11 at 16:36
Using the inductive hypothesis, namely that $11n+17\leq 2^n$ and $n\geq 7$, you want to prove that $$11(n+1)+17\leq 2^{n+1}.$$ This is the inductive step. Note that $11(n+1)+17=(11n+17)+11$, and by the inductive hypothesis, $11n+17\leq 2^n$, so we have that $$11(n+1)+17\leq 2^n+11.$$ Can you show that $2^n+11\leq 2^{n+1}$ when $n\geq 7$? –  Zev Chonoles Jun 21 '11 at 16:38
Let me see if I understand: 11n+17<=2^n adding 1 -> 11(n+1)+17<=2^(n+1) -> 11n+28<2^(n+1) so 11n+28<2^(n+1)<2^n +1 <=2^n 2^n = 2(2^n) = 2(n+1), which is the same as P(n+1), so true. –  Matt Jun 21 '11 at 16:52
@Matt: No, for every positive $n$, it is false that $2^{n+1}<2^n+1$ . Your $P(n)$ is: "the number $11n+17$ is less than or equal to $2^n$". We've seen that $P(7)$ is true. We now want to prove that $P(n)\Rightarrow P(n+1)$ when $n\geq7$. By the definition, $P(n+1)$ is the statement that $$11(n+1)+17\leq 2^{n+1}.$$ You need to use somewhere the assumption that $P(n)$ is true (this is the whole point of induction, proving that $P(n)$ implies $P(n+1)$). So, in your proof that $$11(n+1)+17\leq2^{n+1}$$ you can use that $P(n)$ is true, i.e. $11n+17\leq 2^n$. I indicated in my comment how to use it. –  Zev Chonoles Jun 21 '11 at 16:55
Also, your comment indicates that you might be confused about exponentiation. Note that $$2^{n+1}=\underbrace{2\times\cdots\times 2}_{n+1\text{ times}}$$ and $$2^n+1 = \left(\underbrace{2\times \cdots\times 2}_{n\text{ times}}\right)+1.$$ –  Zev Chonoles Jun 21 '11 at 17:00

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

However the property fails for all $n<k$ 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<k$.

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.
-
@Asaf...not a problem! –  amWhy Jun 21 '11 at 17:29

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

-

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.

-

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

-
How did you get to 7? I tried solving and got 11. –  Matt Jun 21 '11 at 16:30
@Matt: $$(11\times 7)+17=94\leq 128=2^7$$ –  Zev Chonoles Jun 21 '11 at 16:33
So you just tried numbers until it worked? –  Matt Jun 21 '11 at 16:37
@Matt: That's how I did it. Sometimes that's more convenient than trying to solve it explicitly. –  Zev Chonoles Jun 21 '11 at 16:40
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. :-) –  Andrea Mori Jun 21 '11 at 17:08