# Solve Proof by Induction: Explain What's Wrong

• cepheid
In summary, the proof presented in the conversation is flawed because it assumes that x-1 and y-1 are in the set of natural numbers, which is not necessarily true. This assumption leads to an incorrect conclusion and therefore the proof cannot be considered valid.
cepheid
Staff Emeritus
Gold Member

## Homework Statement

Explain what is wrong with the structure and/or reasoning of the following proof. Remember that saying the claim is false is not a justification.

For all x,y,n in {0,1,2,...}, if max(x,y) = n, then x=y.

Proof (by induction):

Base case: Suppose that n=0. If max(x,y) = 0 and x,y are in {0,1,2,...}, then x = y = 0.

Induction step: Assume that whenever we have max(x,y) = k, then x = y must follow. Next, suppose x,y are such that max(x,y) = k+1. Then it follows that max(x-1,y-1) = k, so by the inductive hypothesis, x-1 = y-1 ==> x = y, completing the induction step.

N/A

## The Attempt at a Solution

The claims is obviously false, but I cannot say for sure exactly where the reasoning fails. I think it has something to do with the statement: "Then it follows that max(x-1,y-1) = k."

Somehow, this must not be valid. I just don't know why. Can anyone shed light on this.

If x and y are in N={0,1,2,..} it isn't necessarily true that x-1 and y-1 are in N. If you want to show max(0,1)=1 implies 0=1, you are looking at max(-1,0)=0. That isn't covered in the k=0 case.

I don't know how to mark a thread as solved, but thanks for the help. That makes sense

It is possible that either x or y is equal to 0. If x= 0, then x-1 is not in the set 0, 1, 2, ... Same if y= 0.

## 1. What is proof by induction and how does it work?

Proof by induction is a mathematical technique used to prove statements that involve a natural number n. It involves proving that the statement is true for the first natural number, then assuming it is true for an arbitrary value of n and using that assumption to prove that it is true for n+1. This process is repeated until the statement is proven to be true for all natural numbers.

## 2. What is the base case in a proof by induction?

The base case in a proof by induction is the first natural number for which the statement is proven to be true. It serves as the starting point for the induction process and is essential in proving the statement for all other natural numbers.

## 3. What is the induction hypothesis and why is it important?

The induction hypothesis is the assumption that the statement is true for an arbitrary value of n. It is important because it allows us to prove that the statement is true for n+1 by using the assumption that it is true for n. This is the key step in the induction process.

## 4. What can go wrong in a proof by induction?

There are a few common mistakes that can occur in a proof by induction. One is not proving the base case, which means the statement is not proven to be true for the first natural number. Another mistake is not using the induction hypothesis correctly, which can lead to an incorrect proof. It is also important to make sure that the statement is true for all natural numbers, not just a few specific values.

## 5. How can I improve my skills in solving proofs by induction?

The best way to improve your skills in solving proofs by induction is to practice. Start with simple examples and work your way up to more complex ones. It is also helpful to understand the underlying concepts and principles behind proof by induction, such as the base case and induction hypothesis. Additionally, seeking feedback and guidance from experienced mathematicians can also help improve your skills.

Replies
10
Views
711
Replies
9
Views
606
Replies
4
Views
319
Replies
5
Views
1K
Replies
4
Views
2K
Replies
9
Views
2K
Replies
13
Views
2K
Replies
3
Views
1K
Replies
2
Views
1K
Replies
17
Views
1K