0
$\begingroup$

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?

$\endgroup$
  • 1
    $\begingroup$ There must be some flaw in your argument. Can you show us your work? $\endgroup$ – Tim Raczkowski Jan 31 '15 at 17:18
  • 1
    $\begingroup$ How did you do step 2? $\endgroup$ – Djaian Jan 31 '15 at 17:19
1
$\begingroup$

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?

$\endgroup$
  • 1
    $\begingroup$ Your understanding of inductive proofs is incorrect. Maybe this will help you understand it better. $\endgroup$ – Mufasa Jan 31 '15 at 17:30
  • 1
    $\begingroup$ 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$). $\endgroup$ – Mufasa Jan 31 '15 at 17:34
  • 1
    $\begingroup$ 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. $\endgroup$ – Mufasa Jan 31 '15 at 18:00
1
$\begingroup$

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.

$\endgroup$
0
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ No I don't understood it what are you saying. I know that it's for an unknown number. $\endgroup$ – Sufyan Naeem Jan 31 '15 at 17:53
  • 1
    $\begingroup$ @SufyanSheikh Can you SHOW the details of your proof of step 2? $\endgroup$ – N. S. Jan 31 '15 at 17:54

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.