Wikipedia:Reference desk/Archives/Mathematics/2019 February 16

Welcome to the Wikipedia Mathematics Reference Desk Archives
The page you are currently viewing is an archive page. While you can leave answers for any questions shown below, please ask new questions on one of the current reference desk pages.

February 16

Mathematical induction article, the section "Example: forming dollar amounts by coins"

This example excludes n < 12 because the proposition to be proven fails for n = 11.

However, the proposition is true for n = 8, 9, or 10.

The given proof by induction does not employ the restriction that 'n > 11. Therefore, the base case can start with 8, with 9 or with 10 and the step case can proceed and yield the same valid proof.

True n = 11 is a valid counterexample. But this is only pure coincidence/luck that this counterexample is so easy to detect and avoid.

This example raises a more serious issue:

• How does mathematical induction principle addresses a possible situation in which a counterexample exists for some n that is yet to be discovered?

• And further, how can it guarantee that no such n exist?

UriGeva (talk) 01:50, 16 February 2019 (UTC)

(Courtesy link for the section: Mathematical induction#Example: forming dollar amounts by coins). But the proof does use the assumption that n ≥ 12. It does so in the second case, where a = 0. If it didn't use this assumption, then the proof would have been invalid. We know such a "proof" would have been invalid because we know that 11 is a counterexample. And as far as I can tell, this renders the rest of your question moot. –Deacon Vorbis (carbon • videos) 02:02, 16 February 2019 (UTC)

@UriGeva: You're clearly wrong at the point:

'...the base case can start with 8, with 9 or with 10 and the step case can proceed and yield the same valid proof.'

Obviously you can't make an inductive step to prove $S(10)\implies S(11)$ and the article clearly explains why the inductive step would not work here. --CiaPan (talk) 17:30, 16 February 2019 (UTC)

The general version, in case anyone is interested, is the Coin problem. At the top of the section where the example is given (under "Induction basis other than 0 or 1") it talks about using a starting point other than 0 (or 1 if you believe 0∉N). So the example uses this variant form of induction, which may be a bit confusing if you're not reading the article in order top to bottom. Also, the example pulls the number 12 out of nowhere, so it's natural to ask where it comes from and what happens with coin values other than 4 and 5. For the purposes of a specific proof, it is allowed to have a "magic number" appear as long as the argument is otherwise valid, but it is somewhat unsatisfying to not have any explanation of where the number comes from. The general theorem for coins with vales a, b (a and b relatively prime) is that n can be written as a sum of these two value if n≥(a-1)(b-1), though the proof is somewhat more complicated than a simple induction. At least that explains where the 12=(4-1)(5-1) comes from. Another issue with the example is that there are values of n<12 which an be written as indicated and some that can't. This may be confusing if you're not used to 'if' always meaning material implication, which is often not what it means in ordinary English. So the statement in the example might be read as a characterization, filling in iff for if, and of course that version of the statement is incorrect. A full statement would be: n can be written as the sum of 4's and 5's iff n is 0, 4, 5, 8, 9, 10, or n≥12. I'm not sure that this is the best example to use to illustrate this variant of induction since the cases complicate things, but I don't have a better one in mind. --RDBury (talk) 18:33, 16 February 2019 (UTC)

@Deacon Vorbis:, @CiaPan: and @RDBury: My point is that unless you have some prior knowledge, you have no reason to exclude n = 11. You know that the case $S(10)\implies S(11)$ fails (i.e., to skip n = 11), because either (a) you are familiar with the general case of the Coin problem, or (b) you ran a bunch of tests and in this case you were lucky as n = 11 happens to be just the fourth test (assuming you started with n = 8.) What happens for a proof by induction when neither prior knowledge nor sufficient testing discover that there might be one or more exception? UriGeva (talk) 11:44, 18 February 2019 (UTC)

Any proof, whether or not by induction, depends upon first making some conjecture that turns out to be true - and that requires some familiarity with the subject-matter. In this case, if your conjecture does not include the condition n > 11, then you will find that a negative number of coins is sometimes required, and you must discard the conjecture. You can then guess again or give up. catslash (talk) 14:16, 18 February 2019 (UTC)

Good point. Textbooks can give the wrong impression about mathematics using the theorem-proof-example-discussion format. In reality coming up with a theorem and it's proof often involves a lot experimentation and additional work that isn't shown. Looking for counterexamples and, if you find them, modifying your conjecture accordingly is a big part of that. Another is having prior knowledge of the proofs of similar theorems since they can often be modified to produce a proof of a new theorem. This experimentation and prior knowledge is usually not included in the final write-up because it's not relevant to the logical structure of the proof, and the result is that proofs often have magic numbers or magic formulas that appear to come out of nowhere. The proof is still logically valid even if it's construction is based on prior knowledge. --RDBury (talk) 18:09, 18 February 2019 (UTC)

See all horses are the same color for an incorrect use of induction. The inductive step of a proof by induction has to be valid for all natural numbers under consideration. Any "proof" that fails for some n had to have assumed something it could not assume; if the only assumption is that n is a natural number, and the other steps of the proof are logically sound, the proof cannot have counterexamples.--Jasper Deng (talk) 22:01, 18 February 2019 (UTC)

Polynomials sending primes to primes

It is a well-known fact that no non-constant polynomial with integer coefficients can take only prime values. Is it also true that x and −x are the only non-constant polynomials f for which |f(p)| is prime for all prime numbers p? GeoffreyT2000 (talk) 18:24, 16 February 2019 (UTC)

Yes, as a consequence of Dirichlet's theorem on arithmetic progressions. If the leading coefficient is negative then replace f with -f. If f has the form f(n)=n+c, c≠0, then pick a prime p>|c| and, by Dirichlet, a prime q ≡ -c (mod p) with q>p-c. Then f(q) ≡ 0 (mod p), p|f(q) and f(q)=q+c>p, so f(q) is composite. So either f has degree greater than 1 or f has the form mx+c where m>1. In either case there is M so that f(n)>n and f is increasing for n>M. Let p be a prime greater than M and assume f(p) is a prime q>p. Then f(p) ≡ 0 (mod q). By Dirichlet there is a prime r=aq+p for some a>0. But then f(r) ≡ 0 (mod q), in other words q|f(r), and q=f(p)<f(r) because f is increasing, so f(r) is composite. --RDBury (talk) 19:13, 16 February 2019 (UTC)