Among lectures on Calculus I,II and III, ( Introduction to ) Linear Algebra and ( Introduction to ) Differential Equations from the UCCS ( University of Colorado and Colorado Springs ) Department of Mathematics you will find video lectures on Math 311 Number Theory by Professor Dr. Seung Son here. I have watched most of them earlier this year. This week I watched some of them again.

While watching a video on mathematical induction something amazing happened, not sure if I would call it a cognition, but it's close. Since I was able to do proofs by mathematical induction and thus understood it, I thought I was done studying mathematical induction. ( I mean both the MS221 and M208 exams included questions on induction). Well, I close-to-cognited that I didn't understand proofs by mathematical induction -at all-.

Do you? If so:

- state the first principle ( of mathematical induction ) using symbols only,

- state the second principle using symbols only,

- re-formulate: "Show that: ... $$\sum_{k=1}^{n}k = \frac{n(n+1)}{2}$$ ..." using Set Terminology,

- can you explain the difference between the first and second principle?

- give an example of a proof using the first principle,

- give an example of a statement which can only be proved with the second principle.

I failed ( note: past tense ) all answers to the questions above. Post is To Be Continued ...

3 bloggers

1 week ago

There is a new registration on the UCCS math video website. Make sure and email the administrator and he will give you an option to request access to the video archive.

ReplyDeletehttp://cmes.uccs.edu/registration/request.php

http://mathematics-diary.blogspot.com/2010/12/video-lectures-on-number-theory.html

ReplyDeleteActually, I never liked proofs by mathematical induction, as they just take out the beauty or genius that is expected to be involved in the mathematical proofs. I know its kind of late to post a comment on this blog but, even so, I'm doing for others who come here later.

Mathematical induction is actually proof by recursion.Meaning there by, we express the problem in form of a recurrence equation and then shift it to the values that we already have.

Stating first principle :

Any proposition function P(n) is true for all the n >= m, where m and m are natural numbers, if we can prove following,

a) P(m) is true

b) Assuming P(k) to be true, we can prove that P(k+1) is true

Now lets analyze these statements. By saying that P(m) is true we say that P(n) is true for the first natural number in out set of numbers for which we have to prove that P(n) holds true.

From the second statement if P(k) is true then, P(k+1) is also true directly implies

P(m+1) is true as P(m) is true

P(m+2) is true as P(m+1) is true

P(m+3) is true as P(m+2) is true

...

and so on. As you can see that by using these two simple statments we have proven that P(n) is true for any natural number greater than or equal to m.

Lets try to solve the simple question of adding natural numbers (as suggested in the post).

Lets say that S(k) is the sum of natural numbers from 1 to k.

Now we have to prove that this sum can be represented as

S(k) = k(k+1)/2

Lets apply the first principle on this problem.

a) S(1) = 1 as we know it

putting 1 into the formula 1(1+1)/2 = 1

So S(k) is true for k = 1

b) Assuming that S(k) is true that is S(k) = k(k+1)/2 is true lets prove that it should hold for S(k+1)

S(k+1) = 1 + 2 + 3 + ... k + (k+1)

= S(k) + (k+1)

= k(k+1)/2 + (k+1)

=(k+1)(k+2)/2

=(k+1)((k+1) + 1)/2

Do you see the pattern, its the formula given here by replacing k with (k+1).

Thus we have proved that S(k+1) is true given S(k) is true, but how does it imply that S(k) holds for all k > 1.

Lets try this

as S(1) is true ,S(2) should be true (as if S(k) is true then S(k+1) should be true)

as S(2) is true , S(3) should be true

as S(3) is true , S(4) should be true

...

and so on

Sorry for posting it into second comment but it did not allow me to post more than 4096 characters ;)

ReplyDeleteStarting the second principle :

Any proposition P(n) is true for all the n>=m, where m and n are natural numbers, if we can prove the following,

a) P(m) is true

b) Assuming P(n) to be true for m <= n <= k, we can prove P(k+1) to be true.

Same reasoning goes here, that is

as P(m) is true so, P(m+1) should be true

as P(m), P(m+1) are true so, P(m+2) should be true

as P(m), P(m+1), P(m+2) are true so, P(m+3) should be true

as P(m), P(m+1), P(m+2), P(m+3) are true so, P(m+4) should be true

...

so on

Thus P(m) is true for all natural numbers greater than or equal to m.

Lets take an example. The example of sum of natural numbers is not enough to depict the profoundness of second principle.

You'll think that we are using the first principle again. So I'll take a slightly different example.

I'll select a problem that I just devised, here it is

B(n) = B(n-1) + B(n-2) + ... B(1) = 2^(n-2)B(1) (2 to power (n-2) times B(1)) for all n >=2

Its as simple as it looks, we have whose nth term is sum of all previous terms

starting with the first part of the second principle

a) B(2) = B(1) ( as there is only one term before B(2))

from the proposition B(2) = 2^(2-2)B(1) = B(1)

so first part holds true.

moving to next

b) assuming B(2), B(3), ... B(k) hold true for the propostion we have to prove that it holds true for B(k+1)

B(k+1) = B(k) + B(k-1) + B(k-2) + ... B(1)

now putting B(k) = B(k-1) + B(k-2) + ... B(1) we get (as B(k) holds true for the propostion, as assumed)

B(k+1) = 2B(k-1) + 2B(k-2) + 2B(k-3) + ...2B(1) = 2(B(k-1) + B(k-2) + B(k-3) + ... B(1))

putting the value for B(k-1) we get (as B(k-1) holds true for proposition , as assumed)

B(k+1) = 4 (B(k-2) + B(k-3) + ... B(1)) = 2^2(B(k-2) + B(k-3) + ... B(1))

Going further we get

B(k+1) = 8 (B(k-3) + B(k-4) + ... B(1)) = 2^3(B(k-3) + B(k-4) + ... B(1))

B(k+1) = 16 (B(k-4) + ... B(1)) = 2^4(B(k-4) + ... B(1))

if go on applying the same rule we finally get

B(k+1) = 2^(k-2) (B(2) + B(1))

= 2^(k-2) (B(1) + B(1)) (proved in the first part that B(2) = B(1))

= 2^(k-1) B(1)

= 2^( (k+1) -2) B(1)

Do you see the pattern, we just proved the proposition for B(k+1)

as we have B(k+1) too in our list so we can prove that B(k+2) also holds true, then B(k+3) with the help of B(k+2) and other terms before it.

Here ends the discussion. Hope, you'll understand it.

Thanks for posting 'color less', interesting idea. - As with most of the math I read, I have to give it some time to work on me. Then come back and read again.

ReplyDelete