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.

~~~~

Euclid's Algorithm: Let a and b be two positive integers with a <= b. Let d be their greatest common divisor(GCD). Then there are two lists of...

Euclid's algorithm is a way to find the GCD of any Euclidian domain, in this case, the natural numbers.

Euclid's Algorithm: Let a and b be two positive integers with a <= b. Let d be their greatest common divisor(GCD). Then there are two lists of positive integers q(i) and r(i) such that

b > r(1) > r(2) > r(3) ... > r(k-1) > r(k) > r(k+1) = 0 and

a = bq(1) + r(1)
b = r(1)q(2) + r(2)
r(1) = r(2)q(3) + r(3)
r(2) = r(3)q(2) + r(4)
.
.
.
r(k-2) = r(k-1)q(k) + r(k)
r(k-1) = r(k)q(k+1) (that is, r(k+1) = 0 )

and therefore d = r(k)

Proof

Since a < = b then there exists a q(1) and r(1) such that a = bq(1) + r(1) where 0 < = r(1) < b , and therefore, since r(1) < b there exists a q(2) and r(2) such that b=r(1)q(2) + r(2) and so one for r(2)< r(1). If we keep going down the line of positive integers we reach a point were r(k+1)=0 and so it is evident that:

b > r(1) > r(2) > r(3) ... > r(k-1) > r(k) > r(k+1) = 0

Now, to show that d (the GCD) is equal to r(k) we have to show that r(k) < = d and r(k) > = d.

First we show that r(k) < = d.

We first notice that r(k) divides r(k-1) (because r(k-1) = r(k)q(k+1)), we also notice that r(k) divides r(k-2) because r(k-2) = r(k-1)q(k) + r(k), and so r(k) divides both r(k) and r(k-1) by the proof we did two days ago. (When another proof is used in a proof, it is called a lemma). Now, if we keep going up the line, we see that every number has a component of the previous integer, and so r(k) is a common divisor for all the numbers including a and b. Since d is the GCD for a and b, then r(k) has to be < = d by the proof we did yesterday.

Now we show that r(k) > = d.

We note that d divides r(1) since r(1) = a - bq(1), and since d divides r(1) then by the proof we did two days ago, d also divides r(2) since r(2) = b - r(1)q(2), continuing this pattern down the line we see that d divides r(k-1) and r(k) and therefore r(k) > = d.

Now we can say that d= r(k) which is equal to 1, and 1 is the GCD of all positive integers, or the natural numbers.