Does Induction theorem fails here at Euler's conjecture?

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

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?