# Can I solve this with induction? $n=2^m+p$

For every odd integer $n$, $3\leq n\leq 199$, there exists an integer $m\geq 0$, and a prime number $p$, such that $n=2^m+p$.

I created a software program in Java to solve this problem. The statement is actually false. The first odd number it fails at is 127. I really appreciate everyone's input on this.

-
As my answer no longer applies, I have deleted it. – Timothy Wagner Nov 20 '10 at 1:32
While I can't see how to use it in this case, induction can often still be useful for bounded statements. E.g. “every natural number less than 512 has some binary expansion with at most 9 digits”: of course, you could check each case, but a more efficient proof will use induction. There are two main ways: either relax your statement (to eg “every natural has a binary expansion”), prove by induction, then do a little work to recover the original case; or, directly use induction to prove a conditional statement: “for all $n$, (if $n < 512$ then $n$ has an expansion in $\leq 9$ digits)”. – Peter LeFanu Lumsdaine Nov 20 '10 at 2:25
You do not "solve" proofs, and you did not show "the proof" false. You gave no proof. You meant the statement or proposition is false. And, it might not be the best way to make friends and influence people to come to math forum and say "I hate math so much..." – Arturo Magidin Nov 21 '10 at 3:23

I sort of disagree with the statements saying that induction "cannot work"; but it is a subtle disagreement.

One can use "induction" to prove a statement for a restricted range of numbers. The most common type of such restricted ranges are statements that apply "eventually": for every $n\geq N$ for some $N$. The two standard ways of doing so is to either do the "base case" with $n=N$ instead of $n=0$ (or $1$, depending on whether you are a set theorist or a number theorist1); or to establish the equivalent proposition for $N+n$ (or $N-1+n$ if you are a number theorist) and do "induction on $n$".

But one can take a statement such as the one you give and establish, by mathematical induction, a proposition which is essentially what you want. It's just that it is almost always a wasteful exercise.

To see what I mean, let us take the statement you want to prove: for every odd integer $n$, $3\leq n\leq 199$, there is an integer $m$ and a prime number $p$ such that $n=2^m+p$.

Now consider the following statement P:

• for all natural numbers $n$, either $n$ is even, or $n\lt 3$, or $n\gt 199$, or $n=2^m+p$ for some integer $m$ and some prime $p$.

This is a statement about all natural numbers, and as such could be proven by induction. What is more, the statement is equivalent to the one you want to prove: if the statement above is true, then given an odd integer $n$, $3\leq n\leq 199$, the proposition will hold for $n$; but $n$ is not even, is not less than $3$, and is not greater than $199$, so therefore the clause "$n=2^m+p$ for some integer $m$ and some prime $p$" must hold for $n$, exactly what you want. And if the proposition you want to prove is true, then the statement above is true, since the other clauses of the disjunction will be trivially true for all "other" natural numbers. So in a sense, proving your statement is "the same" as proving the statement P I give above. So, in that sense, you can prove your statement by induction, because you can prove the equivalent statement P, which is something about all natural numbers, by induction.

It's just that the induction argument would be very convoluted, and almost certainly a waste of time, because the inductive step would have to break up into cases depending on $k$: if $k\geq 199$, then the proof proceeds one way; if $k$ is odd, another; and so on, until you get down to showing what happens if $2\leq k\leq 198$, with $k$ even. At that point, your argument would almost certainly devolve into simply a direct proof of the fact, so that "Induction" is really a smokescreen that only confuses the issue.

So, in a sense, "yes, you could prove it by induction, but it is almost certainly a very, very bad idea to try to do so." The same is true for other statements in which $n$ is bounded above.

Induction is particularly powerful when you are trying to prove something holds for infinitely many natural numbers, because that is not something that we can verify by checking the natural numbers one at a time. When we are trying to show something holds for finitely many natural number, then induction is seldom the way to go.

1 The standard way of defining the natural numbers within set theory is to construct them as the smallest inductive set; then the set contains $\emptyset$, which is identified with $0$; or through the Peano axioms, which usually include $0$ (though they need not do so). So for set theorists (and logicians), $\mathbb{N}$ contains $0$. But historically, $\mathbb{N}$ represented the counting numbers, and so "began" with $1$. So number theorists usually consider $\mathbb{N}$ to consist only of the positive integers.

-
I wish I could upvote many times. – Ross Millikan Nov 20 '10 at 3:47
@Ross Millikan: thank you kindly. I hope the new additions didn't diminish it in your view. – Arturo Magidin Nov 20 '10 at 4:01
At the end of your penultimate paragraph, you say "When we are trying to show something holds for finitely many natural numbers, then induction is seldom the way to go". When you wrote "seldom", did you have a specific example in mind where induction is the way to go? – Jason DeVito Nov 20 '10 at 5:00
@Jason De Vito: Peter LeFamu Lumsdaine gives an example in the comments, which in my opinion is not an unreasonable use of induction. I can't think of one natural example off the top of my head, to be honest (or I would have included it (-; ), but I don't want to categorically say it won't work, period. I suspect that any example I can come up with would be a twist on some kind of finite recursion, though. I vaguely remember something along these lines from (oh, so many years ago) my undergraduate days, but I can't seem to zero in on the memory to confirm it. – Arturo Magidin Nov 20 '10 at 5:09
@Jason De Vito: I actually thought of a natural place where one uses "bounded induction": commutator calculus in nilpotent group. It's a bit too much to put into the answer, but basically you often want to show that something holds for commutators; you do "descending bounded induction", by showing it works at the lowest level of the lower central series, and then showing that for the $k-1$st level, it works modulo some stuff in the $k$th level, to which you can apply induction. You can think of it as induction over $n$, looking at the $c-n$th term, and you only do $0\leq n\leq c-1$. – Arturo Magidin Nov 20 '10 at 21:23

Induction can't work.

Edit. As Arturo points out, I made too strong of a statement here. Perhaps a more correct way to state it is "Induction in the usual sense can't work" or "There is likely no natural inductive proof".

If it DID work, then there wouldn't be an upper bound of of n = 199. However, the case n = 251 provides a counterexample since

251 = 1+ 2*125

251 = 2 + 3*83

251 = 4 + 13*19

251 = 8 + 3*81

251 = 16 + 5*49

251 = 32 + 3*73

251 = 64 + 11*17

251 = 128 + 3*41

And all other powers of 2 are greater than 251.

(I didn't check if this is the smallest counterexample or not)

-
De Vito: Induction over the unbounded version of the proposition cannot work (because it is false). – Arturo Magidin Nov 20 '10 at 3:41

Induction is not valid, because it is used to show propositions for all integers positive or integers infinite. The condition $n\Rightarrow n+1$ involves integers infinites.

I believe that the solution is prove each for find $m$ and $p$ in each case.

For example:

$$173= 2^{6}+109$$ $$153=2 ^{6}+89$$ $$117=2^{4}+101$$

-