# Proving by Induction/Recursion

• mr.tea
In summary: I am not sure.In summary, the conversation discusses a problem involving a game where two players take turns removing matches from two heaps, and the player who removes the last match wins. The challenge is to prove that if the players start with equal-sized heaps, the second player has a winning strategy. The conversation includes a proposed solution using strong induction, but the person is unsure about its validity. The other person suggests considering different proofs, such as finding the least example where the second player doesn't have a winning strategy, or simply specifying a winning strategy for the second player.
mr.tea

## Homework Statement

I have a question that I need to prove(probably by induction): In a game, two players take turns removing any positive number of matches from one of two heaps. The player who removes the last match wins. Prove that if the players start out with heaps of equal size, then the second player has a winning strategy.

But I don't know if I am correct or not, and if I can use induction the way I use it here.

## Homework Equations

Induction/Strong induction

## The Attempt at a Solution

I thought to use here strong induction. It's easy to see for the base case(1) why it's true. For any other case(assume n), if the first player removes some matches(I assume he doesn't remove all the matches from one heap, that's an obvious loss for him, I guess the player is not an idiot), then the second player can remove equal matches from the other heap, and they are going back to case n-k which I assumed is true.

Well, another way is just to say that the second player can reduce the problem to 1 match on each heap which is an obvious win to the second player.

I am not sure about my use of the induction here.

Thank you.

mr.tea said:

## Homework Statement

I have a question that I need to prove(probably by induction): In a game, two players take turns removing any positive number of matches from one of two heaps. The player who removes the last match wins. Prove that if the players start out with heaps of equal size, then the second player has a winning strategy.

But I don't know if I am correct or not, and if I can use induction the way I use it here.

## Homework Equations

Induction/Strong induction

## The Attempt at a Solution

I thought to use here strong induction. It's easy to see for the base case(1) why it's true. For any other case(assume n), if the first player removes some matches(I assume he doesn't remove all the matches from one heap, that's an obvious loss for him, I guess the player is not an idiot), then the second player can remove equal matches from the other heap, and they are going back to case n-k which I assumed is true.

Well, another way is just to say that the second player can reduce the problem to 1 match on each heap which is an obvious win to the second player.

I am not sure about my use of the induction here.

Thank you.

What are you not sure about?

PeroK said:
What are you not sure about?
Thank you for the fast comment.

First, it looks way to easy.
Second, I always ask myself, how do we know that the case n-k ends with a win of the second player. I have done some cases, and look at all the combinations. Maybe all the cases before n-k ends like that but that case isn't.

I have just seen some "proof" that all the horses are at the same color. The problem was in the implication from case n=1 to case n=2, but all the other cases(from 2 to 3 and so on) were ok. How do I know that I don't have such a problem?

Thank you again!

mr.tea said:
Thank you for the fast comment.

First, it looks way to easy.
Second, I always ask myself, how do we know that the case n-k ends with a win of the second player. I have done some cases, and look at all the combinations. Maybe all the cases before n-k ends like that but that case isn't.

I have just seen some "proof" that all the horses are at the same color. The problem was in the implication from case n=1 to case n=2, but all the other cases(from 2 to 3 and so on) were ok. How do I know that I don't have such a problem?

Thank you again!

Either there's a flaw in the proof or there isn't. With your logic you could never prove anything, because you'd say: I think my proof is correct, but I remember once I got fooled by one of those paradoxical proofs, so maybe I've made a mistake somewhere.

PeroK said:
Either there's a flaw in the proof or there isn't. With your logic you could never prove anything, because you'd say: I think my proof is correct, but I remember once I got fooled by one of those paradoxical proofs, so maybe I've made a mistake somewhere.

Thank you again.

I think it might be just the induction idea. Maybe I need to get use to the power of induction.

But as I understand from you, my proof(or sketch of the proof) is correct (right?).

Thank you!

mr.tea said:
Thank you again.

I think it might be just the induction idea. Maybe I need to get use to the power of induction.

But as I understand from you, my proof(or sketch of the proof) is correct (right?).

Thank you!

You just have to ask yourself how you would play the game if you were playing second.

PeroK said:
You just have to ask yourself how you would play the game if you were playing second.

I would probably do the same as I wrote(trying to bring the game to a situation I already know I can win independently of the other player's moves).

mr.tea said:
I would probably do the same as I wrote(trying to bring the game to a situation I already know I can win independently of the other player's moves).

You have at least three proofs:

The strong induction proof

If there are games where the second player does not have a winning strategy, there must be a least example.

Simply specify the strategy and note that eventually you must hit 0-0 and win (you can't take positive numbers from a finite pile indefinitely).

PeroK said:
You have at least three proofs:

The strong induction proof

If there are games where the second player does not have a winning strategy, there must be a least example.

Simply specify the strategy and note that eventually you must hit 0-0 and win (you can't take positive numbers from a finite pile indefinitely).

I think that since we are talking about induction, probably the strong induction proof is appropriate here. But you are right, there are few other strategies which can prove the statement without induction.
Regarding the example, what would you do if you don't know if the statement is true\false and the number of combinations for "games" is high?

Thank you!

mr.tea said:
I think that since we are talking about induction, probably the strong induction proof is appropriate here. But you are right, there are few other strategies which can prove the statement without induction.
Regarding the example, what would you do if you don't know if the statement is true\false and the number of combinations for "games" is high?

Thank you!

PeroK said:
Sorry for my English.

If you have a similar game, but this time you don't know if the statement is true of false. And for each case(case n=1,2,...) the number of possibilities increases, let's say by powers of 3. How many cases would you check before you would try to decide if the statement is true or false?

mr.tea said:
Sorry for my English.

If you have a similar game, but this time you don't know if the statement is true of false. And for each case(case n=1,2,...) the number of possibilities increases, let's say by powers of 3. How many cases would you check before you would try to decide if the statement is true or false?

This was a very simple game. In general, it may be very difficult to determine who has the winning strategy. Take a look at:

https://en.wikipedia.org/wiki/Nim

PeroK said:
This was a very simple game. In general, it may be very difficult to determine who has the winning strategy. Take a look at:

https://en.wikipedia.org/wiki/Nim

So this game is Nim of two heaps. I didn't know that there are games with such mathematical theory about them. Absolutely beautiful! :) thank you.

## 1. What is the purpose of proving by induction/recursion?

Proving by induction/recursion is a method used in mathematics and computer science to prove that a statement or property holds for all natural numbers or data structures in a given set. It is particularly useful for proving the correctness of algorithms or mathematical formulas.

## 2. How does the process of proving by induction/recursion work?

The process involves three steps: the base case, the inductive hypothesis, and the inductive step. The base case is the initial value or condition that is proven to be true. The inductive hypothesis assumes that the statement is true for a certain value or condition. Lastly, the inductive step uses the hypothesis to prove that the statement is true for the next value or condition.

## 3. What is the difference between mathematical induction and structural induction?

Mathematical induction is used to prove statements about natural numbers, while structural induction is used to prove properties of data structures. Additionally, mathematical induction typically involves proving a statement for all natural numbers, while structural induction involves proving a statement for all elements in a data structure.

## 4. What are some common mistakes to avoid when using induction/recursion?

One common mistake is assuming that the statement is true for all values without properly proving the base case. Another mistake is incorrectly using the inductive step, such as making assumptions that are not supported by the inductive hypothesis. It is also important to carefully consider the scope of the statement and ensure that all relevant cases are covered.

## 5. Are there any real-world applications of induction/recursion?

Yes, proving by induction/recursion is commonly used in computer science for algorithm analysis and verification. It is also used in various mathematical proofs, such as in number theory and combinatorics. Additionally, the concept of recursion is often used in programming to solve problems by breaking them down into smaller subproblems.

Replies
29
Views
1K
Replies
5
Views
2K
Replies
6
Views
1K
Replies
7
Views
755
Replies
2
Views
3K
Replies
7
Views
2K
Replies
7
Views
5K
Replies
1
Views
1K
Replies
1
Views
1K
Replies
7
Views
723