Finding mistake in proof that all numbers are even [closed]

Clash Royale CLAN TAG#URR8PPP

up vote
4
down vote

favorite

2

Claim: The numbers $0,1,2,3,dots$ are all even.

Proof: We use strong induction to prove the statement '$n$ is even' for
$n=0,1,2,3,dots$

Base case: $n=0$ is an even number, hence the statement is true for $n=0$.

Assume that the statement is true for $n=0,1,2,dots,k$, and consider $n=k+1$. By assumption, both 1 and $k$ are even numbers, and hence so is their sum $k+1$. It thus follows that the statement holds for all $n=0,1,2,3,dots$

I'm having some trouble seeing how to prove this wrong.

induction fake-proofs

share|cite|improve this question

edited Jul 22 at 3:42

Parcly Taxel

33.6k136588

asked Jul 22 at 3:31

Patrick

355

closed as off-topic by Morgan Rodgers, amWhy, Xander Henderson, Mostafa Ayaz, m_t_ Jul 22 at 17:15

This question appears to be off-topic. The users who voted to close gave this specific reason:

• "This question is missing context or other details: Please improve the question by providing additional context, which ideally includes your thoughts on the problem and any attempts you have made to solve it. This information helps others identify where you have difficulties and helps them write answers appropriate to your experience level." – Morgan Rodgers, amWhy, Xander Henderson, Mostafa Ayaz

If this question can be reworded to fit the rules in the help center, please edit the question.

• 
  
  
  

  
  3
  

  
  
  
  
  
  

  
  When did you prove "$1$ is an even number" ? In the heridity step, $k$ is any non negative number. If you consider $k=0$, you see easily that the reasoning does not hold.
  – Suzet
  Jul 22 at 3:32
  
  

  
  
  
  


• 
  
  
  

  
  7
  

  
  
  
  
  
  

  
  Isn't there a proof like this which shows that all horses are the same color? en.wikipedia.org/wiki/All_horses_are_the_same_color
  – Mason
  Jul 22 at 4:01
  
  

  
  
  
  


• 
  
  
  

  
  2
  

  
  
  
  
  
  

  
  "Isn't there a proof like this which shows that all horses are the same color?" It's not really the same. In the horse color you have a method (albeit faulty) of getting from $n$ to $n+1$ by subtracting one and adding one (and assuming condition that $n>1$ which was not in your base case). Here you simply assume with no justification at all that $1$ is even.
  – fleablood
  Jul 22 at 4:41
  

  
  
  
  


• 
  
  
  

  
  

  
  
  
  
  
  

  
  related: math.stackexchange.com/questions/428151/…
  – Henry
  Jul 22 at 14:58
  

  
  
  
  


• 
  
  
  

  
  1
  

  
  
  
  
  
  

  
  @fleablood I think the similarity between the two proofs is that, in both cases, the alleged induction step is OK when $k$ is large enough. People are fooled because they think of the induction variable as big, and neglect the first few steps of the inductive process.
  – Andreas Blass
  Jul 22 at 15:06
  

  
  
  
  

 | 
show 2 more comments

up vote
4
down vote

favorite

2

Claim: The numbers $0,1,2,3,dots$ are all even.

Proof: We use strong induction to prove the statement '$n$ is even' for
$n=0,1,2,3,dots$

Base case: $n=0$ is an even number, hence the statement is true for $n=0$.

Assume that the statement is true for $n=0,1,2,dots,k$, and consider $n=k+1$. By assumption, both 1 and $k$ are even numbers, and hence so is their sum $k+1$. It thus follows that the statement holds for all $n=0,1,2,3,dots$

I'm having some trouble seeing how to prove this wrong.

induction fake-proofs

share|cite|improve this question

edited Jul 22 at 3:42

Parcly Taxel

33.6k136588

asked Jul 22 at 3:31

Patrick

355

closed as off-topic by Morgan Rodgers, amWhy, Xander Henderson, Mostafa Ayaz, m_t_ Jul 22 at 17:15

This question appears to be off-topic. The users who voted to close gave this specific reason:

• "This question is missing context or other details: Please improve the question by providing additional context, which ideally includes your thoughts on the problem and any attempts you have made to solve it. This information helps others identify where you have difficulties and helps them write answers appropriate to your experience level." – Morgan Rodgers, amWhy, Xander Henderson, Mostafa Ayaz

If this question can be reworded to fit the rules in the help center, please edit the question.

• 
  
  
  

  
  3
  

  
  
  
  
  
  

  
  When did you prove "$1$ is an even number" ? In the heridity step, $k$ is any non negative number. If you consider $k=0$, you see easily that the reasoning does not hold.
  – Suzet
  Jul 22 at 3:32
  
  

  
  
  
  


• 
  
  
  

  
  7
  

  
  
  
  
  
  

  
  Isn't there a proof like this which shows that all horses are the same color? en.wikipedia.org/wiki/All_horses_are_the_same_color
  – Mason
  Jul 22 at 4:01
  
  

  
  
  
  


• 
  
  
  

  
  2
  

  
  
  
  
  
  

  
  "Isn't there a proof like this which shows that all horses are the same color?" It's not really the same. In the horse color you have a method (albeit faulty) of getting from $n$ to $n+1$ by subtracting one and adding one (and assuming condition that $n>1$ which was not in your base case). Here you simply assume with no justification at all that $1$ is even.
  – fleablood
  Jul 22 at 4:41
  

  
  
  
  


• 
  
  
  

  
  

  
  
  
  
  
  

  
  related: math.stackexchange.com/questions/428151/…
  – Henry
  Jul 22 at 14:58
  

  
  
  
  


• 
  
  
  

  
  1
  

  
  
  
  
  
  

  
  @fleablood I think the similarity between the two proofs is that, in both cases, the alleged induction step is OK when $k$ is large enough. People are fooled because they think of the induction variable as big, and neglect the first few steps of the inductive process.
  – Andreas Blass
  Jul 22 at 15:06
  

  
  
  
  

 | 
show 2 more comments

up vote
4
down vote

favorite

2

up vote
4
down vote

favorite

2

2

Claim: The numbers $0,1,2,3,dots$ are all even.

Proof: We use strong induction to prove the statement '$n$ is even' for
$n=0,1,2,3,dots$

Base case: $n=0$ is an even number, hence the statement is true for $n=0$.

Assume that the statement is true for $n=0,1,2,dots,k$, and consider $n=k+1$. By assumption, both 1 and $k$ are even numbers, and hence so is their sum $k+1$. It thus follows that the statement holds for all $n=0,1,2,3,dots$

I'm having some trouble seeing how to prove this wrong.

induction fake-proofs

share|cite|improve this question

edited Jul 22 at 3:42

Parcly Taxel

33.6k136588

asked Jul 22 at 3:31

Patrick

355

Claim: The numbers $0,1,2,3,dots$ are all even.

Proof: We use strong induction to prove the statement '$n$ is even' for
$n=0,1,2,3,dots$

Base case: $n=0$ is an even number, hence the statement is true for $n=0$.

Assume that the statement is true for $n=0,1,2,dots,k$, and consider $n=k+1$. By assumption, both 1 and $k$ are even numbers, and hence so is their sum $k+1$. It thus follows that the statement holds for all $n=0,1,2,3,dots$

I'm having some trouble seeing how to prove this wrong.

induction fake-proofs

share|cite|improve this question

edited Jul 22 at 3:42

Parcly Taxel

33.6k136588

asked Jul 22 at 3:31

Patrick

355

share|cite|improve this question

share|cite|improve this question

edited Jul 22 at 3:42

Parcly Taxel

33.6k136588

edited Jul 22 at 3:42

Parcly Taxel

33.6k136588

edited Jul 22 at 3:42

Parcly Taxel

33.6k136588

33.6k136588

asked Jul 22 at 3:31

Patrick

355

asked Jul 22 at 3:31

Patrick

355

asked Jul 22 at 3:31

Patrick

355

355

closed as off-topic by Morgan Rodgers, amWhy, Xander Henderson, Mostafa Ayaz, m_t_ Jul 22 at 17:15

This question appears to be off-topic. The users who voted to close gave this specific reason:

• "This question is missing context or other details: Please improve the question by providing additional context, which ideally includes your thoughts on the problem and any attempts you have made to solve it. This information helps others identify where you have difficulties and helps them write answers appropriate to your experience level." – Morgan Rodgers, amWhy, Xander Henderson, Mostafa Ayaz

If this question can be reworded to fit the rules in the help center, please edit the question.

closed as off-topic by Morgan Rodgers, amWhy, Xander Henderson, Mostafa Ayaz, m_t_ Jul 22 at 17:15

This question appears to be off-topic. The users who voted to close gave this specific reason:

• "This question is missing context or other details: Please improve the question by providing additional context, which ideally includes your thoughts on the problem and any attempts you have made to solve it. This information helps others identify where you have difficulties and helps them write answers appropriate to your experience level." – Morgan Rodgers, amWhy, Xander Henderson, Mostafa Ayaz

If this question can be reworded to fit the rules in the help center, please edit the question.

• 
  
  
  

  
  3
  

  
  
  
  
  
  

  
  When did you prove "$1$ is an even number" ? In the heridity step, $k$ is any non negative number. If you consider $k=0$, you see easily that the reasoning does not hold.
  – Suzet
  Jul 22 at 3:32
  
  

  
  
  
  


• 
  
  
  

  
  7
  

  
  
  
  
  
  

  
  Isn't there a proof like this which shows that all horses are the same color? en.wikipedia.org/wiki/All_horses_are_the_same_color
  – Mason
  Jul 22 at 4:01
  
  

  
  
  
  


• 
  
  
  

  
  2
  

  
  
  
  
  
  

  
  "Isn't there a proof like this which shows that all horses are the same color?" It's not really the same. In the horse color you have a method (albeit faulty) of getting from $n$ to $n+1$ by subtracting one and adding one (and assuming condition that $n>1$ which was not in your base case). Here you simply assume with no justification at all that $1$ is even.
  – fleablood
  Jul 22 at 4:41
  

  
  
  
  


• 
  
  
  

  
  

  
  
  
  
  
  

  
  related: math.stackexchange.com/questions/428151/…
  – Henry
  Jul 22 at 14:58
  

  
  
  
  


• 
  
  
  

  
  1
  

  
  
  
  
  
  

  
  @fleablood I think the similarity between the two proofs is that, in both cases, the alleged induction step is OK when $k$ is large enough. People are fooled because they think of the induction variable as big, and neglect the first few steps of the inductive process.
  – Andreas Blass
  Jul 22 at 15:06
  

  
  
  
  

 | 
show 2 more comments

• 
  
  
  

  
  3
  

  
  
  
  
  
  

  
  When did you prove "$1$ is an even number" ? In the heridity step, $k$ is any non negative number. If you consider $k=0$, you see easily that the reasoning does not hold.
  – Suzet
  Jul 22 at 3:32
  
  

  
  
  
  


• 
  
  
  

  
  7
  

  
  
  
  
  
  

  
  Isn't there a proof like this which shows that all horses are the same color? en.wikipedia.org/wiki/All_horses_are_the_same_color
  – Mason
  Jul 22 at 4:01
  
  

  
  
  
  


• 
  
  
  

  
  2
  

  
  
  
  
  
  

  
  "Isn't there a proof like this which shows that all horses are the same color?" It's not really the same. In the horse color you have a method (albeit faulty) of getting from $n$ to $n+1$ by subtracting one and adding one (and assuming condition that $n>1$ which was not in your base case). Here you simply assume with no justification at all that $1$ is even.
  – fleablood
  Jul 22 at 4:41
  

  
  
  
  


• 
  
  
  

  
  

  
  
  
  
  
  

  
  related: math.stackexchange.com/questions/428151/…
  – Henry
  Jul 22 at 14:58
  

  
  
  
  


• 
  
  
  

  
  1
  

  
  
  
  
  
  

  
  @fleablood I think the similarity between the two proofs is that, in both cases, the alleged induction step is OK when $k$ is large enough. People are fooled because they think of the induction variable as big, and neglect the first few steps of the inductive process.
  – Andreas Blass
  Jul 22 at 15:06
  

  
  
  
  

3

3

When did you prove "$1$ is an even number" ? In the heridity step, $k$ is any non negative number. If you consider $k=0$, you see easily that the reasoning does not hold.
– Suzet
Jul 22 at 3:32

When did you prove "$1$ is an even number" ? In the heridity step, $k$ is any non negative number. If you consider $k=0$, you see easily that the reasoning does not hold.
– Suzet
Jul 22 at 3:32

7

7

Isn't there a proof like this which shows that all horses are the same color? en.wikipedia.org/wiki/All_horses_are_the_same_color
– Mason
Jul 22 at 4:01

Isn't there a proof like this which shows that all horses are the same color? en.wikipedia.org/wiki/All_horses_are_the_same_color
– Mason
Jul 22 at 4:01

2

2

"Isn't there a proof like this which shows that all horses are the same color?" It's not really the same. In the horse color you have a method (albeit faulty) of getting from $n$ to $n+1$ by subtracting one and adding one (and assuming condition that $n>1$ which was not in your base case). Here you simply assume with no justification at all that $1$ is even.
– fleablood
Jul 22 at 4:41

"Isn't there a proof like this which shows that all horses are the same color?" It's not really the same. In the horse color you have a method (albeit faulty) of getting from $n$ to $n+1$ by subtracting one and adding one (and assuming condition that $n>1$ which was not in your base case). Here you simply assume with no justification at all that $1$ is even.
– fleablood
Jul 22 at 4:41

related: math.stackexchange.com/questions/428151/…
– Henry
Jul 22 at 14:58

related: math.stackexchange.com/questions/428151/…
– Henry
Jul 22 at 14:58

1

1

@fleablood I think the similarity between the two proofs is that, in both cases, the alleged induction step is OK when $k$ is large enough. People are fooled because they think of the induction variable as big, and neglect the first few steps of the inductive process.
– Andreas Blass
Jul 22 at 15:06

@fleablood I think the similarity between the two proofs is that, in both cases, the alleged induction step is OK when $k$ is large enough. People are fooled because they think of the induction variable as big, and neglect the first few steps of the inductive process.
– Andreas Blass
Jul 22 at 15:06

 | 
show 2 more comments

2 Answers
2

active

oldest

votes

up vote
18
down vote



accepted

The following statement is not true for $k = 0$

"By assumption, both $1$ and $k$ are even numbers, and hence so is their sum $k + 1$."

For $k = 0$, you only know that $0$ is even not $1$. So you can't make the assertion above for all $k$.

share|cite|improve this answer

answered Jul 22 at 4:04

Key Flex

4,318424

add a comment | 

up vote
6
down vote

The problem is that your proof of the induction step should include the step from $0$ to $1$; and that's where your argument fails.

share|cite|improve this answer

edited Jul 22 at 4:04

Key Flex

4,318424

answered Jul 22 at 3:37

Martin Argerami

116k1071164

add a comment | 

2 Answers
2

active

oldest

votes

2 Answers
2

active

oldest

votes

active

oldest

votes

active

oldest

votes

up vote
18
down vote



accepted

The following statement is not true for $k = 0$

"By assumption, both $1$ and $k$ are even numbers, and hence so is their sum $k + 1$."

For $k = 0$, you only know that $0$ is even not $1$. So you can't make the assertion above for all $k$.

share|cite|improve this answer

answered Jul 22 at 4:04

Key Flex

4,318424

add a comment | 

up vote
18
down vote



accepted

The following statement is not true for $k = 0$

"By assumption, both $1$ and $k$ are even numbers, and hence so is their sum $k + 1$."

For $k = 0$, you only know that $0$ is even not $1$. So you can't make the assertion above for all $k$.

share|cite|improve this answer

answered Jul 22 at 4:04

Key Flex

4,318424

add a comment | 

up vote
18
down vote



accepted

up vote
18
down vote



accepted

The following statement is not true for $k = 0$

"By assumption, both $1$ and $k$ are even numbers, and hence so is their sum $k + 1$."

For $k = 0$, you only know that $0$ is even not $1$. So you can't make the assertion above for all $k$.

share|cite|improve this answer

answered Jul 22 at 4:04

Key Flex

4,318424

The following statement is not true for $k = 0$

"By assumption, both $1$ and $k$ are even numbers, and hence so is their sum $k + 1$."

For $k = 0$, you only know that $0$ is even not $1$. So you can't make the assertion above for all $k$.

share|cite|improve this answer

answered Jul 22 at 4:04

Key Flex

4,318424

share|cite|improve this answer

share|cite|improve this answer

answered Jul 22 at 4:04

Key Flex

4,318424

answered Jul 22 at 4:04

Key Flex

4,318424

answered Jul 22 at 4:04

Key Flex

4,318424

4,318424

add a comment | 

add a comment | 

up vote
6
down vote

The problem is that your proof of the induction step should include the step from $0$ to $1$; and that's where your argument fails.

share|cite|improve this answer

edited Jul 22 at 4:04

Key Flex

4,318424

answered Jul 22 at 3:37

Martin Argerami

116k1071164

add a comment | 

up vote
6
down vote

The problem is that your proof of the induction step should include the step from $0$ to $1$; and that's where your argument fails.

share|cite|improve this answer

edited Jul 22 at 4:04

Key Flex

4,318424

answered Jul 22 at 3:37

Martin Argerami

116k1071164

add a comment | 

up vote
6
down vote

up vote
6
down vote

The problem is that your proof of the induction step should include the step from $0$ to $1$; and that's where your argument fails.

share|cite|improve this answer

edited Jul 22 at 4:04

Key Flex

4,318424

answered Jul 22 at 3:37

Martin Argerami

116k1071164

The problem is that your proof of the induction step should include the step from $0$ to $1$; and that's where your argument fails.

share|cite|improve this answer

edited Jul 22 at 4:04

Key Flex

4,318424

answered Jul 22 at 3:37

Martin Argerami

116k1071164

share|cite|improve this answer

share|cite|improve this answer

edited Jul 22 at 4:04

Key Flex

4,318424

edited Jul 22 at 4:04

Key Flex

4,318424

edited Jul 22 at 4:04

Key Flex

4,318424

4,318424

answered Jul 22 at 3:37

Martin Argerami

116k1071164

answered Jul 22 at 3:37

Martin Argerami

116k1071164

answered Jul 22 at 3:37

Martin Argerami

116k1071164

116k1071164

add a comment | 

add a comment |