that's log base 2 of n... log(n) implies log
base 10 of n, which is incorrect
Not if you're talking about asymptotic complexity. Constant coefficients are ignored, and the only difference between log_2(n) and log_10(n) is a constant factor of log(10)/log(2). (Again, the base of the logarithm doesn't matter because it just introduces a common factor that'll cancel itself).
For a proof by induction, you express what you're trying to prove as a statement with a parameter n - call it P(n). Then you show that it is true for P(1) (or some other n), and that if P(n) is true (for any n) then it implies that P(n+1) is true.
Then, for example, P(378) must be true because it is implied by P(377), which is implied by P(376), and so on down to P(2), which is implied by P(1), which you have shown is true separately.
If you've proved that P(n) implies P(n+1) for any n, without assuming any special cases such as that n is prime, then it must be true for all n >= 1.
Proving induction: the proof I've seen is a proof by contradiction based on the principle that the natural numbers are well-ordered. This means that any non-empty set of natural numbers must contain a lowest element.
Now suppose you have a statement, P, that P(1) is true, and that P(n) implies P(n+1). To prove that this is sufficient to show that P(n) is true for all n, first assume it isn't - ie there are some values, k, for which P(n) is not true.
Now let S be the set of all of these values, ie S = {k : P(k) is false}. As we have assumed that P(n) is not true for every n, S cannot be empty, so it must have a least element, x, by well-ordering. x cannot be 1 since we have shown P(1) is true separately.
Therefore we have that P(x) is false, but P(x-1) is true since x is the least element of S. But x-1 is a natural number because x is, so by the inductive step P(x-1) must imply P(x). Therefore P(x) must be true, but by definition it is false. This is a contradiction, and as all the logical reasoning since the assumption was sound, the assumption must be wrong - ie P(n) is true for all natural numbers n, so S is empty and x doesn't exist.
The Hurd can't be based on Linux because it's older. (Look at the "Linux is obsolete" flamewar where the Hurd was cited as a reason why there was no point developing Linux). It also has a very different architecture underneath. The drivers from Linux are presumably just for compatability with PC hardware, which I don't think was the platform that the Hurd was originally intended to run on.
Slashdot Mirror
that's log base 2 of n... log(n) implies log base 10 of n, which is incorrect
Not if you're talking about asymptotic complexity. Constant coefficients are ignored, and the only difference between log_2(n) and log_10(n) is a constant factor of log(10)/log(2). (Again, the base of the logarithm doesn't matter because it just introduces a common factor that'll cancel itself).
For a proof by induction, you express what you're trying to prove as a statement with a parameter n - call it P(n). Then you show that it is true for P(1) (or some other n), and that if P(n) is true (for any n) then it implies that P(n+1) is true.
Then, for example, P(378) must be true because it is implied by P(377), which is implied by P(376), and so on down to P(2), which is implied by P(1), which you have shown is true separately.
If you've proved that P(n) implies P(n+1) for any n, without assuming any special cases such as that n is prime, then it must be true for all n >= 1.
Proving induction: the proof I've seen is a proof by contradiction based on the principle that the natural numbers are well-ordered. This means that any non-empty set of natural numbers must contain a lowest element.
Now suppose you have a statement, P, that P(1) is true, and that P(n) implies P(n+1). To prove that this is sufficient to show that P(n) is true for all n, first assume it isn't - ie there are some values, k, for which P(n) is not true.
Now let S be the set of all of these values, ie S = {k : P(k) is false}. As we have assumed that P(n) is not true for every n, S cannot be empty, so it must have a least element, x, by well-ordering. x cannot be 1 since we have shown P(1) is true separately.
Therefore we have that P(x) is false, but P(x-1) is true since x is the least element of S. But x-1 is a natural number because x is, so by the inductive step P(x-1) must imply P(x). Therefore P(x) must be true, but by definition it is false. This is a contradiction, and as all the logical reasoning since the assumption was sound, the assumption must be wrong - ie P(n) is true for all natural numbers n, so S is empty and x doesn't exist.
AndyThe Hurd can't be based on Linux because it's older. (Look at the "Linux is obsolete" flamewar where the Hurd was cited as a reason why there was no point developing Linux). It also has a very different architecture underneath. The drivers from Linux are presumably just for compatability with PC hardware, which I don't think was the platform that the Hurd was originally intended to run on.