Does Induction theorem fails here at Euler's conjecture?

Question

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?

Answer 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?

Answer 2

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.

Answer 3

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.