4 ms·

This reminds me why I don't like induction proofs. Although sound, almost by definition no insight can be obtained from it for either why the proposition is tru

by air7 9y ago

This reminds me why I don't like induction proofs. Although sound, almost by definition no insight can be obtained from it for either why the proposition is true, or why the proof itself is valid. Here's another proof I just though of that doesn't use induction: Let's prove that x^5-x is divisible by 10. x^5-x = x(x^4-1) = x(x^2+1)(X^2-1) We want to prove that among these 3 multiplied elements, we can find the factors 2 & 5. 2: If x is even, it's x. If x is odd, it's the other ones. 5: Consider the following table of : x | x^2 (mod 5) x | x^2 | Which element is divisible by 5 ------------------------------------------- 0 0 x 1 1 x^2-1 2 4 x^2+1 3 4 x^2+1 4 1 x^2-1 so we get that in all cases there is a factor of 5 as well. Not sure this provides more insight into why the proposition is true, but IMO this proof feels more valid.

eeereerews 9y ago
You can do it without a table by factoring x (x^2-1) (x^2+1) = x (x-1) (x+1) (x^2 - 4 + 5) = x (x-1) (x+1) ((x-2)(x+2) + 5) Now one of the five consecutive numbers (x-2), (x-1), x, (x+1), (x+2) must be divisible by 5, so the whole is as well. I agree with you about induction.
kleiba 9y ago
Intuitively, induction proofs are valid because you're checking the theorem for every natural number n. Of course, you're doing that in a clever way because the naive way would take a little too long, but still that's what it is all about.
davemp 9y ago
I find proof by induction very intuitive: “If every ‘legal’ step holds, then any way of chaining legal steps also holds”. There can be a lot of information gleaned from the steps (operational semantics for example). Playing around with induction on church encodings and other inductively defined structures certainly helped me to build the intuition though.
karthickgururaj 9y ago
That leads me to think what can be even more unsatisfying proof. How about the following: It is easy to see that the last digit of x^5 is same as k^5, where k is the last digit of x. Then the problem reduces to proving that the ten possibilities, 0^5, 1^5, 2^5, ... 9^5 ends respectively in 0, 1, 2, ...9.

by air7 9y ago

eeereerews 9y ago

You can do it without a table by factoring x (x^2-1) (x^2+1) = x (x-1) (x+1) (x^2 - 4 + 5) = x (x-1) (x+1) ((x-2)(x+2) + 5) Now one of the five consecutive numbers (x-2), (x-1), x, (x+1), (x+2) must be divisible by 5, so the whole is as well. I agree with you about induction.

kleiba 9y ago

Intuitively, induction proofs are valid because you're checking the theorem for every natural number n. Of course, you're doing that in a clever way because the naive way would take a little too long, but still that's what it is all about.

davemp 9y ago

I find proof by induction very intuitive: “If every ‘legal’ step holds, then any way of chaining legal steps also holds”. There can be a lot of information gleaned from the steps (operational semantics for example). Playing around with induction on church encodings and other inductively defined structures certainly helped me to build the intuition though.

karthickgururaj 9y ago

That leads me to think what can be even more unsatisfying proof. How about the following: It is easy to see that the last digit of x^5 is same as k^5, where k is the last digit of x. Then the problem reduces to proving that the ten possibilities, 0^5, 1^5, 2^5, ... 9^5 ends respectively in 0, 1, 2, ...9.