4 ms·

Inductive here meaning going from specific to general. I've never played the game, but it seems like you start with a specific example of the rule and try to ge

Inductive here meaning going from specific to general. I've never played the game, but it seems like you start with a specific example of the rule and try to generalize its definition. So in that sense, it's a little like pattern matching. "Proof by induction" is a proof technique where you prove that if something holds for n, then it also holds for n+1. That doesn't seem related to this game, but the game might help with your pattern matching abilities.

thaumasiotes 4y ago
> "Proof by induction" is a proof technique where you prove that if something holds for n, then it also holds for n+1. Proof by induction is actually a little more general than that. The idea of induction is that if: (1) you start with an object that has some property; (2) you modify it by a series of steps; and (3) all modification steps preserve this property then whatever object you end up with will also exhibit the property in question. The style of induction you're talking about modifies small numbers into larger numbers by the process of adding 1; in order to prove that your property holds for all integers larger than whatever your base case is, you also need a theorem that tells you all larger integers can be reached from smaller integers by a process of repeatedly adding 1.[1] (This is true, but it tends to get left out of ordinary induction proofs.) It is very common to use induction in this more general form when you have a set that is defined as (a) some elements that are in the set by definition, plus (b) some elements that are in the set by virtue of a membership rule [which usually takes the form "if x is in the set, then f(x) is also in the set"]. If you can prove that all of the base elements [from step (a)] have a property, and you can show that every membership rule produces an element that shares that property, then you have shown that every member of the set has the property. As an example, we can define the Fibonacci sequence this way: 1. The ordered triple (0, 0, 1) is in the set. 2. If (a, b, c) is in the set, then so is (a+1, c, b+c) Now every Fibonacci number F_n is the second element of the triple in the set whose first element is n. [Theorem: for any n >= 0, there is exactly one such element.] You can do induction on the Fibonacci numbers by proving things about the three dimensional map f(a, b, c) = (a+1, c, b+c). (You could also do induction on the more fundamental Fibonacci map f(a,b) = (b, a+b), but then you'd lose the ability to refer to the index of the Fibonacci number.) [1] Note: it's not necessary that there be no other way to reach your target element. As long as you can get from base case to target by using only steps that preserve the property, the target will have the property. If there's another path, using other steps, that doesn't necessarily preserve the property at every intermediate step, that doesn't matter.
- doorman2 4y ago
  I think you're missing a step (4). You have to prove your series of steps covers the entire domain of the problem.
  - thaumasiotes 4y ago
    I mentioned that: >> The style of induction you're talking about modifies small numbers into larger numbers by the process of adding 1; in order to prove that your property holds for all integers larger than whatever your base case is, you also need a theorem that tells you all larger integers can be reached from smaller integers by a process of repeatedly adding 1. But you get to define what the domain of the problem is; induction is just about functions preserving properties of their input. If your induction proof fails to cover a particular space, it's still a valid induction proof for some subset of the space.

thaumasiotes 4y ago

> "Proof by induction" is a proof technique where you prove that if something holds for n, then it also holds for n+1. Proof by induction is actually a little more general than that. The idea of induction is that if: (1) you start with an object that has some property; (2) you modify it by a series of steps; and (3) all modification steps preserve this property then whatever object you end up with will also exhibit the property in question. The style of induction you're talking about modifies small numbers into larger numbers by the process of adding 1; in order to prove that your property holds for all integers larger than whatever your base case is, you also need a theorem that tells you all larger integers can be reached from smaller integers by a process of repeatedly adding 1.[1] (This is true, but it tends to get left out of ordinary induction proofs.) It is very common to use induction in this more general form when you have a set that is defined as (a) some elements that are in the set by definition, plus (b) some elements that are in the set by virtue of a membership rule [which usually takes the form "if x is in the set, then f(x) is also in the set"]. If you can prove that all of the base elements [from step (a)] have a property, and you can show that every membership rule produces an element that shares that property, then you have shown that every member of the set has the property. As an example, we can define the Fibonacci sequence this way: 1. The ordered triple (0, 0, 1) is in the set. 2. If (a, b, c) is in the set, then so is (a+1, c, b+c) Now every Fibonacci number F_n is the second element of the triple in the set whose first element is n. [Theorem: for any n >= 0, there is exactly one such element.] You can do induction on the Fibonacci numbers by proving things about the three dimensional map f(a, b, c) = (a+1, c, b+c). (You could also do induction on the more fundamental Fibonacci map f(a,b) = (b, a+b), but then you'd lose the ability to refer to the index of the Fibonacci number.) [1] Note: it's not necessary that there be no other way to reach your target element. As long as you can get from base case to target by using only steps that preserve the property, the target will have the property. If there's another path, using other steps, that doesn't necessarily preserve the property at every intermediate step, that doesn't matter.

doorman2 4y ago
I think you're missing a step (4). You have to prove your series of steps covers the entire domain of the problem.
- thaumasiotes 4y ago
  I mentioned that: >> The style of induction you're talking about modifies small numbers into larger numbers by the process of adding 1; in order to prove that your property holds for all integers larger than whatever your base case is, you also need a theorem that tells you all larger integers can be reached from smaller integers by a process of repeatedly adding 1. But you get to define what the domain of the problem is; induction is just about functions preserving properties of their input. If your induction proof fails to cover a particular space, it's still a valid induction proof for some subset of the space.