Prove every non empty subset of the natural numbers has a smallest element. (Well-Ordering Principle)WOP

Prove every non empty subset of the natural numbers has a smallest element. (Well-Ordering Principle) WOP

To prove this we must define a subset of the natural numbers T, and show that T is nonempty, and has a smallest element.

We will use a combination of taking the contrapositive and proving it by induction. That sounds more complicated than it is, so hold on to your hat and see the proof before thinking all this is confusing!

The contrapositive is to suppose that T has no smallest element. If this is true then there must be another set S that is equal to the natural numbers(N) so that we can make the statement:

S = N - T , or that is to say that S will be equal to N only if T is empty.

To prove this using iduction we take the first case in the natural numbers which is 1. 1 is the smallest element in the natural numbers and as T has no smallest element, 1 must be in S by our statement S = N - T

Now, say that a number k is an element in S, then that number cannot be in T, because if it were, it would imply that there is a smallest element in T, and also, k cannot be in T since k is in S. Then k+1 cannot be in T, by the same implication of there being a smallest element in T, and so k+1 must be an element in S.

So by induction S = N, or the set S is equal to the natural numbers, and since T has no smallest element, T has to be an empty subset of the natural numbers.

However, by contraposition, if T had an element, then it would have to have a smallest element. Thus, any non-empty subset of the natural numbers (N) has a smallest element, and this is the Well Ordering Principle.

Proof of the Fibonacci sequence and Golden Ratio

This is a proof of the Fibonacci sequence and its relation to the Golden Ratio.

If we consider the equation (x^2) - x - 1 we find it can be solved by letting x=a=(1+sqrt(5))/2)=1.618 which is the golden ratio.

We can prove that all numbers in the Fibonacci sequence produces solutions for this equation if we can prove that any number in the sequence f(n) is less than or equal to any solution before it a^(n-1)

We start by testing the first two cases which is a=1 and a=2, (1 and 2 are both Fibonacci numbers) thus we have 1 < = (a^0) = 1, and 1 < = a^1 = (1+sqrt(5))/2)

Now we prove the general case,

f(n) = f(n-1) + f(n-2) where f(n) is any Fibonacci number (in other words a Fibonacci number is generated by the addition of the two previous numbers, consider the first few numbers in the Fibonacci sequence: (1,2,3,5,8...)

f(n-1) + f(n-2) < = a^(n-2) + a^(n-3)

= a^(n-3) * (a+1) by factorization

= a^(n-3) * (a^2) (because a+1 is a solution to the equation (x^2) - x - 1

= a(n-1)

so therefore f(n) < = a^(n-1)

Prove that (4^n)-1 is divisible by 3 for all natural numbers

Prove that (4^n)-1 is divisible by 3 for all natural numbers

We will use induction for this proof, so first we prove the case for the first natural number 1:

(4^1) - 1 = 3 which is divisible by 3.

Now we need to prove the general case for n+1

4^(n+1) - 1

= 4(4^n) - 1

= 4((4^n) - 1) - 1 + 4

= 4((4^n) - 1) + 3

Now both (4^n - 1) and 3 are divisible by 3, thus by induction we can say for all natural numbers 4^n - 1 is divisible by 3.

Prove for all natural numbers a and b, there exists a natural number s such that a < sb (Archimedean Principle)

Prove for all natural numbers a and b, there exists a natural number s such that a < sb.

This is a proof of the Archimedean Principle which states that with a lever large enough a man could move the earth. In other words, with a multiple large enough, a can be surpassed by b.

This is a proof by induction, so we prove the first case which is 1 for the natural numbers.

If b = 1 then we choose s to be a+1. Then a < a+1 = sb, so the first case works.

Now let us assume the general case where b is equal to some natural number n. Then there exists an s such that a < sn < s(n+1), so the statement is true when b=n+1.

Thus, by induction there exists a natural number s such that a < sb for all natural numbers a and b. ~~~~

Prove for every natural number n, x-y divides (x^n) - (y^n)

Prove for every natural number n, x-y divides (x^n) - (y^n)

This is another proof by induction, so first we prove the first case, which for the natural numbers is 1.

x - y divides (x^1) - (y^1) = 1(x-y) so this is true.

Now by induction we must show that x-y divides x^(n+1) - y^(n+1)

x^(n+1) - y^(n+1)

= x(x^n) - y(y^n)

= x(x^n) - y(x^n) + y(x^n) - y(y^n)

= (x-y)(x^n) + y(x^n - y^n)

so now we have a form where x-y divides the first term (since x-y is a factor) and divides the second term((x^n - y^n)) by the hypothesis of induction.

Thus x-y divides (x^n) - (y^n) for all natural numbers n.

Prove that for all natural numbers n, n+3 < 5(n^2)

Prove that for all natural numbers n, n+3 < 5(n^2)

Once again we will use induction to solve this proof.

First we prove the case to be true for the first natural number:1

1+3 < 5*(1^2) that is to say 4 < 5

Now we will try prove the case to be true for n+1 to do this, we will add one to both sides and get:

(n+1) + 3 < 5(n^2) + 1

5(n^2) + 1 < 5 = 5(n+1)^2

thus

(n+1) + 3 < 5(n+1) ^2

The reason why we did all that algebra in the middle was to get the form n+1 on both sides which is important to use the principle of mathematical induction to conclude that n+3<5(n^2) for all n in the natural numbers. ~~~~

Prove for every natural number n, 1+3+5+...(2n-1)=(n^2)

Prove for every natural number n, 1+3+5+...(2n-1)=(n^2)

First let us consider an example where n=6, then we see that

1+3+5+7+9+11 = 36 = (6^2) = (n^2)

Now we have use to the principle of mathematical induction (PMI) to prove that this is true for all cases.

So we define a set S to be the set of natural numbers for which the statment:

for every natural number n, 1+3+5+...(2n-1)=(n^2)

is true.

First, let us find that the statement is true for the first natural number: 1=(1^2)

Thus, 1 is an element in our set S.

Now that we have proved the case for 1, we should prove the same thing for the next case which is (n+1), if we can prove that (n+1) is in the set S, then by induction we have proved it to be true for all n.

To do this we take the original antecedent:

1+3+5+...(2n-1)=(n^2) and add 2(n+1) - 1 to both sides, doing that we get

1+3+5+...(2n-1) + [2(n+1) - 1] = (n^2) + 2(n+1) - 1

= (n^2) + 2n + 1
= (n+1)^2

thus (n+1) is in our set S, and the statement: 1+3+5+...(2n-1)=(n^2), is true for all n.

Another way to think about a proof by induction is as a direct proof in which we are saying, for all n, n in S implies that n+1 is in S, and thus is true for all n.

~~~~