0

I read in a Book written by Raymond A. Barnett and Micheal R. Ziegler the way to prove conjectures for infinite members of a given set and that is, Mathematical Induction. When I read Induction, I found it very interesting. The way to prove propositions using induction theorem looks like this:

Step 1: Base case i.e. to prove for 1.

Step :2 Inductive step i.e. to assume that proposition is true for any unknown number (k) and then prove for k+1

Then on other page I found an conjecture given by Euler i.e. for each positive integer n, the number n^2 - n + 41 is a prime. When I tried it to prove by Induction theorem stated above, it resulted it to be true for each positive integer however Euler's proposition failed when I put n=41. Is there any other method to check for the Euler's proposition; that could prove it wrong for all n?

Sufyan Naeem
  • 2,298

3 Answers3

1

You can certainly show it is true for the base case $n=1$ which gives $41$ which is indeed prime.

You then assume that it is true for $n=k$ and get:$$k^2-k+41=p_k$$where $p_k$ is some prime number.

If we now use the inductive step and try to prove this is also true for $n=k+1$ then we get:$$(k+1)^2-(k+1)+41=k^2+2k+1-k-1+41=(k^2-k+41)+2k$$$$=p_k+2k$$Now how did you conclude that $p_k+2k$ is also prime?

Mufasa
  • 5,434
  • 1
    Your understanding of inductive proofs is incorrect. Maybe this will help you understand it better. – Mufasa Jan 31 '15 at 17:30
  • 1
    Look at what you stated (correctly) about step 2 in your question: "Inductive step i.e. to assume that proposition is true for any unknown number ($k$) and then prove for $k+1$". In your case, you were trying to assume it is true for a known number (i.e. $k=2$). – Mufasa Jan 31 '15 at 17:34
  • 1
    I strongly advise you to lookup the correct definition of proof by induction. You misunderstanding the subtle point in step 2 of the inductive proof. – Mufasa Jan 31 '15 at 18:00
1

Suppose $f(k)=k^2-k+41$ is prime (for $k\ge1$). Then $$ f(k+1)=(k+1)^2-(k+1)+41=k^2+2k+1-k-1+41=f(k)+2k $$ which is not prime if $k$ divides $f(k)$. This happens for $k=41$, so there's no way to prove that “$f(k)$ prime implies $f(k+1)$ prime”, because it's false.

egreg
  • 238,574
0

You probably misunderstood this step:

Step :2 Inductive step i.e. to assume that proposition is true for any unknown number (k) and then prove for k+1

My guess is that by "any unknown number" you understood ONE unknown number you can chose. But this step actually sais the following:

Assume (k) step is true, no matter what k is (i.e. you cannot chose k) and then prove k+1.

N. S.
  • 132,525