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.
 A: 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)
A: 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.
A: 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$$
